How to compare two std::maps with std::weak_ptr as key?

Question

I have a code like this:

#include <memory>
#include <map>

struct element {
  std::map<std::weak_ptr<int>, int> weights;
  bool operator<(const element &a) const { return this->weights < a.weights; }
};

int main() { return 0; }

I'd like to compare two instances of this class, however I get compiler errors:

/usr/include/c++/4.8/bits/stl_pair.h: In instantiation of ‘constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&) [with _T1 = const std::weak_ptr<int>; _T2 = int]’:
/usr/include/c++/4.8/bits/stl_pair.h:221:24: error: no match for ‘operator<’ (operand types are ‘const std::weak_ptr<int>’ and ‘const std::weak_ptr<int>’)
     { return __x.first < __y.first
/usr/include/c++/4.8/bits/stl_pair.h:222:23: error: no match for ‘operator<’ (operand types are ‘const std::weak_ptr<int>’ and ‘const std::weak_ptr<int>’)
       || (!(__y.first < __x.first) && __x.second < __y.second); }
/usr/include/c++/4.8/bits/stl_pair.h:222:65: error: body of constexpr function ‘constexpr bool std::operator<(const std::pair<_T1, _T2>&, const std::pair<_T1, _T2>&) [with _T1 = const std::weak_ptr<int>; _T2 = int]’ not a return-statement
       || (!(__y.first < __x.first) && __x.second < __y.second); }

Seeing no match for operator, I added the following code, but it didn't help.

// from boost::weak_ptr
template<typename T, typename U>
bool operator<(const std::weak_ptr<T> &a, const std::weak_ptr<U> &b)
{
  return a.owner_before(b);
}

The errors were still present when I tried the following:

• Adding constexpr to any of this operator;
• Add a custom comparator to the map like this: std::map<std::weak_ptr<int>, int, std::owner_less<std::weak_ptr<int>>>.

I can make this code compile by:

1. Replacing the operator return statements with: return true;
2. Changing the type of the weights member to not use std::weak_ptr, e.g. to std::map<int, int>;
3. Adding a custom comparison operator to class element that does not compare the maps, but compares every key and value.

Options 1. and 2. are just to test and not an option; 3. would be possible, but I would like to understand why I get this error and use the standard library if possible. In my understanding it should compile: std::map has an operator<, which compares the internal tree, which should compare the pairs<key, data>, which compares first and second elements in the pair which should work at least if an operator< for weak_ptr is provided.

But it does not work (at least not with g++ 4.8.{1,2}), hence my questions:

• Why does it not work and why do I get this error message?
• How can I compare two maps with weak_ptr as key?

Update, using std::lexicographical_compare as suggested by KerrekSB.

I am trying to compare two different maps. In the example below both maps m1 and m2 have the same key, but store a different value with this key. If these two maps are compared, they should not be equal, one should sort before the other.

#include <memory>
#include <map>
#include <iostream>

typedef std::owner_less<std::weak_ptr<int>> wp_less;
typedef std::map<std::weak_ptr<int>, int, wp_less> wp_map;
bool map_cmp(const wp_map &a, const wp_map &b)
{
  return std::lexicographical_compare(
    a.begin(), a.end(),
    b.begin(), b.end(),
    []( std::pair<std::weak_ptr<int> const, int> const & p, 
        std::pair<std::weak_ptr<int> const, int> const & q) -> bool 
      { return wp_less()(p.first, q.first); });
      //{ return wp_less()(p.first, q.first) 
      //    || ( ! (wp_less()(q.first, p.first)) && p.second < q.second); });
}

int main() 
{
  std::shared_ptr<int> sp_int(std::make_shared<int>(5));
  std::weak_ptr<int> wp_int(sp_int);
  wp_map m1, m2;
  m1[wp_int] = 1;
  m2[wp_int] = 2;
  std::cout << "m1 < m2=" << map_cmp(m1, m2) << "\nm2 < m1=" << map_cmp(m2, m1);
  return 0; 
}

The output as shown is suggesting both are equal:

m1 < m2=0
m2 < m1=0

But they are not, and by using the commented comparison, the result becomes:

m1 < m2=1
m2 < m1=0

So this leaves me with:

• What do I have to do to make the default lexicographical compare do what I want for comparing these pairs?
• And from the original part of the question, why do I get this error, in particular what causes the constexpr error?

Answer 1

Don't use the naked <, but instead use the std::lexicographical_compare algorithm, which you can supply with a custom predicate such as std::owner_less.

The naked < operator uses the default version of lexicographical compare with std::less predicate, which does not work well for weak pointers.

---

It's a bit of a mouthful, so let me spell out an example for you:

std::map<std::weak_ptr<int>, int, std::owner_less<std::weak_ptr<int>>> a, b;

return std::lexicographical_compare(
    a.begin(), a.end(),
    b.begin(), b.end(),
    [](std::pair<std::weak_ptr<int> const, int> const & p,
       std::pair<std::weak_ptr<int> const, int> const & q)
    -> bool { return std::owner_less<std::weak_ptr<int>>()(p.first, q.first); });

In this example, the expression a < b is identical to:

std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end())

This doesn't work, since this would attempt to compare pairs, which in turn would try to compare weak pointers with std::less<std::weak_ptr<int>>(). (The problem is of course that the algorithm uses iterators and isn't aware of the comparator object in the respective containers. In general, there's no reason why two maps with the same value type should even use the same comparator at all.)

You could write something similar in terms of owner_before if you wanted. The beauty of std::owner_less is that it compares both weak and shared pointers in the same wash.