Effective STL Item 24: add_or_update for std::map with perfect forwarding and emplace

Question

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

Answer 1

You're correct that using perfect forwarding and emplace will produce more efficient results than not using them, so I won't even try to review the versions of your code that don't use them. Let's look at this most efficient one:

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));
  }
}

I see more than one std::forward<X>(x) of the same x — that's a red flag, because often the reason we're forwarding x is so that someone else can move its guts out, at which point any further use of the moved-from x could trigger unintended behavior. Let's take a closer look.

The two appearances of std::forward<ValT>(v) are okay, because they're on separate (disjoint) codepaths.

The three appearances of std::forward<KeyT>(k) are scary. Let's see... the first appearance is the argument to m.lower_bound(), which always takes its argument by const&, so there's no bug there — but the use of std::forward is redundant and thus a bad idea. The second appearance is as an argument to m.key_comp()(), which means you're forwarding k to a user-defined comparator. This could definitely trash the value of k, depending on the user-defined comparator's code. I can't think of any really plausible argument-trashing comparator, but just for the proof of concept:

struct Comp {
    bool operator()(std::string a, std::string b) const { return a < b; }
};

[wandbox link].

We can fix this easily by simply not perfect-forwarding the expressions that we don't want to be subject to perfect forwarding.

---

Incidentally, the return type (typename MapT::iterator) is needlessly verbose and constrained, as of C++14. In C++14 and later, you should write simply auto, unless you have a technical reason not to. In this case, the technical reason would be "I want to make sure that pf_emplace_add_or_update does not participate in overload resolution unless MapT has a member typename iterator" (because the explicitly specified return type participates in SFINAE, whereas auto would not). Since I'm pretty sure you don't have that technical reason in mind, you should not specify the return type.

---

Debatable style nits:

• Most C++11-and-later coding styles prefer T& x over T &x. (Yes, even if they prefer T *x over T* x.) Plus, personally, I find T& x easier to read.
• Two-space indents strike me as masochistic.
• You've got some excess parentheses there.

---

Putting it all together:

template <typename MapT, typename KeyT, typename ValT>
auto pf_emplace_add_or_update(MapT& m, KeyT&& k, ValT&& v)
{
    auto lb = m.lower_bound(k);
    if (lb != m.end() && !m.key_comp()(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));
    }
}

---

As of C++17, you can use insert_or_assign like this:

template <typename MapT, typename KeyT, typename ValT>
auto pf_emplace_add_or_update(MapT& m, KeyT&& k, ValT&& v)
{
    return m.insert_or_assign(std::forward<KeyT>(k), std::forward<ValT>(v)).first;
}