定数マップ

昨日のエントリの続き。
ソート済み配列が手に入るとマップが作れます。ソートされていなくても線形検索すればいいんですが、それはそれ、効率よく検索したいじゃないですか。ソート済みなら二分探索ができるので、二分探索で実装した定数マップです。

以下コード。

// ConstMap.h

#ifndef CONSTMAP_H
#define CONSTMAP_H

#include "ConstSortedArray.h"

#include <stdexcept>

namespace emattsan
{

template<typename Key, typename T>
class ConstMap
{
public:
    typedef Key key_type;
    typedef T   mapped_type;

    struct Value
    {
        key_type    key;
        mapped_type value;

        bool operator < (const Value& other) const
        {
            return key < other.key;
        }
    };

    typedef Value value_type;


    template<int N>
    class Container
    {
    public:
        static const int size = N;

        explicit Container(const value_type (&array)[N]) : array_(array)
        {
        }

        const mapped_type& operator [] (const key_type& key) const
        {
            int left  = 0;
            int right = N;
            for(;;)
            {
                if(left >= right)
                {
                    throw std::out_of_range("not found");
                }

                int mid = (left + right) / 2;
                if(array_[mid].key == key)
                {
                    return array_[mid].value;
                }
                else if(array_[mid].key < key)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid;
                }
            }
        }

    private:
        const ConstSortedArray<value_type, N> array_;
    };
};

} // namespace emattsan

#endif//CONSTMAP_H

テスト。

#include "ConstMap.h"

#include <iostream>

namespace
{
template<typename T, int N>
char (&numberof_(T (&array)[N]))[N];
}

#define numberof(array) sizeof(numberof_(array))


typedef emattsan::ConstMap<int, const char*> SampleMap;

static const SampleMap::value_type items[] =
{
    { 1, "one"   },
    { 5, "five"  },
    { 8, "eight" },
    { 3, "three" },
    { 0, "zero"  },
    { 7, "seven" },
    { 4, "four"  },
    { 6, "six"   },
    { 2, "two"   },
    { 9, "nine"  }
};

int main(int, char* [])
{
    SampleMap::Container<numberof(items)> map(items);

    try
    {
        for(int i = 0; i < 11; ++i)
        {
            std::cout << map[i] << std::endl;
        }
    }
    catch(const std::exception& e)
    {
        std::cerr << "EXCEPTION THROWN : " << e.what() << std::endl;
    }

    return 0;
}