Add missing multiset class to the standard library bindings (GH-4273)

3 files changed, 225 insertions, 10 deletions

diff --git a/Cython/Includes/libcpp/set.pxd b/Cython/Includes/libcpp/set.pxd
index 1069be746..272509f78 100644
--- a/Cython/Includes/libcpp/set.pxd
+++ b/Cython/Includes/libcpp/set.pxd
@@ -59,3 +59,63 @@ cdef extern from "<set>" namespace "std" nogil:
         iterator upper_bound(const T&)
         const_iterator const_upper_bound "upper_bound"(const T&)
         #value_compare value_comp()
+
+    cdef cppclass multiset[T]:
+        ctypedef T value_type
+
+        cppclass iterator:
+            T& operator*()
+            iterator operator++()
+            iterator operator--()
+            bint operator==(iterator)
+            bint operator!=(iterator)
+        cppclass reverse_iterator:
+            T& operator*()
+            iterator operator++()
+            iterator operator--()
+            bint operator==(reverse_iterator)
+            bint operator!=(reverse_iterator)
+        cppclass const_iterator(iterator):
+            pass
+        cppclass const_reverse_iterator(reverse_iterator):
+            pass
+
+        multiset() except +
+        multiset(multiset&) except +
+        #multiset(key_compare&)
+        #multiset& operator=(multiset&)
+        bint operator==(multiset&, multiset&)
+        bint operator!=(multiset&, multiset&)
+        bint operator<(multiset&, multiset&)
+        bint operator>(multiset&, multiset&)
+        bint operator<=(multiset&, multiset&)
+        bint operator>=(multiset&, multiset&)
+        iterator begin()
+        const_iterator const_begin "begin"()
+        void clear()
+        size_t count(const T&)
+        bint empty()
+        iterator end()
+        const_iterator const_end "end"()
+        pair[iterator, iterator] equal_range(const T&)
+        #pair[const_iterator, const_iterator] equal_range(T&)
+        iterator erase(iterator)
+        iterator erase(iterator, iterator)
+        size_t erase(T&)
+        iterator find(T&)
+        const_iterator const_find "find"(T&)
+        pair[iterator, bint] insert(const T&) except +
+        iterator insert(iterator, const T&) except +
+        void insert(iterator, iterator) except +
+        #key_compare key_comp()
+        iterator lower_bound(T&)
+        const_iterator const_lower_bound "lower_bound"(T&)
+        size_t max_size()
+        reverse_iterator rbegin()
+        const_reverse_iterator const_rbegin "rbegin"()
+        reverse_iterator rend()
+        const_reverse_iterator const_rend "rend"()
+        size_t size()
+        void swap(multiset&)
+        iterator upper_bound(const T&)
+        const_iterator const_upper_bound "upper_bound"(const T&)
diff --git a/Cython/Includes/libcpp/unordered_set.pxd b/Cython/Includes/libcpp/unordered_set.pxd
index 5aa241752..2eba3a1c0 100644
--- a/Cython/Includes/libcpp/unordered_set.pxd
+++ b/Cython/Includes/libcpp/unordered_set.pxd
@@ -21,14 +21,9 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
             pass
         unordered_set() except +
         unordered_set(unordered_set&) except +
-        #unordered_set(key_compare&)
         #unordered_set& operator=(unordered_set&)
         bint operator==(unordered_set&, unordered_set&)
         bint operator!=(unordered_set&, unordered_set&)
-        bint operator<(unordered_set&, unordered_set&)
-        bint operator>(unordered_set&, unordered_set&)
-        bint operator<=(unordered_set&, unordered_set&)
-        bint operator>=(unordered_set&, unordered_set&)
         iterator begin()
         const_iterator const_begin "begin"()
         void clear()
@@ -45,10 +40,7 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
         const_iterator const_find "find"(T&)
         pair[iterator, bint] insert(T&)
         iterator insert(iterator, T&)
-        #key_compare key_comp()
         iterator insert(iterator, iterator)
-        iterator lower_bound(T&)
-        const_iterator const_lower_bound "lower_bound"(T&)
         size_t max_size()
         reverse_iterator rbegin()
         const_reverse_iterator const_rbegin "rbegin"()
@@ -56,8 +48,65 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
         const_reverse_iterator const_rend "rend"()
         size_t size()
         void swap(unordered_set&)
