Wednesday, February 18, 2015

C++ Ordered Map

The std::map class is not ordered. Coming from any other programming language with a nice standard library this seems like a serious hole in C++. Boost has one, but not everyone can use Boost. So, here is one a threw together. Sure it's missing things, but that's what you get for free. Enjoy!

#ifndef ORDEREDMAP_H
#define ORDEREDMAP_H

#include <map>
#include <vector>
#include <assert .h="">


template <typename _t1="" _t2="" typename="">
struct pair
{
    typedef _T1 first_type;
    typedef _T2 second_type;
    
    first_type first;
    second_type second;
    
    pair(first_type Value1, second_type Value2) {
        first = Value1;
        second = Value2;
    }
};

template <typename tkey="" tvalue="" typename="">
class OrderedMap {
public:
    typedef TKey key_type;
    typedef TValue mapped_type;
    typedef pair<key_type mapped_type=""> container_type;
    
private:
    typedef std::map<key_type container_type=""> map_type;
    typedef std::vector<container_type> list_type;
    
    map_type FMap;
    list_type FList;
    
    typename list_type::iterator FindListItem(const key_type Key) {
        typename list_type::iterator result = FList.end();
        
        for (typename list_type::iterator iterator = FList.begin(); iterator != FList.end(); iterator++) {
            container_type *item = *iterator;
            
            if (item->first == Key) {
                result = iterator;
                break;
            }
        }
        
        return result;
    }
    
public:
    OrderedMap() {
    }
    
    ~OrderedMap() {
        for (typename list_type::iterator iterator = FList.begin(); iterator != FList.end(); iterator++) {
            container_type *item = *iterator;
            delete item;
        }
    }
    
    void Append(key_type Key, mapped_type Value) {
        container_type *item = new container_type(Key, Value);
        item->first = Key;
        item->second = Value;
        
        FMap.insert(std::pair<key_type container_type="">(Key, item));
        FList.push_back(item);
    }
    
    void Insert(size_t Index, key_type Key, mapped_type Value) {
        container_type *item = new container_type(Key, Value);
        item->first = Key;
        item->second = Value;
        
        FMap.insert(std::pair<key_type container_type="">(Key, item));
        FList.insert(FList.begin() + Index, item);
    }
    
    void Remove(key_type Key) {
        typename list_type::iterator iterator = FindListItem(Key);
        
        if (iterator != FList.end()) {
            FMap.erase(Key);
            FList.erase(iterator);
        }
    }
    
    void Remove(size_t Index) {
        typename list_type::iterator iterator = FList.begin() + Index;
        
        if (iterator != FList.end()) {
            container_type* item = *iterator;
        
            if (item != NULL) {
                FMap.erase(item->first);
                FList.erase(iterator);
            }
        }
    }
    
    mapped_type &operator[](key_type Key) {
        container_type* item = FMap[Key];
        assert(item != NULL);
        
        if (item != NULL) {
            return item->second;
        }
        
        throw std::out_of_range("Index out of range");
    }
    
    mapped_type &operator[](size_t Index) {
        assert(Index >= 0 && Index < Count());
        container_type* item = FList[Index];
        assert(item != NULL);
        
        if (item != NULL) {
            return item->second;
        }
        
        throw std::out_of_range("Index out of range");
    }
    
    size_t Count() {
        return FList.size();
    }
};

#endif //ORDEREDMAP_H

Update: March, 25 2015 - The code was not escaped properly and didn't show up right. Now it should be better.