Map

// Dynamically sized map using po2b memory. Also see class MapMem in Memory section for 
// additional functions used by this template.
template<typename K, typename I>
class Map : public MapMem
{
public:
    class const_iterator
    {
    public:
        struct Pair { const K &key; const I &item; };
        typedef const_iterator self_type;
        typedef const Pair value_type;
        typedef value_type reference;
        typedef int difference_type;

        const K &Key() const { return map->GetKey(n); }
        const I &Item() const { return map->GetItem(n); }

        self_type operator++() { n++; return *this; }
        self_type operator++(int ignore) { self_type i = *this; n++; return i; }
        reference operator*() const { return { map->GetKey(n), map->GetItem(n) }; }
        bool operator==(const self_type &rhs) const { return n == rhs.n; }
        bool operator!=(const self_type &rhs) const { return n != rhs.n; }

        const_iterator(const Map<K, I> &map, int n) : map(&map), n(n) {}
        const_iterator() : map(0), n(0) {}

    private:
        const Map<K, I> *map;
        int n;
    };

    class iterator
    {
    public:
        struct Pair { const K &key; I &item; };
        typedef iterator self_type;
        typedef Pair value_type;
        typedef value_type reference;
        typedef int difference_type;

        const K &Key() const { return map->GetKey(n); }
        I &Item() const { return map->GetItem(n); }

        self_type operator++() { n++; return *this; }
        self_type operator++(int ignore) { self_type i = *this; n++; return i; }
        reference operator*() const { return { map->GetKey(n), map->GetItem(n) }; }
        bool operator==(const self_type &rhs) const { return n == rhs.n; }
        bool operator!=(const self_type &rhs) const { return n != rhs.n; }

        iterator(Map<K, I> &map, int n) : map(&map), n(n) {}
        iterator() : map(0), n(0) {}

    private:
        Map<K, I> *map;
        int n;
    };

    class const_reverse_iterator
    {
    public:
        struct Pair { const K &key; const I &item; };
        typedef const_reverse_iterator self_type;
        typedef const Pair value_type;
        typedef value_type reference;
        typedef int difference_type;

        const K &Key() const { return map->GetKey(n); }
        const I &Item() const { return map->GetItem(n); }

        self_type operator++() { n--; return *this; }
        self_type operator++(int ignore) { self_type i = *this; n--; return i; }
        reference operator*() const { return { map->GetKey(n), map->GetItem(n) }; }
        bool operator==(const self_type &rhs) const { return n == rhs.n; }
        bool operator!=(const self_type &rhs) const { return n != rhs.n; }

        const_reverse_iterator(const Map<K, I> &map, int n) : map(&map), n(n) {}
        const_reverse_iterator() : map(0), n(0) {}

    private:
        const Map<K, I> *map;
        int n;
    };

    class reverse_iterator
    {
    public:
        struct Pair { const K &key; I &item; };
        typedef reverse_iterator self_type;
        typedef Pair value_type;
        typedef value_type reference;
        typedef int difference_type;

        const K &Key() const { return map->GetKey(n); }
        I &Item() const { return map->GetItem(n); }

        self_type operator++() { n--; return *this; }
        self_type operator++(int ignore) { self_type i = *this; n--; return i; }
        reference operator*() const { return { map->GetKey(n), map->GetItem(n) }; }
        bool operator==(const self_type &rhs) const { return n == rhs.n; }
        bool operator!=(const self_type &rhs) const { return n != rhs.n; }

        reverse_iterator(Map<K, I> &map, int n) : map(&map), n(n) {}
        reverse_iterator() : map(0), n(0) {}

    private:
        Map<K, I> *map;
        int n;
    };

    // Get constant begin iterator.
    const_iterator begin() const { return const_iterator(*this, 0); }

    // Get constant end iterator.
    const_iterator end() const { return const_iterator(*this, GetCount()); }

    // Get begin iterator.
    iterator begin() { return iterator(*this, 0); }

    // Get end iterator.
    iterator end() { return iterator(*this, GetCount()); }

    // Get constant reverse begin iterator.
    const_reverse_iterator rbegin() const { return const_reverse_iterator(*this, GetCount() - 1); }

    // Get constant reverse end iterator.
    const_reverse_iterator rend() const { return const_reverse_iterator(*this, -1); }

    // Get reverse begin iterator.
    reverse_iterator rbegin() { return reverse_iterator(*this, GetCount() - 1); }

    // Get reverse end iterator.
    reverse_iterator rend() { return reverse_iterator(*this, -1); }

    // Get key at index. Sequential access by index returns keys in key order.
    K &GetKey(int index) const { return *(K *)MapMem::GetKey(index); }

    // Get item at index. Sequential access by index returns items in key order.
    I &GetItem(int index) const { return *(I *)MapMem::GetItem(index); }

    // Get item using key. Returns 0 if not found.
    I *operator [] (const K &key) const { return (I *)Find(&(K &)key); }

    // Construct map. Use estimated maximum elemements for [incr].
    Map(uint incr = 8) : MapMem((uint)sizeof(I), (uint)sizeof(K), incr, CompareKeys, ConstructKey, IDestruct, KDestruct) {}

    // Destructor.
    ~Map() {}

private:
    static int CompareKeys(cptr a_, cptr b_) { K &a = *(K *)a_; K &b = *(K *)b_; return a < b ? -1 : a > b ? 1 : 0; }
    static void ConstructKey(void *mem, cptr key) { new (mem) K(*(K *)key); }
    static void IDestruct(void *ptr) { ((I *)ptr)->~I(); }
    static void KDestruct(void *ptr) { ((K *)ptr)->~K(); }
};