Cython: std::sort on C++ vector

Question

I'm having trouble compiling using libcpp.algorithm.sort (std::sort) on my libcpp.vector. This is my short code below:

from libcpp.algorithm cimport sort as stdsort
from libcpp.vector cimport vector

cdef sort_something(mylist):
    myvec = vector[int]()
    for num in mylist: myvec.push_back(num)
    stdsort(myvec.begin(), myvec.end())

This is using the standard syntax for using std::sort on a C++ vector. I get some angry compiler messages. For reference, this is my setup.py file:

from distutils.core import setup
from Cython.Build import cythonize

setup(
    ext_modules=cythonize("*.pyx", language="c++")
)

This is the compiler output. (Warning: It's long, and I can't comprehend it.)

python setup.py build_ext --inplace
running build_ext
building 'sample' extension
cc -fno-strict-aliasing -fno-common -dynamic -arch x86_64 -arch i386 -g -Os -pipe -fno-common -fno-strict-aliasing -fwrapv -DENABLE_DTRACE -DMACOSX -DNDEBUG -Wall -Wstrict-prototypes -Wshorten-64-to-32 -DNDEBUG -g -fwrapv -Os -Wall -Wstrict-prototypes -DENABLE_DTRACE -arch x86_64 -arch i386 -pipe -I/System/Library/Frameworks/Python.framework/Versions/2.7/Extras/lib/python/numpy/core/include -I/System/Library/Frameworks/Python.framework/Versions/2.7/include/python2.7 -c sample.cpp -o build/temp.macosx-10.10-intel-2.7/sample.o
In file included from sample.cpp:257:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:702:71: error: invalid operands to binary expression ('const _object' and 'const _object')
    bool operator()(const _T1& __x, const _T1& __y) const {return __x < __y;}
                                                                  ~~~ ^ ~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3862:17: note: in instantiation of member function 'std::__1::__less<_object, _object>::operator()' requested here
            if (__comp(*--__last, *__first))
                ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4048:5: note: in instantiation of function template specialization 'std::__1::__sort<std::__1::__less<_object, _object> &, _object *>' requested here
    __sort<_Comp_ref>(__first, __last, __comp);
    ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4057:12: note: in instantiation of function template specialization 'std::__1::sort<_object *, std::__1::__less<_object, _object> >' requested here
    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
           ^
sample.cpp:855:8: note: in instantiation of function template specialization 'std::__1::sort<_object *>' requested here
  std::sort<PyObject *>(__pyx_t_2, __pyx_t_5);
       ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/utility:424:1: note: candidate template ignored: could not match 'pair<type-parameter-0-0, type-parameter-0-1>' against 'const _object'
operator< (const pair<_T1,_T2>& __x, const pair<_T1,_T2>& __y)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:592:1: note: candidate template ignored: could not match 'reverse_iterator<type-parameter-0-0>' against 'const _object'
operator<(const reverse_iterator<_Iter1>& __x, const reverse_iterator<_Iter2>& __y)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:996:1: note: candidate template ignored: could not match 'move_iterator<type-parameter-0-0>' against 'const _object'
operator<(const move_iterator<_Iter1>& __x, const move_iterator<_Iter2>& __y)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/iterator:1312:1: note: candidate template ignored: could not match '__wrap_iter<type-parameter-0-0>' against 'const _object'
operator<(const __wrap_iter<_Iter1>& __x, const __wrap_iter<_Iter2>& __y) _NOEXCEPT
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:2917:1: note: candidate template ignored: could not match 'unique_ptr<type-parameter-0-0, type-parameter-0-1>' against 'const _object'
operator< (const unique_ptr<_T1, _D1>& __x, const unique_ptr<_T2, _D2>& __y)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:2975:1: note: candidate template ignored: could not match 'unique_ptr<type-parameter-0-0, type-parameter-0-1>' against 'const _object'
operator<(const unique_ptr<_T1, _D1>& __x, nullptr_t)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:2984:1: note: candidate template ignored: could not match 'unique_ptr<type-parameter-0-0, type-parameter-0-1>' against 'const _object'
operator<(nullptr_t, const unique_ptr<_T1, _D1>& __x)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:4774:1: note: candidate template ignored: could not match 'shared_ptr<type-parameter-0-0>' against 'const _object'
operator<(const shared_ptr<_Tp>& __x, const shared_ptr<_Up>& __y) _NOEXCEPT
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:4839:1: note: candidate template ignored: could not match 'shared_ptr<type-parameter-0-0>' against 'const _object'
operator<(const shared_ptr<_Tp>& __x, nullptr_t) _NOEXCEPT
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/memory:4847:1: note: candidate template ignored: could not match 'shared_ptr<type-parameter-0-0>' against 'const _object'
operator<(nullptr_t, const shared_ptr<_Tp>& __x) _NOEXCEPT
^
In file included from sample.cpp:257:
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3649:20: error: no matching function for call to '__sort3'
    unsigned __r = __sort3<_Compare>(__x1, __x2, __x3, __c);
                   ^~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3869:20: note: in instantiation of function template specialization 'std::__1::__sort4<std::__1::__less<_object, _object> &, _object *>' requested here
            _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
                   ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4048:5: note: in instantiation of function template specialization 'std::__1::__sort<std::__1::__less<_object, _object> &, _object *>' requested here
    __sort<_Comp_ref>(__first, __last, __comp);
    ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4057:12: note: in instantiation of function template specialization 'std::__1::sort<_object *, std::__1::__less<_object, _object> >' requested here
    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
           ^
