C++: Alternative to std::map when all entries guaranteed to be unique

user_3834415 0
Viewed 147

I have a simple use case: parsing a header. I have to parse very many of these headers, and I am guaranteed to have a header which does not repeat any fields.

As I parse these headers, I organize them in a std::map, 

// pseudo code
std::map<std::string,std::string> x;
x[key] = value;

// etc.

I have streamlined my code, and the single slowest point is the map insertion for these headers. Specifically, the std::_Rb_tree_iterator interior method called when inserting items into the map. Benchmarking with gprof indicates that this single method, when called only during the read-in of these headers (and not during any other operations that may insert or remove items from the map) takes approx. 50% of my runtime.

The question amounts to: supposing I can guarantee the uniqueness of all entries to the map, is there a way for me to disable the std::_Rb_tree_iterator for streamlined map insertion?

I would prefer to run the slow code than use something other than std::map, unless the replacement has an equivalent api (i.e., the iterators yield a std::pair<std::string,std::string>).

std c++
1 Answers

std::map inserts are slow because it tries to balance a binary search tree. Use std::unordered_map to use a hash table; while it will not keep the elements sorted, it will be a lot faster to insert elements, and it's highly recommended if you don't need the elements sorted.

Also, try inserting using insert calls; [] will first create an empty element, then write your own element over it.

user_14005480
Related