std::vector<std::pair<int,std::pair<Bone,std::string> > > not sorting by int?

I have a std::vector<std::pair<int,std::pair<Bone,std::string> > >

I'm trying to sort it with std sort, with the expectation that it is sorted by int, but instead I get 21 errors related to the sort call.

What could be wrong?

Code:

std::vector<std::pair<int,std::pair<Bone,std::string> > > tempBones;
std::sort(tempBones.begin(),tempBones.end());

Errors:

Error 1 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 2 error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 3 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 4 error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 5 error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 6 error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 7 error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 8 error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 9 error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 102

Error 10 error C2676: binary '<' : 'const skl::Bone' does not define this operator or a conversion to a type acceptable to the predefined operator c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 10

Error 11 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const _Elem *)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 12 error C2784: 'bool std::operator <(const _Elem *,const std::basic_string<_Ele开发者_开发百科m,_Traits,_Alloc> &)' : could not deduce template argument for 'const _Elem *' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 13 error C2784: 'bool std::operator <(const std::basic_string<_Elem,_Traits,_Alloc> &,const std::basic_string<_Elem,_Traits,_Alloc> &)' : could not deduce template argument for 'const std::basic_string<_Elem,_Traits,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 14 error C2784: 'bool std::operator <(const std::_Tree<_Traits> &,const std::_Tree<_Traits> &)' : could not deduce template argument for 'const std::_Tree<_Traits> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 15 error C2784: 'bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 16 error C2784: 'bool std::operator <(const std::list<_Ty,_Ax> &,const std::list<_Ty,_Ax> &)' : could not deduce template argument for 'const std::list<_Ty,_Ax> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 17 error C2784: 'bool std::operator <(const std::reverse_iterator<_RanIt> &,const std::reverse_iterator<_RanIt2> &)' : could not deduce template argument for 'const std::reverse_iterator<_RanIt> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 18 error C2784: 'bool std::operator <(const std::_Revranit<_RanIt,_Base> &,const std::_Revranit<_RanIt2,_Base2> &)' : could not deduce template argument for 'const std::_Revranit<_RanIt,_Base> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 19 error C2784: 'bool std::operator <(const std::pair<_Ty1,_Ty2> &,const std::pair<_Ty1,_Ty2> &)' : could not deduce template argument for 'const std::pair<_Ty1,_Ty2> &' from 'const skl::Bone' c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Error 20 error C2676: binary '<' : 'const skl::Bone' does not define this operator or a conversion to a type acceptable to the predefined operator c:\Program Files\Microsoft Visual Studio 9.0\VC\include\utility 103

Why would you expect it to be sorted by int? Any container<T> is sorted by T, and sorting requires that there be a less-than comparison for T. Now for pair<S,T>, there is an operator<, defined as lexicographic ordering, but this requires comparability of both S and T:

// lexicographic compare:
bool operator<(pair<S,T> a, pair<S,T> b)
{
  return a.first < b. first || (!(b.first < a.first) && (a.second < b.second));
  //                                                    ^^^^^^^^^^^^^^^^^^^^^^^
} //                                                     compare second type!

Moving down recursively, you need Bone to be less-than comparable. Do check, any bet that you didn't implement a comparison operator for that type!

Edit: According to your update that is precisely your problem.

Remark: You might wonder why lexicographic compare is the default: It's the only sensible comparison for which !(x < y) && !(y < x) is identical to x == y, provided the same holds for both sub-types individually.

Update: If you only want ordering by the first member, you should write a custom comparator predicate, or use a multi-map instead.

Custom comparator:

template <typename S, typename T>
bool PairCompareOnlyFirst(const std::pair<S,T> & a, const std::pair<S,T> & b)
{
  return a.first < b.first;
}

std::sort(v.begin(), v.end(), PairCompareOnlyFirst);

Note that sort may rearrange elements with the same key. If you want those to maintain their relative ordering, use stable_sort instead.

Multimap:

typedef std::multimap<int, std::pair<Bone,std::string> > myMapType;

The multimap is a more complicated structure than the vector, and its elements are always kept in sorted order by key value, i.e. your int. Which one is preferable depends on what you're doing.

Without seeing the error I can't be sure about this, but one thing to note is that std::pair does not just sort by the first value; it also uses the second value if needed to break ties. In the context of std::map this isn't an issue because internally the map uses a custom comparator instead of the default operator<, but if you sort pairs naturally the ordering may take the second element into account.

Because of this, if you didn't define operator< for Bone, you will get a compiler error because the template code for pair's operator< will try to use it. On top of that, you'd get some ferocious compiler errors about it, since the compiler will only report the error after instantiating the templates for sort and pair.

Hope this helps!