sample.cpp:855:8: note: in instantiation of function template specialization 'std::__1::sort<_object *>' requested here
  std::sort<PyObject *>(__pyx_t_2, __pyx_t_5);
       ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3609:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3675:20: error: no matching function for call to '__sort4'
    unsigned __r = __sort4<_Compare>(__x1, __x2, __x3, __x4, __c);
                   ^~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3872:20: note: in instantiation of function template specialization 'std::__1::__sort5<std::__1::__less<_object, _object> &, _object *>' requested here
            _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
                   ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4048:5: note: in instantiation of function template specialization 'std::__1::__sort<std::__1::__less<_object, _object> &, _object *>' requested here
    __sort<_Comp_ref>(__first, __last, __comp);
    ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4057:12: note: in instantiation of function template specialization 'std::__1::sort<_object *, std::__1::__less<_object, _object> >' requested here
    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
           ^
sample.cpp:855:8: note: in instantiation of function template specialization 'std::__1::sort<_object *>' requested here
  std::sort<PyObject *>(__pyx_t_2, __pyx_t_5);
       ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3646:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3740:5: error: no matching function for call to '__sort3'
    __sort3<_Compare>(__first, __first+1, __j, __comp);
    ^~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3877:20: note: in instantiation of function template specialization 'std::__1::__insertion_sort_3<std::__1::__less<_object, _object> &, _object *>' requested
      here
            _VSTD::__insertion_sort_3<_Compare>(__first, __last, __comp);
                   ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4048:5: note: in instantiation of function template specialization 'std::__1::__sort<std::__1::__less<_object, _object> &, _object *>' requested here
    __sort<_Comp_ref>(__first, __last, __comp);
    ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4057:12: note: in instantiation of function template specialization 'std::__1::sort<_object *, std::__1::__less<_object, _object> >' requested here
    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
           ^
sample.cpp:855:8: note: in instantiation of function template specialization 'std::__1::sort<_object *>' requested here
  std::sort<PyObject *>(__pyx_t_2, __pyx_t_5);
       ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3609:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3773:9: error: no matching function for call to '__sort3'
        _VSTD::__sort3<_Compare>(__first, __first+1, --__last, __comp);
        ^~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__config:366:15: note: expanded from macro '_VSTD'
#define _VSTD std::_LIBCPP_NAMESPACE
              ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4003:32: note: in instantiation of function template specialization 'std::__1::__insertion_sort_incomplete<std::__1::__less<_object, _object> &, _object *>'
      requested here
            bool __fs = _VSTD::__insertion_sort_incomplete<_Compare>(__first, __i, __comp);
                               ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4048:5: note: in instantiation of function template specialization 'std::__1::__sort<std::__1::__less<_object, _object> &, _object *>' requested here
    __sort<_Comp_ref>(__first, __last, __comp);
    ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:4057:12: note: in instantiation of function template specialization 'std::__1::sort<_object *, std::__1::__less<_object, _object> >' requested here
    _VSTD::sort(__first, __last, __less<typename iterator_traits<_RandomAccessIterator>::value_type>());
           ^
sample.cpp:855:8: note: in instantiation of function template specialization 'std::__1::sort<_object *>' requested here
  std::sort<PyObject *>(__pyx_t_2, __pyx_t_5);
       ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3609:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3776:9: error: no matching function for call to '__sort4'
        _VSTD::__sort4<_Compare>(__first, __first+1, __first+2, --__last, __comp);
        ^~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__config:366:15: note: expanded from macro '_VSTD'
#define _VSTD std::_LIBCPP_NAMESPACE
              ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3646:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort4(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3779:9: error: no matching function for call to '__sort5'
        _VSTD::__sort5<_Compare>(__first, __first+1, __first+2, __first+3, --__last, __comp);
        ^~~~~~~~~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/__config:366:15: note: expanded from macro '_VSTD'
#define _VSTD std::_LIBCPP_NAMESPACE
              ^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3672:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort5(_ForwardIterator __x1, _ForwardIterator __x2, _ForwardIterator __x3,
^
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3784:5: error: no matching function for call to '__sort3'
    __sort3<_Compare>(__first, __first+1, __j, __comp);
    ^~~~~~~~~~~~~~~~~
/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/../include/c++/v1/algorithm:3609:1: note: candidate template ignored: substitution failure [with _Compare = std::__1::__less<_object, _object> &, _ForwardIterator = _object *]
__sort3(_ForwardIterator __x, _ForwardIterator __y, _ForwardIterator __z, _Compare __c)
^
8 errors generated.
error: command 'cc' failed with exit status 1
make: *** [all] Error 1

What am I not doing right to sort this vector?

Answer 1

Look at the first error message: "invalid operands to binary expression ('const _object' and 'const _object')" and the line it quotes is indirectly from std::less, which is the default comparison function when using std::sort. The reason for the error is that the C++ sequence being sorted seems to be made up of _object instances, not of integers as you seem to assume, and that for this type the less-than comparison is simply not defined.