efficient way to insert a unique_ptr into a map without deleting the pointer if the key already exists

Question

The easy way is obviosuly

std::map<int,std::unique_ptr<something>> mymap;

auto f = mymap.find(5);
std::unique_ptr<something> myptr;

if (f == mymap.end())
    mymap.insert({5, std::move(myptr)});

However, this doesn't look too efficient, as I have to find the key in the map twice. One to check if the key doesn't exist, and the insert function will also do the same.

If I simply use mymap.insert({5, std::move(myptr)}); then my unique ptr (myptr) is gone if pair.second returns false (key already exists).

EDIT:

Apparently the answer is on C++17, with try_emplace, and it's already available in the compiler I'm using (vs2015) and since I'm working on a personal project, I can afford to use it.

If you are worried about the complexity of `std::map::find` then perhaps you are using the wrong container? `std::unordered_map` sits on top of a hashtable, making some operations O(1) amortized instead of O(log n) - find included. — Conduit, Jun 10 '16 at 19:14
Looks almost like you want the coming in the next standard [`try_emplace`](http://en.cppreference.com/w/cpp/container/map/try_emplace) — NathanOliver, Jun 10 '16 at 19:16
This looks like an [XY problem](http://xyproblem.info/): You ask us a question about a solution you have and want help fixing it, but you don't tell us the problem you are actually trying to solve. — Some programmer dude, Jun 10 '16 at 19:16
@NathanOliver Thanks for that, Before I created this question I was looking for a try_ function, but in the wrong place (cplusplus.com) — Gam, Jun 10 '16 at 19:32

Leon · Answer 1 · 2016-06-10T19:27:19.163

6

If you are not going to store nullptrs in your map then you can do it like this:

auto& r = mymap[5];
if ( r == nullptr )
    r = std::move(myptr);

edited Jun 10 '16 at 19:27

answered Jun 10 '16 at 19:24

Leon

31,443
4
72
97

1

That's a very interesting idea! – Gam Jun 10 '16 at 19:32

Joshua Green · Answer 2 · 2016-06-10T23:50:58.980

2

The standard trick is to search for the insertion point:

auto f = mymap.lower_bound(5);
if ((f == mymap.end()) || mymap.key_comp()(5, f->first)) {
    mymap.insert(f, {5, std::move(myptr)}); // or mymap.emplace_hint(f, 5, std::move(myptr))
}

edited Jun 10 '16 at 23:50

answered Jun 10 '16 at 23:29

Joshua Green

1,517
1
10
14

score 0 · Answer 3 · answered Jun 10 '16 at 20:20

0

Maybe I don't quite understand the context but why to move anything and not emplace it?

std::map<int,std::unique_ptr<something>> mymap;

auto f = mymap.find(5);

if (f == mymap.end()) 
    mymap.emplace(5, std::make_unique<something>(myptr));

answered Jun 10 '16 at 20:20

Jan Korous

666
4
11

1

This still does the lookup twice, just as the original OP snippet. – Ilya Popov Jun 10 '16 at 23:08

efficient way to insert a unique_ptr into a map without deleting the pointer if the key already exists

3 Answers3