wxOrderedMap

If you have a cool piece of software to share, but you are not hosting it officially yet, please dump it in here. If you have code snippets that are useful, please donate!
Post Reply
eranif
Moderator
Moderator
Posts: 607
Joined: Tue Nov 29, 2005 7:10 pm
Location: Israel

wxOrderedMap

Post by eranif » Wed Jun 06, 2012 4:27 pm

I often find myself in need of a container similar to std::map but that also maintains the order
in which elements were inserted.

Attached is my version of the wxOrderedMap

Code: Select all

#ifndef WX_ORDERED_MAP_H
#define WX_ORDERED_MAP_H

#include <map>
#include <list>

/// A container that allows fast insertions / retrieval of elements
/// And also maintains the order of which elements where inserted
template<typename Key, typename Value>
class wxOrderedMap
{
    typedef std::pair<Key, Value> Pair_t;
    typedef std::list<Pair_t> List_t;
    typedef std::map<Key, typename List_t::iterator> Map_t;

public:
    typedef typename List_t::const_iterator ConstIterator;
    typedef typename List_t::iterator Iterator;

protected:
    Map_t  m_map;
    List_t m_list;

public:
    wxOrderedMap() {}
    virtual ~wxOrderedMap() {
        m_map.clear();
        m_list.clear();
    }

    void Put(const Key& k, const Value& v) {
        Iterator iter = m_list.insert(m_list.end(), Pair_t(k, v));
        m_map.insert(std::make_pair<Key, Iterator>(k, iter));
    }

    Value &Get(const Key& k) {
        static Value NullValue;
        typename Map_t::iterator iter = m_map.find(k);
        if(iter == m_map.end())
            return NullValue;
        else {
            return iter->second->second;

        }
    }

    const Value &Get(const Key& k) const {
        static Value NullValue;
        typename Map_t::const_iterator iter = m_map.find(k);
        if(iter == m_map.end())
            return NullValue;
        else {
            return iter->second->second;

        }
    }

    bool Contains(const Key& k) const {
        return m_map.count(k);
    }

    void Remove(const Key &k) {
        typename Map_t::iterator iter = m_map.find(k);
        if(iter == m_map.end()) {
            // nothing to remove here
            return;
        }

        m_list.erase(iter->second);
        m_map.erase(iter);
    }

    ConstIterator Begin() const {
        return m_list.begin();
    }

    ConstIterator End() const {
        return m_list.end();
    }

    Iterator Begin() {
        return m_list.begin();
    }

    Iterator End() {
        return m_list.end();
    }
};

#endif // WX_ORDERED_MAP_H
Here is an example of usage:

Code: Select all

#include <stdio.h>
#include "wx_ordered_map.h"
#include <string>

void print(wxOrderedMap<std::string, std::string>& mp)
{
    // the iterator is of type:
    // std::pair<Key, Value>
    wxOrderedMap<std::string, std::string>::ConstIterator iter = mp.Begin();
    for(; iter != mp.End(); iter++) {
        printf("%s = %s\n", (*iter).first.c_str(),  (*iter).second.c_str());
    }
}

int main(int argc, char **argv)
{
	wxOrderedMap<std::string, std::string> mymap;
    
    mymap.Put("fruit",    "apple");
    mymap.Put("car",      "jeep");
    mymap.Put("game",     "wow");
    mymap.Put("computer", "linux");
    
    print(mymap);
    
    // Modify item (fetching an item is similar to fetching it from std::map)
    mymap.Get("fruit") = "banana";
    print(mymap);
    
    // Remove item (the complexity of removing an item is similar to std::map::find)
    mymap.Remove("car");
    print(mymap);
    
    if(!mymap.Contains("car")) {
        printf("Item 'car' does not exists\n");
    }
    
    return 0;
}


Eran
IDE: CodeLite + wxCrafter
OS: All
https://wxcrafter.codelite.org
https://codelite.org

Post Reply