In Scott's Effective STL Item 24, his template function of "efficientAddorUpdate" does not take advantage of rvalue references.
I've tried implementing a modern equivalent with perfect forwarding and emplace, then various less efficient alternatives to compare. It seems that the pf with emplace is the most efficient implementation I can think of. I'd just like to know what everyone else thinks.
#include <iostream>
#include <map>
#include <utility>
// Modern adaptation of Effective STL's Item 24
// Know your map's operator[] and insert
template <typename MapT, typename KeyT, typename ValT>
typename MapT::iterator pf_emplace_add_or_update(MapT &m, KeyT &&k, ValT &&v) {
auto lb = m.lower_bound(std::forward<KeyT>(k));
// if key exists
if (lb != m.end() && !(m.key_comp()(std::forward<KeyT>(k), lb->first))) {
lb->second = std::forward<ValT>(v);
return lb;
} else {
return m.emplace_hint(
lb, std::forward<KeyT>(k), std::forward<ValT>(v));
}
}
template <typename MapT, typename KeyT, typename ValT>
typename MapT::iterator pf_add_or_update(MapT &m, KeyT &&k, ValT &&v) {
auto lb = m.lower_bound(std::forward<KeyT>(k));
// if key exists
if (lb != m.end() && !(m.key_comp()(std::forward<KeyT>(k), lb->first))) {
lb->second = std::forward<ValT>(v);
return lb;
} else {
return m.insert(
lb, typename MapT::value_type(std::forward<KeyT>(k), std::forward<ValT>(v)));
}
}
template <typename MapT, typename KeyT, typename ValT>
typename MapT::iterator rvalue_add_or_update(MapT &m, KeyT &&k, ValT &&v) {
auto lb = m.lower_bound(k);
// if key exists
if (lb != m.end() && !(m.key_comp()(k, lb->first))) {
lb->second = v;
return lb;
} else {
return m.insert(
lb, typename MapT::value_type(k, v));
}
}
template <typename MapT, typename KeyT, typename ValT>
typename MapT::iterator lvalue_add_or_update(MapT &m, KeyT const& k, ValT const& v) {
auto lb = m.lower_bound(k);
// if key exists
if (lb != m.end() && !(m.key_comp()(k, lb->first))) {
lb->second = v;
return lb;
} else {
return m.insert(
lb, typename MapT::value_type(k, v));
}
}
struct Dummy {
Dummy() {
std::cout << "Constructed" << std::endl;
}
Dummy& operator=(Dummy&&)
{
std::cout << "Move Assigned" << std::endl;
}
Dummy& operator=(Dummy const&) {
std::cout << "Const Ref Assigned" << std::endl;
}
Dummy(Dummy const&)
{
std::cout << "Copy Constructed" << std::endl;
}
Dummy(Dummy&&)
{
std::cout << "Move Constructed" << std::endl;
}
~Dummy()
{
std::cout << "Deleted" << std::endl;
}
};
int main ()
{
{
std::cout << "perfect forwarding with emplace add or update\n";
std::map<char, Dummy> mymap;
pf_emplace_add_or_update(mymap, 'b', Dummy());
}
{
std::cout << std::endl << "perfect forwarding add or update\n";
std::map<char, Dummy> mymap;
pf_add_or_update(mymap, 'b', Dummy());
}
{
std::cout << std::endl << "rvalue reference add or update\n";
std::map<char, Dummy> mymap;
rvalue_add_or_update(mymap, 'b', Dummy());
}
{
std::cout << std::endl << "const lvalue reference add or update\n";
std::map<char, Dummy> mymap;
lvalue_add_or_update(mymap, 'b', Dummy());
}
return 0;
}
Outputs:
perfect forwarding with emplace add or update Constructed Move Constructed Deleted Deleted perfect forwarding add or update Constructed Move Constructed Move Constructed Deleted Deleted Deleted rvalue reference add or update Constructed Copy Constructed Move Constructed Deleted Deleted Deleted const lvalue reference add or update Constructed Copy Constructed Move Constructed Deleted Deleted Deleted
m.lower_bound(std::forward<KeyT>(k))
the value ofk
after this point must be considered "unknown" (as you potentially just moved it). \$\endgroup\$