sorting on C++ vector with cython

Question

I need a given structure with which i would have to do a lot of append/pop, accessing the values and make calculations. I would have to do them continuously to update my data.

I first looked at python list that will be in a dic. The main concern is that the calculations are slow, even a simple sum takes time.

I looked at the numpy side but the append/pop are long (although i don't think it's a good idea with numpy) and even accessing a value is not that fast.

I turned to cython to boost my code by staying on lists/dict and i saw a good performance gain but and it was always slow.

So i thought of turning to std::map and std::vector to do the same thing but faster.

I did the test with the sum of a vector, even numpy was slower so i thought i had found the structure i needed. I then tested the sorting, which i should do very regularly and surprisingly the vector is 2-3 times longer than it takes to sort a list in python. After a lot of research I can't figure out the reason why sorting vector was so 'slow'.

test_cython.pyx

# distutils: language = c++
from libcpp.vector cimport vector

from libcpp.algorithm cimport sort as stdsort

#I tried to import this way but the speed doesn't change.
"""cdef extern from "<algorithm>" namespace "std":
    void sort(...)
    void stdsort "sort"(...)"""

cdef class VectorSort:
    cdef vector[long] v

    def __init__(self):
        for i in range(100000):
            self.v.push_back(i)

    def vector_sort(self):
        stdsort(self.v.begin(), self.v.end())

cdef class PythonSort:
    cdef list l

    def __init__(self):
        self.l = [i for i in range(100000)]

    def python_sort(self):
        self.l.sort()

main.py

import timeit
from test_cython import VectorSort, PythonSort

v = VectorSort()
def sort_vector():
    v.vector_sort()

l = PythonSort()
def sort_python():
    l.python_sort()

print(timeit.timeit('sort_vector()', 'from __main__ import sort_vector', number=1000), '-> sort_vector')
print(timeit.timeit('sort_python()', 'from __main__ import sort_python', number=1000), '-> sort_python')

output:

0.9847416740085464 -> sort_vector
0.3762993350101169 -> sort_python