CODEWITHSUNDEEP
c++memory-managementreferenceunordered-map
Rubens
Rubens

Reputation: 14768

Avoid extra process in unordered_map insertion

I have an std::unordered_map, and I want both to increment the first value in a std::pair, hashed by key, and to create a reference to key. For example:

std::unordered_map<int, std::pair<int, int> > hash;
hash[key].first++;

auto it(hash.find(key));
int& my_ref(it->first);

I could, instead of using the [] operator, insert the data with insert(), but I'd allocate a pair, even if it were to be deallocated later, as hash may already have key -- not sure of it, though. Making it clearer:

// If "key" is already inserted, the pair(s) will be allocated
// and then deallocated, right?
auto it(hash.insert(std::make_pair(key, std::make_pair(0, 0))));
it->second.first++;

// Here I can have my reference, with extra memory operations,
// but without an extra search in `hash`
int& my_ref(it->first);

I'm pretty much inclined to use the first option, but I can't seem to decide which one is the best. Any better solution to this?

P.S.: an ideal solution for me would be something like an insertion that does not require an initial, possibly useless, allocation of the value.

Upvotes: 4

Views: 1261

Answers (3)

FredericS
FredericS

Reputation: 413

If I understand correctly, what you want is an operator[] that returns an iterator, not a mapped_type. The current interface of unordered_map does not provide such feature, and operator[] implementation relies on private members (at least the boost implementation, I don't have access C++11 std files in my environment).

I suppose that JoergB's answer will be faster and Kerrek SB's one will have a smaller memory footprint. It's up to you to decide what is more critical for your project.

Upvotes: 1

JoergB
JoergB

Reputation: 4443

As others have pointed out, a "allocating" a std::pair<int,int> is really nothing more than copying two integers (on the stack). For the map<int,pair<int,int>>::value_type, which is pair<int const, pair<int, int>> you are at three ints, so there is no significant overhead in using your second approach. You can slightly optimize by using emplace instead of insert i.e.:

// Here an `int` and a struct containing two `int`s are passed as arguments (by value)
auto it(hash.emplace(key, std::make_pair(0, 0)).first);
it->second.first++;

// You get your reference, without an extra search in `hash`
// Not sure what "extra memory operations" you worry about
int const& my_ref(it->first);

Your first approach, using both hash[key] and hash.find(key) is bound to be more expensive, because an element search will certainly be more expensive than an iterator dereference.

Premature copying of arguments on their way to construction of the unordered_map<...>::value_type is a negligible problem, when all arguments are just ints. But if instead you have a heavyweight key_type or a pair of heavyweight types as mapped_type, you can use the following variant of the above to forward everything by reference as far as possible (and use move semantics for rvalues):

// Here key and arguments to construct mapped_type 
// are forwarded as tuples of universal references
// There is no copying of key or value nor construction of a pair 
// unless a new map element is needed.
auto it(hash.emplace(std::piecewise_construct, 
                        std::forward_as_tuple(key), // one-element tuple
                        std::forward_as_tuple(0, 0) // args to construct mapped_type
                     ).first);
it->second.first++;

// As in all solutions, get your reference from the iterator we already have
int const& my_ref(it->first);

Upvotes: 4

Kerrek SB
Kerrek SB

Reputation: 477010

How about this:

auto it = hash.find(key);

if (it == hash.end()) { it = hash.emplace(key, std::make_pair(0, 0)).first; }

++it->second.first;

int const & my_ref = it->first;   // must be const

(If it were an ordered map, you'd use lower_bound and hinted insertion to re­cycle the tree walk.)

Upvotes: 1

Related Questions