Std :: map that track insertion order?

Question

Currently, I have std::map<std::string,int> that stores an integer value for a unique string identifier, and I am viewing the line. This is basically what I want, except that it does not track the insertion order. So when I repeat the map to print the values, they are sorted according to the line; but I want them to be sorted according to the order of the (first) insert.

I thought about using vector<pair<string,int>> instead, but I need to look for the string and increase the numerical values ​​around 10,000,000 times, so I don’t know if the vector will be much slower.

Is there a way to use std :: map or is there another std container that works best for me?

[I am on GCC 3.4, and I probably have no more than 50 pairs of values ​​on my std :: map].

Answer 1

If you have only 50 values ​​on std :: map, you can copy them to std :: vector before printing and sort through std :: sort using the corresponding functor.

Or you can use boost :: multi_index . It allows you to use multiple indexes. In your case, it might look like this:

 struct value_t { string s; int i; }; struct string_tag {}; typedef multi_index_container< value_t, indexed_by< random_access<>, // this index represents insertion order hashed_unique< tag<string_tag>, member<value_t, string, &value_t::s> > > > values_t; 

Answer 2

You can combine std::vector with std::tr1::unordered_map (hash table). Here's a link to the Boost documentation for unordered_map . You can use the vector to track the insertion order and hash table for frequent searches. If you do hundreds of thousands of searches, the difference between O (log n) searches for std::map and O (1) for the hash table can be significant.

 std::vector<std::string> insertOrder; std::tr1::unordered_map<std::string, long> myTable; // Initialize the hash table and record insert order. myTable["foo"] = 0; insertOrder.push_back("foo"); myTable["bar"] = 0; insertOrder.push_back("bar"); myTable["baz"] = 0; insertOrder.push_back("baz"); /* Increment things in myTable 100000 times */ // Print the final results. for (int i = 0; i < insertOrder.size(); ++i) { const std::string &s = insertOrder[i]; std::cout << s << ' ' << myTable[s] << '\n'; } 

Answer 3

Store parallel list<string> insertionOrder .

When it's time to print, iterate over the list and search on the map.

 each element in insertionOrder // walks in insertionOrder.. print map[ element ].second // but lookup is in map 

Answer 4

If you need both search strategies, you will have two containers. You can use vector with your actual values ​​( int s) and place map< string, vector< T >::difference_type> next to it, returning the index to the vector.

To complete all this, you can encapsulate both in the same class.

But I believe boost has a container with multiple indexes.

Answer 5

Tessil has a very nice incarnation of an ordered map (and set), which is a MIT license. You can find it here: ordered-map

Map example

 #include <iostream> #include <string> #include <cstdlib> #include "ordered_map.h" int main() { tsl::ordered_map<char, int> map = {{'d', 1}, {'a', 2}, {'g', 3}}; map.insert({'b', 4}); map['h'] = 5; map['e'] = 6; map.erase('a'); // {d, 1} {g, 3} {b, 4} {h, 5} {e, 6} for(const auto& key_value : map) { std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl; } map.unordered_erase('b'); // Break order: {d, 1} {g, 3} {e, 6} {h, 5} for(const auto& key_value : map) { std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl; } } 

Answer 6

You cannot do this with a map, but you can use two separate structures - a map and a vector and synchronize them, that is, when you delete from the map, find and delete an element from the vector. Or you can create map<string, pair<int,int>> - and in your pair save the size () of the map when pasting at the record position along with the int value, and then when you print, use the position element to sort.

Answer 7

This is somewhat related to Faisals answer. You can simply create a wrapper class around the map and the vector and easily synchronize them. Proper encapsulation will allow you to control the access method and therefore which container to use ... a vector or map. This avoids the use of Boost or anything like that.

Answer 8

Another way to implement this is map instead of vector . I will show you this approach and discuss the differences:

Just create a class that has two maps behind the scenes.

 #include <map> #include <string> using namespace std; class SpecialMap { // usual stuff... private: int counter_; map<int, string> insertion_order_; map<string, int> data_; }; 

Then you can set the iterator for the iterator over data_ in the correct order. How do you do this, iterate through insertion_order_ , and for each element that you get from this iteration, do a search in data_ with a value from insertion_order_

You can use the more efficient hash_map for insertion_order, since you do not need to iterate directly through insertion_order_ .

To make inserts, you might have a method like this:

 void SpecialMap::Insert(const string& key, int value) { // This may be an over simplification... You ought to check // if you are overwriting a value in data_ so that you can update // insertion_order_ accordingly insertion_order_[counter_++] = key; data_[key] = value; } 

There are many ways to improve design and worry about performance, but this is a good skeleton to get you started using this functionality yourself. You can make it a template, and you can actually store the pairs as values ​​in data_, so that you can easily reference the entry in insertion_order_. But I leave these design problems as an exercise :-).

Update . I suppose I have to say something about the efficiency of using map vs. vector for insertion_order _

