How to extern from <algorithm> in Cython

Question

I'm trying to use partial_sort from the <algorithm> library within Cython, but I just cannot find the correct way to properly extern it.

reference

Here's my failed attempt:

%%cython -f

cdef extern from "<algorithm>" namespace "std":
    void partial_sort[RandomAccessIterator](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
    void partial_sort[RandomAccessIterator, Compare](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp)

Error message when using Cython 0.19.1:

Error compiling Cython file:
------------------------------------------------------------
...

cdef extern from "<algorithm>" namespace "std":
    cdef cppclass RandomAccessIterator:
        cppclass Compare
        void partial_sort[RandomAccessIterator]
                                             ^
------------------------------------------------------------

/Users/richizy/.ipython/cython/_cython_magic_cf4fbe14563c3de19c8c3af3253a182e.pyx:5:46: Not allowed in a constant expression

Error compiling Cython file:
------------------------------------------------------------
...

cdef extern from "<algorithm>" namespace "std":
    cdef cppclass RandomAccessIterator:
        cppclass Compare
        void partial_sort[RandomAccessIterator]
                                             ^
------------------------------------------------------------

/Users/richizy/.ipython/cython/_cython_magic_cf4fbe14563c3de19c8c3af3253a182e.pyx:5:46: Array dimension not integer

Error compiling Cython file:
------------------------------------------------------------
...

cdef extern from "<algorithm>" namespace "std":
    cdef cppclass RandomAccessIterator:
        cppclass Compare
        void partial_sort[RandomAccessIterator]
                        ^
------------------------------------------------------------

/Users/richizy/.ipython/cython/_cython_magic_cf4fbe14563c3de19c8c3af3253a182e.pyx:5:25: Array element type 'void' is incomplete

Error message when using Cython 0.20.1:

CompileError: command 'gcc' failed with exit status 1

warning: .ipython/cython/_cython_magic_121a91d1fdd64d85c4b01e6540fd86d6.pyx:4:52: Function signature does not match previous declaration

---

Edit: As of 2/22/14, for Cython 0.20.1

https://groups.google.com/forum/#!topic/cython-users/H4UEM6IlvpM

Correct, Cython does not support default template specializations (for functions or classes). Nor does it support non-typename template parameters (with out some hacking). Both are missing features that we'd like to get to someday.

• Robert

Answer 1

It seems that Cython doesn't work well with template specialization. The following code works for me (Cython version 0.20, Python 2.7.5, g++ (SUSE Linux) 4.8.1)

from libcpp.vector cimport vector

cdef extern from "<algorithm>" namespace "std":
    void partial_sort[RandomAccessIterator](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
    #    void partial_sort[RandomAccessIterator, Compare](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp)

cpdef bla():
    cdef vector[int] v
    cdef int i = 0
    cdef list res = []
    v.push_back(4)
    v.push_back(6)
    v.push_back(2)
    v.push_back(5)
    partial_sort[vector[int].iterator](v.begin(), v.end(), v.end())
    for i in v:
        res.append(i)
    return res

Then

>>> import bla
>>> bla.bla()
[2, 4, 5, 6]

However uncommenting the line break the code with

bla.pyx:15:16: Wrong number of template arguments: expected 2, got 1

Here is a workaround: You declare the different specialization of the template function under two different names:

cdef extern from "<algorithm>" namespace "std":
    void partial_sort_1 "std::partial_sort"[RandomAccessIterator](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
    void partial_sort_2 "std::partial_sort"[RandomAccessIterator, Compare](RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp)

And then you use the correct one as in:

partial_sort_1[vector[int].iterator](v.begin(), v.end(), v.end())

Note: I got from Cython-Users that this is a know problem and that having template partial specialization on Cython is on their wish list for a moment.