Creating an Indexed Ordered Map

Question

I have looked around here and similar sites the past few days and have spent many hours trying to come up with a solution and would like to reach out for advice.

I have come to the disappointing conclusion that without going into boost libraries for C++ there is no possible way to create an associative container which retains an indexed ordering.

More clearly and specifically what I am in need of, is a map which can lookup using operator[key] but also is indexed in the order elements were added for iteration purposes.

I decided this morning I would need to write one myself, and I have tried a few approaches using maps of maps and vectors of pairs, etc. But nothing has actually worked and getting all of the functionality I am looking for is surprisingly not easily achievable whatsoever in this language. Ive got to be wrong right? Has anyone else had an experience with needing this functionality or familiar with this concept that could point me in the right direction of what I am looking for?

Many thanks in advance! Happy new year everyone.

Answer 1

Warning: This is a very rough mock-up of the desired behaviour. This isn't anywhere near good code, but it's quick and should demonstrate a technique for doing this.

You should use existing solutions like Boost's multi_index before considering rolling your own. It'll be easier, faster, less error-prone, and better designed.

template<typename Key, typename Val>
class OrderedMap
{
private:
    std::vector<std::pair<Key, Val>> ordered;
    std::map<Key, std::size_t> lookup;

public:
    void insert(Key k, Val v)
    {
        ordered.push_back(std::pair<Key, Val>(k, v));
        lookup.emplace(k, ordered.size() - 1);
    }

    Val find(Key k)
    {
        std::size_t index = lookup[k];
        return ordered[index].second;
    }
    // "typename" needed as the "iterator" is a dependent type
    typename std::vector<std::pair<Key, Val>>::iterator begin()
    {
        return ordered.begin();
    }
    typename std::vector<std::pair<Key, Val>>::iterator end()
    {
        return ordered.end();
    }
};

---

All we need is a std::vector<std::pair<Key, Val>> to keep track of the actual order of elements that were inserted, and a std::map<Key, std::size_t> to keep track of the association between keys and value indices. Then we can delegate the functionality we want from this class to the functions of these internal backing/lookup structures.

The interface this class provides between the desired behaviour and the internal containers can be as robust as you please - here, I've only fleshed out the ugly bones needed for a demo.

---

See a quick demo here.

OrderedMap<std::string, int> m;
m.insert("1", 1);
m.insert("2", 2);
m.insert("3", 3);

std::cout << m.find("2") << std::endl << std::endl;

for (auto i = m.begin(); i != m.end(); i++)
    std::cout << i->first << " " << i->second << std::endl;
std::cout << std::endl;

Yields the output:

2

1 1
2 2
3 3