• search directly in data, in both cases O (1)
• The insertion in the vector approach is O (1), the insertion in the approach to the map is O (logn)
• deletes O (n) in the vector approach because you need to scan the item for deletion. Using the map approach, they are equal to O (logn).

Perhaps if you are not going to use the removal as much, you should use a vector approach. A card-based approach would be better if you maintained a different order (for example, priority) instead of the placement order.

Answer 9

// There must be such a person!

// This supports the complexity of inserting O (logN), and deleting also O (logN).

 class SpecialMap { private: int counter_; map<int, string> insertion_order_; map<string, int> insertion_order_reverse_look_up; // <- for fast delete map<string, Data> data_; }; 

Answer 10

Here is a solution that only requires a standard template library without using boost multiindex:
You can use std::map<std::string,int>; and vector <data>; where on the map you store the data location index in vector and vector data warehouses in the order of placement. Here, access to data is O (log n) complexity. displaying data in input order has complexity O (n). data insertion has complexity O (log n).

Example:

 #include<iostream> #include<map> #include<vector> struct data{ int value; std::string s; } typedef std::map<std::string,int> MapIndex;//this map stores the index of data stored //in VectorData mapped to a string typedef std::vector<data> VectorData;//stores the data in insertion order void display_data_according_insertion_order(VectorData vectorData){ for(std::vector<data>::iterator it=vectorData.begin();it!=vectorData.end();it++){ std::cout<<it->value<<it->s<<std::endl; } } int lookup_string(std::string s,MapIndex mapIndex){ std::MapIndex::iterator pt=mapIndex.find(s) if (pt!=mapIndex.end())return it->second; else return -1;//it signifies that key does not exist in map } int insert_value(data d,mapIndex,vectorData){ if(mapIndex.find(ds)==mapIndex.end()){ mapIndex.insert(std::make_pair(ds,vectorData.size()));//as the data is to be //inserted at back //therefore index is //size of vector before //insertion vectorData.push_back(d); return 1; } else return 0;//it signifies that insertion of data is failed due to the presence //string in the map and map stores unique keys } 

Answer 11

What you want (without resorting to Boost) is what I call an "ordered hash", which is essentially a hash of the hash and a linked list with string or integer keys (or both at the same time). An ordered hash preserves the order of elements during iteration with absolute hash performance.

I have put together a relatively new C ++ snippet library that fills what I see as C ++ holes for C ++ library developers. Go here:

https://github.com/cubiclesoft/cross-platform-cpp

Grab:

 templates/detachable_ordered_hash.cpp templates/detachable_ordered_hash.h templates/detachable_ordered_hash_util.h 

If user-driven data is put into a hash, you might also need:

 security/security_csprng.cpp security/security_csprng.h 

Call it:

 #include "templates/detachable_ordered_hash.h" ... // The 47 is the nearest prime to a power of two // that is close to your data size. // // If your brain hurts, just use the lookup table // in 'detachable_ordered_hash.cpp'. // // If you don't care about some minimal memory thrashing, // just use a value of 3. It'll auto-resize itself. int y; CubicleSoft::OrderedHash<int> TempHash(47); // If you need a secure hash (many hashes are vulnerable // to DoS attacks), pass in two randomly selected 64-bit // integer keys. Construct with CSPRNG. // CubicleSoft::OrderedHash<int> TempHash(47, Key1, Key2); CubicleSoft::OrderedHashNode<int> *Node; ... // Push() for string keys takes a pointer to the string, // its length, and the value to store. The new node is // pushed onto the end of the linked list and wherever it // goes in the hash. y = 80; TempHash.Push("key1", 5, y++); TempHash.Push("key22", 6, y++); TempHash.Push("key3", 5, y++); // Adding an integer key into the same hash just for kicks. TempHash.Push(12345, y++); ... // Finding a node and modifying its value. Node = TempHash.Find("key1", 5); Node->Value = y++; ... Node = TempHash.FirstList(); while (Node != NULL) { if (Node->GetStrKey()) printf("%s => %d\n", Node->GetStrKey(), Node->Value); else printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value); Node = Node->NextList(); } 

I came across this SO thread during my research phase to see if something like OrderedHash exists, without requiring me to fall into a massive library. I was disappointed. So I wrote my own. And now I shared it.

Answer 12

One thing you need to consider is the small number of data items that you use. It is possible that only the vector will be faster. There are some overheads on the map that can lead to a more expensive search in small data sets than a simpler vector. So, if you know that you will always use around the same number of elements, do some benchmarking and see if the performance of the map and vector is really what you really think. You may find that a search in a vector with 50 elements almost matches the map.

Answer 13

Use boost::multi_index with map and list indices.

Answer 14

A map of a pair (str, int) and a static int, which increases the index calls of the data pair when inserted. Put in a structure that can return a static int val with an index () element, perhaps?