A std::map that keep track of the order of insertion?

If you have only 50 values in std::map you could copy them to std::vector before printing out and sort via std::sort using appropriate functor.

Or you could use boost::multi_index. It allows to use several indexes. In your case it could look like the following:

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;

You might combine a std::vector with a std::tr1::unordered_map (a hash table). Here's a link to Boost's documentation for unordered_map. You can use the vector to keep track of the insertion order and the hash table to do the frequent lookups. If you're doing hundreds of thousands of lookups, the difference between O(log n) lookup for std::map and O(1) for a hash table might 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';
}

If you need both lookup strategies, you will end up with two containers. You may use a vector with your actual values (ints), and put a map< string, vector< T >::difference_type> next to it, returning the index into the vector.

To complete all that, you may encapsulate both in one class.

But I believe boost has a container with multiple indices.

You cannot do that with a map, but you could use two separate structures - the map and the vector and keep them synchronized - that is when you delete from the map, find and delete the element from the vector. Or you could create a map<string, pair<int,int>> - and in your pair store the size() of the map upon insertion to record position, along with the value of the int, and then when you print, use the position member to sort.

Another way to implement this is with a map instead of a 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_;
};

You can then expose an iterator to iterator over data_ in the proper order. The way you do that is iterate through insertion_order_, and for each element you get from that iteration, do a lookup in the data_ with the value from insertion_order_

You can use the more efficient hash_map for insertion_order since you don't care about directly iterating through insertion_order_.

To do inserts, you can 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 a lot of ways you can make the design better and worry about performance, but this is a good skeleton to get you started on implementing this functionality on your own. You can make it templated, and you might actually store pairs as values in data_ so that you can easily reference the entry in insertion_order_. But I leave these design issues as an exercise :-).

Update: I suppose I should say something about efficiency of using map vs. vector for insertion_order_

• lookups directly into data, in both cases are O(1)
• inserts in the vector approach are O(1), inserts in the map approach are O(logn)
• deletes in the vector approach are O(n) because you have to scan for the item to remove. With the map approach they are O(logn).

Maybe if you are not going to use deletes as much, you should use the vector approach. The map approach would be better if you were supporting a different ordering (like priority) instead of insertion order.

This is somewhat related to Faisals answer. You can just create a wrapper class around a map and vector and easily keep them synchronized. Proper encapsulation will let you control the access method and hence which container to use... the vector or the map. This avoids using Boost or anything like that.

One thing you need to consider is the small number of data elements you are using. It is possible that it will be faster to use just the vector. There is some overhead in the map that can cause it to be more expensive to do lookups in small data sets than the simpler vector. So, if you know that you will always be using around the same number of elements, do some benchmarking and see if the performance of the map and vector is what you really think it is. You may find the lookup in a vector with only 50 elements is near the same as the map.

There is no need to use a separate std::vector or any other container for keeping track of the insertion order. You can do what you want as shown below. If you want to keep the insertion order then you can use the following program(version 1):

Version 1: For counting unique strings using std::map<std::string,int> in insertion order

#include <iostream>
#include <map>
#include <sstream>
int findExactMatchIndex(const std::string &totalString, const std::string &toBeSearched)
{
    std::istringstream ss(totalString);
    std::string word;
    std::size_t index = 0;
    while(ss >> word)
    {
        if(word == toBeSearched)
        {
            return index;
        }
        ++index;
    }
    return -1;//return -1 when the string to be searched is not inside the inputString
}
int main() {
    std::string inputString = "this is a string containing my name again and again and again ", word;
   
   //this map maps the std::string to their respective count
    std::map<std::string, int> wordCount;
    
    std::istringstream ss(inputString);
    
    while(ss >> word)
    {
        //std::cout<<"word:"<<word<<std::endl;
    wordCount[word]++;
    }      
  
    std::cout<<"Total unique words are: "<<wordCount.size()<<std::endl;
    
    std::size_t i = 0;
    
    std::istringstream gothroughStream(inputString);
    
    //just go through the inputString(stream) instead of map
    while( gothroughStream >> word)
    {
        int index = findExactMatchIndex(inputString, word);
        
        
        if(index != -1 && (index == i)){
         std::cout << word <<"-" << wordCount.at(word)<<std::endl;
         
        }
        ++i;
    }
   
    return 0;
}

The output of the above program is as follows:

Total unique words are: 9
this-1
is-1
a-1
string-1
containing-1
my-1
name-1
again-3
and-2

Note that in the above program, if you have a comma or any other delimiter then it is counted as a separate word. So for example lets say you have the string this is, my name is then the string is, has count of 1 and the string is has count of 1. That is is, and is are different. This is because the computer doesn't know our definition of a word.

Note

The above program is a modification of my answer to How do i make the char in an array output in order in this nested for loop? which is given as version 2 below:

Version 2: For counting unique characters using std::map<char, int> in insertion order

#include <iostream>
#include <map>
int main() {
    std::string inputString;
    std::cout<<"Enter a string: ";
    std::getline(std::cin,inputString);
    //this map maps the char to their respective count
    std::map<char, int> charCount;
    
    for(char &c: inputString)
    {
        charCount[c]++;
    }
    
    std::size_t i = 0;
    //just go through the inputString instead of map
    for(char &c: inputString)
    {
        std::size_t index = inputString.find(c);
        if(index != inputString.npos && (index == i)){
         std::cout << c <<"-" << charCount.at(c)<<std::endl;
         
        }
        ++i;
    }
    return 0;
}

In both cases/versions there is no need to use a separate std::vector or any other container to keep track of the insertion order.