A Std::Map That Keep Track of the Order of Insertion

How to retrieve the elements from map in the order of insertion?

If you are not concerned about the order based on the int (IOW you only need the order of insertion and you are not concerned with the normal key access), simply change it to a vector<pair<int, char*>>, which is by definition ordered by the insertion order (assuming you only insert at the end).

If you want to have two indices simultaneously, you need, well, Boost.MultiIndex or something similar. You'd probably need to keep a separate variable that would only count upwards (would be a steady counter), though, because you could use .size()+1 as new "insertion time key" only if you never erased anything from your map.

c++ Container that preserve insertion order

There is no standard library container that both provides fast access by key (which is presumably why you're using std::map to begin with) and "preserves insertion order". If you really need access by key, then iteration order is something you give up control over.

If you need to recover the order of insertion, then you are going to have to preserve it. The simplest way to do that is to just store a vector of map iterators alongside your map. When you insert an item into the map, push the new iterator for it to the back of the vector too.

Keep the order of unordered_map as we insert a new key

Not with an unordered associative data structure. However, other data structures preserve order, such as std::map which keeps the data sorted by their keys. If you search Stackoverflow a little, you will find many solutions for a data structure with fast key-based lookup and ordered access, e.g. using boost::multi_index.

If it is just about adding values to a container, and taking them out in the order of insertion, then you can go with something that models a queue, e.g. std::dequeue. Just push_back to add a new value, and pop_front to remove the oldest value. If there is no need to remove the values from the container then just go with a std::vector.

a C++ hash map that preserves the order of insertion

#include <iostream>
#include "boost/unordered_map.hpp"

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>

using namespace std;
using namespace boost;
using namespace boost::multi_index;


struct key_seq{};
struct key{};

struct Data_t
{
    int key_;
    int data_;
    Data_t (int key_v, int data_v) : key_(key_v), data_(data_v) {}
};

int main()
{
    typedef multi_index_container<
        Data_t,
        indexed_by<
            hashed_unique<tag<key>,  BOOST_MULTI_INDEX_MEMBER(Data_t,int,key_)>,
            sequenced<tag<key_seq> >
        >
    > Map;

    typedef Map::const_iterator It;

    typedef index<Map,key>::type Map_hashed_by_key_index_t;
    typedef index<Map,key>::type::const_iterator  Map_hashed_by_key_iterator_t;

    typedef index<Map,key_seq>::type Map_sequenced_by_key_index_t;
    typedef index<Map,key_seq>::type::const_iterator  Map_sequenced_by_key_iterator_t;

    Map m;
    m.insert(Data_t(11,0));
    m.insert(Data_t(0,1));
    m.insert(Data_t(21,1));

    {
        cout << "Hashed values\n";
        Map_hashed_by_key_iterator_t i = get<key>(m).begin();
        Map_hashed_by_key_iterator_t end = get<key>(m).end();
        for (;i != end; ++i) {
            cout << (*i).key_ << " " << (*i).data_ << endl;
        }
    }

    {
        cout << "Sequenced values\n";
        Map_sequenced_by_key_iterator_t i = get<key_seq>(m).begin();
        Map_sequenced_by_key_iterator_t end = get<key_seq>(m).end();
        for (;i != end; ++i) {
            cout << (*i).key_ << " " << (*i).data_ << endl;
        }
    }

    return 0;
}

Insertion order in nested map c++

Is there a way to keep track of order of char saved to the map?

Yes. You can copy the returned iterator when you insert into the map, and push that iterator into a vector. Elements pushed into a vector remain in the insertion order, so it will keep track for you. Alternatively you might just push the char value, depending on what you want to keep track of - the character or the map element. Also, you might need to store a pair of both the inner and outer iterators depending how you use them.

Note that you must use std::map::insert to get the iterator instead of operator[].

C++ STL map I don't want it to sort!

There is no standard container that does directly what you want. The obvious container to use if you want to maintain insertion order is a vector. If you also need look up by string, use a vector AND a map. The map would in general be of string to vector index, but as your data is already integers you might just want to duplicate it, depending on your use case.

Call member function of std::map value object on insertion

You can do it in C++17 efficient:

auto [iter, success] = myMap.try_emplace(k, k);
if (!success){
    (iter -> second).g(k);
}

According to the manual it inserts in-place if the key does not exist, does nothing if the key exists.
std::map<Key,T,Compare,Allocator>::try_emplace

Make Map Key Sorted According To Insert Sequence

No. A std::map is a sorted container; the insertion order is not maintained. There are a number of solutions using a second container to maintain insertion order in response to another, related question.

That said, you should use std::string as your key. Using a const char* as a map key is A Bad Idea: it makes it near impossible to access or search for an element by its key because only the pointers will be compared, not the strings themselves.

---

Related Topics