C++ creating sorted vector from map

Question

I'm trying to create a sorted vector from a map, sorted according to a value that isn't the map's key. The map value is block object, and I want the vector to be sorted according to size, attribute of block.
My code:

#include <map>
#include <string>
#include <vector>

struct block {
    string data;
    int size;
};

struct vecotrCompare {
    bool operator()(pair<const string, block*> &left,
      pair<const string, block*> &right) {
        return left.second -> size < right.second -> size;
    }
};

int main() {
    map<const string, block*> myMap;
    vector<pair<const string, block*> > myVector(
      myMap.begin(), myMap.end());
    sort(myVector.begin(), myVector.end(), vecotrCompare());
}

The sort(...) line can't compile, and I'm getting a compile-error:

error: no match for call to ‘(vecotrCompare) (std::pair<const
  std::basic_string<char>, block*>&, const std::pair<const
  std::basic_string<char>, block*>&)’

required from here is only part of the error, and the most useless part at that. — chris
Anyway, you can't have non-copyable objects (like a pair of a const something) in a vector. It's redundant in the map, and won't work outside of that. — chris
Good job! You've completely changed the error and the reason you're seeing it by getting rid of the const& from vecotrCompare::operator()'s arguments. Add the const& back in, and you'll run into the next error, which I've explained in my answer. — Praetorian

Praetorian Praetorian · Accepted Answer · 2014-06-06T00:17:01

Elements in a vector need to be MoveAssignable or CopyAssignable. A pair<const string, block*> is neither due to the const string. Change that to string and your code compiles.

map<string, block*> myMap;
vector<pair<string, block*> > myVector(myMap.begin(), myMap.end());

Also change your comparator so that the argument types are const&

struct vecotrCompare {
    bool operator()(pair< string, block*> const&left, 
                    pair< string, block*> const&right) const {
        return left.second -> size < right.second -> size;
    }
};

Live demo

The second part about the arguments needing to be const& is actually not a requirement. From §25.1/9

The BinaryPredicate parameter is used whenever an algorithm expects a function object that when applied to the result of dereferencing two corresponding iterators or to dereferencing an iterator and type T when T is part of the signature returns a value testable as true. In other words, if an algorithm takes BinaryPredicate binary_pred as its argument and first1 and first2 as its iterator arguments, it should work correctly in the construct binary_pred(*first1, *first2) contextually converted to bool (Clause 4). BinaryPredicate always takes the first iterator’s value_type as its first argument, that is, in those cases when T value is part of the signature, it should work correctly in the construct binary_pred(*first1, value) contextually converted to bool (Clause 4). binary_pred shall not apply any non-constant function through the dereferenced iterators.

So the standard never mentions that the functor's argument types must be const&, but libstdc++ seems to be passing temporaries to the functor and the code doesn't compile unless you add the const& (looks like this has been fixed in gcc-4.9).

On the other hand, both libc++ and VS2013 handle the case where the arguments are not const& correctly.

C++ creating sorted vector from map

2 Answers