python 3.7 dict (insertion ordered) equivalent in c++

Question

There are several questions regarding the c++ equivalents to pythons dict. Since python 3.7, however, python dictionaries preserves insertion order. All previous answers give std::map or std::unordered_map as the answer, but they do not provide this property. std::map orders by key values but not in order of insertion.

I know that the key values in python can also have different types, but that's not what this question is about. For this question i would restrict that there is only one key type.

So what would be the equivalent to a dict that preserves the insertion order in c++?

Can something like this be assembled from standard library containers? No matter which c++ standard.

The C++ standard library has no equivalent for this data structure, since this isn’t a behaviour found in “classical” map data structures. Of course you can write your own, using a separate `std::vector` that contains the elements, coupled with a `std::unordered_map` that maps keys to indices in that vector. — Before implementing this I would think hard whether the Python semantics are *actually* required for your use-case, since I haven’t found this to be the case very often in real-world applications. — Konrad Rudolph, Oct 03 '22 at 08:26
I don't know about such a container, but depending on the operations on the map you could write a wrapper data structure with a value type that's basically a linked list node and simply keep track of the last insertion point. Alternatively simply store pointers to the pairs in a vector on insertion (;This will make the remove operation more expensive though). — fabian, Oct 03 '22 at 08:28
This question really doesn't concern Python people. You are asking for an associative container which remembers insertion order in C++. That it is similar to Python `dict` is just tangential. — Passer By, Oct 03 '22 at 08:53
[boost::multi_index](https://www.boost.org/doc/libs/1_80_0/libs/multi_index/doc/index.html) lets you construct a map-like container with an insertion order index — Caleth, Oct 03 '22 at 09:15
duplicates: [A std::map that keep track of the order of insertion?](https://stackoverflow.com/q/1098175/995714), [c++ Container that preserve insertion order](https://stackoverflow.com/q/66226727/995714), [Keep the order of unordered_map as we insert a new key](https://stackoverflow.com/q/35053544/995714). Did you do any research? — phuclv, Oct 03 '22 at 14:26
Does this answer your question? [c++ Container that preserve insertion order](https://stackoverflow.com/questions/66226727/c-container-that-preserve-insertion-order) — phuclv, Oct 03 '22 at 14:27

Victor Gubin · Answer 1 · 2022-10-03T14:11:51.357

C++ standard library doesn't have a linked hash table container out of the box. This kind of container introduces additional memory overhead to save insertion order, which is not needed in most of common scenarios. This behavior doesn't satisfy a common C++ concept: "don't pay for something you don't use". At the same time, if you still need to save insertions order you can trivially combine std::list - doubly linked list and unordered_map - hash table in a single class.

For example:

#include <iostream>

#include <list>
#include <unordered_map>

template<typename K, typename V, typename H = std::hash<K> >
class linked_hash_map
{
private:
    typedef std::list<V> holder_container_t;
public:
    typedef typename holder_container_t::iterator iterator;
    typedef typename holder_container_t::const_iterator const_iterator;
private:
    typedef typename std::unordered_map<K, iterator> access_container_t;
public:
    linked_hash_map():
        holder_(),
        index_()
    {}

    std::pair<iterator, bool> insert( const std::pair<K,V>& entry)
    {
        holder_.push_back( entry.second );
        auto idx_insert = index_.insert( std::make_pair(entry.first, --holder_.end() ) );
        if(!idx_insert.second) {
            holder_.pop_back();
            return std::make_pair(holder_.end(),false);
        }
        else {
            return std::make_pair(--holder_.end(),true);
        }
    }

    iterator erase(const K& key)
    {
        auto ret = index_.find(key);
        if(ret == index_.end()) {
            return end();
        }
        index_.erase(ret);
        return holder_.erase( ret->second );
    }

    bool contains(const K& k) const
    {
        return index_.contains(k);
    }

    iterator find(const K& key)
    {
        auto ret = index_.find(key);
        return  ( ret == index_.end() ) ? end() : ret->second;
    }

    const_iterator find(const K& key) const
    {
        auto idx = index_.find(key);
        return idx == index_.cend() ? cend() : *idx;
    }

    iterator begin()
    {
        return holder_.begin();
    }

    iterator end()
    {
        return holder_.end();
    }

    const_iterator cbegin() const
    {
        return holder_.cbegin();
    }

    const_iterator cend() const
    {
        return holder_.cend();
    }

private:
    holder_container_t holder_;
    access_container_t index_;
};

int main()
{

    linked_hash_map<std::string, std::size_t> lhm;

    // fill a map in a reverse order
    for(int i=10; i >= 0 ; i--) {
        auto key = std::string("Test") + std::to_string(i);
        lhm.insert( std::make_pair( key, i ) );
    }

    //  look up for elements
    auto sret = lhm.find("Test5");
    if( lhm.end() != sret )
        std::cout << "Test5 = " << *sret << std::endl;

    sret = lhm.find("Test7");
    if( lhm.end() != sret )
        std::cout << "Test7 = " << *sret << std::endl;

    lhm.erase("Test5");
    sret = lhm.find("Test5");
    if( lhm.end() != sret )
        std::cout << "Test5 = " << *sret << std::endl;
    else
        std::cout << "Test5 not found" << std::endl;

    // Iterate over the map by values in their insert order
    for(auto it: lhm) {
        std::cout<< it << ' ';
    }

    return 0;
}

python 3.7 dict (insertion ordered) equivalent in c++

1 Answers1