-        iterator upper_bound(T&)
-        const_iterator const_upper_bound "upper_bound"(T&)
+        #value_compare value_comp()
+        void max_load_factor(float)
+        float max_load_factor()
+        void rehash(size_t)
+        void reserve(size_t)
+        size_t bucket_count()
+        size_t max_bucket_count()
+        size_t bucket_size(size_t)
+        size_t bucket(const T&)
+
+    cdef cppclass unordered_multiset[T,HASH=*,PRED=*,ALLOCATOR=*]:
+        ctypedef T value_type
+
+        cppclass iterator:
+            T& operator*()
+            iterator operator++()
+            iterator operator--()
+            bint operator==(iterator)
+            bint operator!=(iterator)
+        cppclass reverse_iterator:
+            T& operator*()
+            iterator operator++()
+            iterator operator--()
+            bint operator==(reverse_iterator)
+            bint operator!=(reverse_iterator)
+        cppclass const_iterator(iterator):
+            pass
+        cppclass const_reverse_iterator(reverse_iterator):
+            pass
+
+        unordered_multiset() except +
+        unordered_multiset(unordered_multiset&) except +
+        #unordered_multiset& operator=(unordered_multiset&)
+        bint operator==(unordered_multiset&, unordered_multiset&)
+        bint operator!=(unordered_multiset&, unordered_multiset&)
+        iterator begin()
+        const_iterator const_begin "begin"()
+        void clear()
+        size_t count(T&)
+        bint empty()
+        iterator end()
+        const_iterator const_end "end"()
+        pair[iterator, iterator] equal_range(T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(T&)
+        iterator erase(iterator)
+        iterator erase(iterator, iterator)
+        size_t erase(T&)
+        iterator find(T&)
+        const_iterator const_find "find"(T&)
+        pair[iterator, bint] insert(T&)
+        iterator insert(iterator, T&)
+        iterator insert(iterator, iterator)
+        size_t max_size()
+        reverse_iterator rbegin()
+        const_reverse_iterator const_rbegin "rbegin"()
+        reverse_iterator rend()
+        const_reverse_iterator const_rend "rend"()
+        size_t size()
+        void swap(unordered_set&)
         #value_compare value_comp()
         void max_load_factor(float)
         float max_load_factor()
diff --git a/tests/run/cpp_stl_multiset.pyx b/tests/run/cpp_stl_multiset.pyx
new file mode 100644
index 000000000..26f3bbe61
--- /dev/null
+++ b/tests/run/cpp_stl_multiset.pyx
@@ -0,0 +1,106 @@
+# mode: run
+# tag: cpp, cpp11
+
+# cython: language_level=3
+
+from libcpp.set cimport multiset
+from libcpp.unordered_set cimport unordered_multiset
+
+def test_multiset_insert(vals):
+    """
+    >>> test_multiset_insert([1,2,2,3, -1])
+    [-1, 1, 2, 2, 3]
+    """
+    cdef multiset[int] ms = multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    return [ item for item in ms ]
+
+def test_multiset_count(vals, to_find):
+    """
+    >>> test_multiset_count([1,2,2,3, -1], 1)
+    1
+    >>> test_multiset_count([1,2,2,3, -1], 2)
+    2
+    """
+    cdef multiset[int] ms = multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    return ms.count(to_find)
+
+def test_multiset_erase(vals, int to_remove):
+    """
+    >>> test_multiset_erase([1,2,2,3, -1], 1)
+    [-1, 2, 2, 3]
+    >>> test_multiset_erase([1,2,2,3, -1], 2)  # removes both copies of 2
+    [-1, 1, 3]
+    """
+    cdef multiset[int] ms = multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    ms.erase(to_remove)
+    return [ item for item in ms ]
+
+def test_multiset_find_erase(vals, to_remove):
+    """
+    >>> test_multiset_find_erase([1,2,2,3, -1], 1)
+    [-1, 2, 2, 3]
+    >>> test_multiset_find_erase([1,2,2,3, -1], 2)  # removes a single copy of 2
+    [-1, 1, 2, 3]
+    """
+    cdef multiset[int] ms = multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    it = ms.find(to_remove)
+    ms.erase(it)
+    return [ item for item in ms ]
+
+
+def test_unordered_multiset_insert(vals):
+    """
+    >>> test_unordered_multiset_insert([1,2,2,3, -1])
+    [-1, 1, 2, 2, 3]
+    """
+    cdef unordered_multiset[int] ms = unordered_multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    return sorted([ item for item in ms ])
+
+def test_unordered_multiset_count(vals, to_find):
+    """
+    >>> test_unordered_multiset_count([1,2,2,3, -1], 1)
+    1
+    >>> test_unordered_multiset_count([1,2,2,3, -1], 2)
+    2
+    """
+    cdef unordered_multiset[int] ms = unordered_multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    return ms.count(to_find)
+
+def test_unordered_multiset_erase(vals, int to_remove):
+    """
+    >>> test_unordered_multiset_erase([1,2,2,3, -1], 1)
+    [-1, 2, 2, 3]
+    >>> test_unordered_multiset_erase([1,2,2,3, -1], 2)  # removes both copies of 2
+    [-1, 1, 3]
+    """
+    cdef unordered_multiset[int] ms = unordered_multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    ms.erase(to_remove)
+    return sorted([ item for item in ms ])
+
+def test_unordered_multiset_find_erase(vals, to_remove):
+    """
+    >>> test_unordered_multiset_find_erase([1,2,2,3, -1], 1)
+    [-1, 2, 2, 3]
+    >>> test_unordered_multiset_find_erase([1,2,2,3, -1], 2)  # removes a single copy of 2
+    [-1, 1, 2, 3]
+    """
+    cdef unordered_multiset[int] ms = unordered_multiset[int]()
+    for v in vals:
+        ms.insert(v)
+    it = ms.find(to_remove)
+    ms.erase(it)
+    return sorted([ item for item in ms ])