Ordered hash table. The order is given by the order of key-value insertion.

Ordered Hash Table

template<typename K, typename V>
struct key2value  {
    typedef K                                   argument_type;
    typedef V					mapped_type;
    typedef boost::unordered_map<K,V>           hash_type;
    typedef typename hash_type::value_type      result_type;
    typedef boost::shared_ptr<hash_type>        hash_ptr;

    key2value(const hash_ptr& h):hash_(h) {
    }
    const result_type& operator () (const argument_type& key) const {
	return *hash_->find(key);
    }
private:
    hash_ptr	hash_;
};


/**
 * A Hash table which remembers the keys order
 * It implements 3 different types of iterators
 * iterator:		standard iterator over key-value pair container
 * key_iterator:	iterator over ordered collection of keys
 * ord_iterator:	iterator over ordered collection of key-value pairs
 */
template<class K, class V>
class OrderedDictionary {
public:
    typedef boost::unordered_map<K,V>                       hash_type;
    typedef typename hash_type::size_type                   size_type;
    typedef key2value<K,V>                                  vtransform;
    typedef boost::shared_ptr<hash_type>                    hash_ptr;
    typedef typename hash_type::key_type                    key_type;
    typedef std::vector<key_type>                           key_container;
    typedef typename hash_type::mapped_type                 mapped_type;
    typedef typename hash_type::value_type                  value_type;
    // Iterators
    typedef typename hash_type::iterator                    hash_iterator;
    typedef typename hash_type::const_iterator              const_hash_iterator;
    typedef typename key_container::iterator                key_iterator;
    typedef typename key_container::const_iterator          const_key_iterator;
    typedef boost::transform_iterator<vtransform,key_iterator>
                                                            iterator;
    typedef boost::transform_iterator<vtransform,const_key_iterator>
                                                            const_iterator;

    OrderedDictionary():hash_(new hash_type){
    }
    // Standard Library Interface
    hash_iterator find(const key_type& k) const {
        return hash_->find(k);
    }
    const_hash_iterator find(const key_type& k) {
        return hash_->find(k);
    }
    size_type size() const {
        return keys_.size();
    }
    std::pair<hash_iterator, bool> insert(const value_type& va) {
        std::pair<hash_iterator, bool> re = hash_->insert(va);
        if(re.second)
            keys_.push_back(re.first->first);
        return re;
    }
    void clear() {
        hash_->clear();
        keys_.clear();
    }

    size_type erase (const key_type& key) {
        size_type s = hash_->erase(key);
        for(key_iterator it=key_begin();it!=key_end();++it) {
            if(*it == key) {
                keys_.erase(it);
                break;
            }
        }
        return s;
    }

    const_iterator begin() const {
        return boost::make_transform_iterator(keys_.begin(),vtransform(hash_));
    }
    const_iterator end() const {
        return boost::make_transform_iterator(keys_.end(),vtransform(hash_));
    }
    iterator begin() {
        return boost::make_transform_iterator(keys_.begin(),vtransform(hash_));
    }
    iterator end() {
        return boost::make_transform_iterator(keys_.end(),vtransform(hash_));
    }

    const_key_iterator key_begin() const {
        return keys_.begin();
    }
    const_key_iterator key_end() const {
        return keys_.end();
    }
    key_iterator key_begin() {
        return keys_.begin();
    }
    key_iterator key_end() {
        return keys_.end();
    }

    const_hash_iterator hash_begin() const {
        return hash_->begin();
    }
    const_hash_iterator hash_end() const {
        return hash_->end();
    }
    hash_iterator hash_begin() {
        return hash_->begin();
    }
    hash_iterator hash_end() {
        return hash_->end();
    }

    // Additional Methods
    const key_type& key(unsigned idx) const {
        CASTOR_REQUIRE(idx<keys_.size(),"Out of bound");
        return keys_[idx];
    }
    const_hash_iterator get(unsigned idx) const {
        return hash_->find(key(idx));
    }
    hash_iterator get(unsigned idx) {
        return hash_->find(key(idx));
    }
protected:
    hash_ptr            hash_;
    key_container	keys_;
};