3
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ @Incomputable I have to say; so what. \$\endgroup\$ Nov 28, 2016 at 8:49
  • \$\begingroup\$ @kyuan: If you forward something, and it matches a function whose parameter is an rvalue reference then the value is gone. You can't re-use that value safely. In m.lower_bound(std::forward<KeyT>(k)) the value of k after this point must be considered "unknown" (as you potentially just moved it). \$\endgroup\$ Nov 28, 2016 at 8:53
  • \$\begingroup\$ @Incomputable: So what. That will always be true. Just because you don't currently understand the worth of a book does not mean you can trash it without a response. Feel free to trash it. I will feel free to comment on the usefulness of your comments. \$\endgroup\$ Nov 28, 2016 at 16:59

1 Answer 1

2
\$\begingroup\$

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;
}
\$\endgroup\$
6
  • \$\begingroup\$ Thanks so much, I was so caught up on forwarding the right valueness but forgot that the internals can be gutted out. And thanks for pointing out the new library member call in c++17, looks like my concerns have already been heard by the committee. Couldn't be more useful! \$\endgroup\$
    – kyuan
    Nov 27, 2016 at 19:53
  • \$\begingroup\$ It just occurred to me that for 'insert_or_assign', the ValT is forwarded on update. Doesn't this essentially force us to create a temporary ValT, instead, if I wanted to edit a member variable of ValT, it would've been better to say 'lb->second.member = std::move(v);' ? Saving us a move construct. \$\endgroup\$
    – kyuan
    Nov 27, 2016 at 22:41
  • \$\begingroup\$ @kyuan: I doubt I understand that comment. If you might want to mutate lb->second instead of assigning to it, then yeah, insert_or_assign/pf_emplace_add_or_update won't do what you want. You could write a pf_emplace_or_mutate that accepted (MapT&, KeyT&&, MutatorLambda&&, EmplacementArgs&&...)... but at some point doesn't it get simpler to just write the lower_bound / if / emplace_hint directly inline and not use any helper function at all? :) \$\endgroup\$ Nov 28, 2016 at 5:24
  • \$\begingroup\$ which always takes its argument by. In this case and in this version of the library. This is still a huge red flag. No matter how unlikely we think something is now and then it will happen. Thus this code is likely to break down the road when the library is updated. \$\endgroup\$ Nov 28, 2016 at 8:57
  • \$\begingroup\$ @Quuxplusone, what you said is consistent with what I was thinking, if we wanted to mutate a member of ValT. The update_or_assign doesn't provide the exact call. Ya, at that point, the extra Lambda and EmplacementArg just gets verbose. But good to know I was on the right track! \$\endgroup\$
    – kyuan
    Nov 28, 2016 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.