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
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