std::map::try_emplace() seems very convenient and efficient but it's only available in C++17. Is it possible to re-implement it in C++11?
template <class... Args> pair<iterator, bool> try_emplace(const key_type& k, Args&&... args); 
- You can express the same effect in C++11 using only the public interface, but potentially not as efficiently. Otherwise you need to modify your standard library implementation.Kerrek SB– Kerrek SB2015-12-20 14:37:50 +00:00Commented Dec 20, 2015 at 14:37
Add a comment |
2 Answers
For an ordered map, you can get close to the behaviour with lower_bound:
template <class M, class... Args> std::pair<typename M::iterator, bool> try_emplace_m(M& m, const typename M::key_type& k, Args&&... args) { auto it = m.lower_bound(k); if (it == m.end() || m.key_comp()(k, it->first)) { return {m.emplace_hint( it, std::piecewise_construct, std::forward_as_tuple(k), std::forward_as_tuple(std::forward<Args>(args)...)), true}; } return {it, false}; } For an unordered map, you can't use lower_bound. You can replace it with find, and the test with key_eq(), to get a functional version, which will perform a repeated lookup in the case of an insertion, though. Sp speaking purely in terms of algorithmic complexity this new member function pulls more weight in the unordered case, which users cannot currently implement using only the public API. But the added convenience applies equally to both cases.
5 Comments
Kerrek SB
(The code I showed is actually very similar to libc++'s current implementation for C++17. In principle, implementers could provide this function at a lower level where you wouldn't need to repeat the key comparison.)
Pol
Thanks! Why do you say "close to the behaviour"? What would be different with the C++17 native version?
Pol
Ah, you preemptively answered my follow-up while I was typing it!
Kerrek SB
@Pol: Yes, if the key comparison would for some reason be really expensive (think very long, nearly equal strings?), then it might be worth working harder to avoid the second key comparison. The
lower_bound operation is already comparing keys.
FrankHB
This does not implement
try_emplace with hint for map. Current libc++ ignores user-provided hint. OTOH libstdc++ implement it by replacing lower_bound with internal interface. I have written some related interface to ease such. It is named search_map here, but can be also used on other custom associative containers. I have implemented (more compact than the internal impl in libstdc++) but haven't release the overloading with hint parameter. I will commit it days (less than a week) later hopefully.Hmmm... Simply search for the value before?
auto it = map.find(k); if (it == map.end()){ //value does not exist auto newIt = map.emplace({std::move(k),std::forward<Args>(args)...}); } 
2 Comments
Pol
This is not exactly the same behavior as
try_emplace since it will still create an intermediary std::pair instead of truly constructing the element in place.