Add C++ multimap/unordered_multimap (GH-4419)

3 files changed, 275 insertions, 0 deletions

diff --git a/Cython/Includes/libcpp/map.pxd b/Cython/Includes/libcpp/map.pxd
index 624a7ac02..67cfc1c25 100644
--- a/Cython/Includes/libcpp/map.pxd
+++ b/Cython/Includes/libcpp/map.pxd
@@ -66,3 +66,77 @@ cdef extern from "<map>" namespace "std" nogil:
         iterator upper_bound(const T&)
         const_iterator const_upper_bound "upper_bound"(const T&)
         #value_compare value_comp()
+
+    cdef cppclass multimap[T, U, COMPARE=*, ALLOCATOR=*]:
+        ctypedef T key_type
+        ctypedef U mapped_type
+        ctypedef pair[const T, U] value_type
+        ctypedef COMPARE key_compare
+        ctypedef ALLOCATOR allocator_type
+        cppclass iterator:
+            pair[T, U]& operator*()
+            iterator& operator++()
+            iterator& operator--()
+            bint operator==(const iterator&)
+            bint operator!=(const iterator&)
+        cppclass reverse_iterator:
+            pair[T, U]& operator*()
+            reverse_iterator& operator++()
+            reverse_iterator& operator--()
+            bint operator==(const reverse_iterator&)
+            bint operator!=(const reverse_iterator&)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const pair[T, U]& operator*()
+            const_iterator& operator++()
+            const_iterator& operator--()
+            bint operator==(const const_iterator&)
+            bint operator!=(const const_iterator&)
+        cppclass const_reverse_iterator:
+            const_reverse_iterator(reverse_iterator)
+            const pair[T, U]& operator*()
+            const_reverse_iterator& operator++()
+            const_reverse_iterator& operator--()
+            bint operator==(const const_reverse_iterator&)
+            bint operator!=(const const_reverse_iterator&)
+        multimap() except +
+        multimap(const multimap&) except +
+        #multimap(key_compare&)
+        #multimap& operator=(multimap&)
+        bint operator==(const multimap&, const multimap&)
+        bint operator!=(const multimap&, const multimap&)
+        bint operator<(const multimap&, const multimap&)
+        bint operator>(const multimap&, const multimap&)
+        bint operator<=(const multimap&, const multimap&)
+        bint operator>=(const multimap&, const multimap&)
+        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] const_equal_range "equal_range"(const T&)
+        iterator erase(iterator)
+        iterator const_erase "erase"(const_iterator)
+        iterator erase(const_iterator, const_iterator)
+        size_t erase(const T&)
+        iterator find(const T&)
+        const_iterator const_find "find"(const T&)
+        iterator insert(const pair[T, U]&) except +
+        iterator insert(const_iterator, const pair[T, U]&) except +
+        void insert[InputIt](InputIt, InputIt) except +
+        #key_compare key_comp()
+        iterator lower_bound(const T&)
+        const_iterator const_lower_bound "lower_bound"(const 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(multimap&)
+        iterator upper_bound(const T&)
+        const_iterator const_upper_bound "upper_bound"(const T&)
+        #value_compare value_comp()
diff --git a/Cython/Includes/libcpp/unordered_map.pxd b/Cython/Includes/libcpp/unordered_map.pxd
index 9da0fffd5..8edf44482 100644
--- a/Cython/Includes/libcpp/unordered_map.pxd
+++ b/Cython/Includes/libcpp/unordered_map.pxd
@@ -73,3 +73,69 @@ cdef extern from "<unordered_map>" namespace "std" nogil:
         size_t max_bucket_count()
         size_t bucket_size(size_t)
         size_t bucket(const T&)
+
+    cdef cppclass unordered_multimap[T, U, HASH=*, PRED=*, ALLOCATOR=*]:
+        ctypedef T key_type
+        ctypedef U mapped_type
+        ctypedef pair[const T, U] value_type
+        ctypedef ALLOCATOR allocator_type
+        cppclass iterator:
+            pair[T, U]& operator*()
+            iterator operator++()
+            bint operator==(iterator)
+            bint operator!=(iterator)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const pair[T, U]& operator*()
+            const_iterator& operator++()
+            bint operator==(const const_iterator&)
+            bint operator!=(const const_iterator&)
+        unordered_multimap() except +
+        unordered_multimap(const unordered_multimap&) except +
+        #unordered_multimap(key_compare&)
+        #unordered_map& operator=(unordered_multimap&)
+        bint operator==(const unordered_multimap&, const unordered_multimap&)
+        bint operator!=(const unordered_multimap&, const unordered_multimap&)
+        bint operator<(const unordered_multimap&, const unordered_multimap&)
+        bint operator>(const unordered_multimap&, const unordered_multimap&)
+        bint operator<=(const unordered_multimap&, const unordered_multimap&)
+        bint operator>=(const unordered_multimap&, const unordered_multimap&)
+        iterator begin()
+        const_iterator const_begin "begin"()
+        #local_iterator begin(size_t)
+        #const_local_iterator const_begin "begin"(size_t)
+        void clear()
+        size_t count(const T&)
+        bint empty()
+        iterator end()
+        const_iterator const_end "end"()
+        #local_iterator end(size_t)
+        #const_local_iterator const_end "end"(size_t)
+        pair[iterator, iterator] equal_range(const T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(const T&)
+        iterator erase(iterator)
+        iterator const_erase "erase"(const_iterator)
+        iterator erase(const_iterator, const_iterator)
+        size_t erase(const T&)
+        iterator find(const T&)
+        const_iterator const_find "find"(const T&)
+        iterator insert(const pair[T, U]&) except +
+        iterator insert(const_iterator, const pair[T, U]&) except +
+        void insert[InputIt](InputIt, InputIt) except +
+        #key_compare key_comp()
+        iterator lower_bound(const T&)
+        const_iterator const_lower_bound "lower_bound"(const T&)
+        size_t max_size()
+        size_t size()
+        void swap(unordered_multimap&)
+        iterator upper_bound(const T&)
+        const_iterator const_upper_bound "upper_bound"(const 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&)
diff --git a/tests/run/cpp_stl_multimap.pyx b/tests/run/cpp_stl_multimap.pyx
new file mode 100644
index 000000000..ede42b552
--- /dev/null
+++ b/tests/run/cpp_stl_multimap.pyx
@@ -0,0 +1,135 @@
+# mode: run
+# tag: cpp, cpp11
+
+# cython: language_level=3
+
+from libcpp.map cimport multimap
+from libcpp.unordered_map cimport unordered_multimap
+from libcpp.utility cimport pair
+
+def test_multimap_insert(vals):
+    """
+    >>> test_multimap_insert([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (2, 2), (3, 3)]
+    """
+    cdef multimap[int,int] mm = multimap[int, int]()
+    cdef multimap[int, int].iterator it
+    for v in vals:
+        it = mm.insert(v)
+    return [ (item.first, item.second) for item in mm ]
+
+def test_multimap_insert_it(vals):
+    """
+    >>> test_multimap_insert_it([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (2, 2), (3, 3)]
+    """
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    cdef multimap[int,int] mm = multimap[int,int]()
+    for k, v in vals:
+        umm.insert(pair[int,int](k, v))
+    mm.insert(umm.begin(), umm.end())
+    return [ (item.first, item.second) for item in mm ]
+
+def test_multimap_count(vals, to_find):
+    """
+    >>> test_multimap_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    1
+    >>> test_multimap_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    2
+    """
+    cdef multimap[int,int] mm = multimap[int,int]()
+    for v in vals:
+        mm.insert(v)
+    return mm.count(to_find)
+
+def test_multimap_erase(vals, int to_remove):
+    """
+    >>> test_multimap_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (2, 2), (3, 3)]
+    >>> test_multimap_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef multimap[int,int] mm = multimap[int,int]()
+    for v in vals:
+        mm.insert(v)
+    cdef size_t ret = mm.erase(to_remove)
+    return [ (item.first, item.second) for item in mm ]
+
+def test_multimap_find_erase(vals, to_remove):
+    """
+    >>> test_multimap_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (2, 2), (3, 3)]
+    >>> test_multimap_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef multimap[int,int] mm = multimap[int,int]()
+    cdef multimap[int,int].iterator it
+    for v in vals:
+        mm.insert(v)
+    it = mm.find(to_remove)
+    it = mm.erase(it)
+    return [ (item.first, item.second) for item in mm ]
+
+
+def test_unordered_multimap_insert(vals):
+    """
+    >>> test_unordered_multimap_insert([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (2, 2), (3, 3)]
+    """
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    cdef unordered_multimap[int,int].iterator it
+    for v in vals:
+        it = umm.insert(v)
+    return sorted([ (item.first, item.second) for item in umm ])
+
+def test_unordered_multimap_insert_it(vals):
+    """
+    >>> test_unordered_multimap_insert_it([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (2, 2), (3, 3)]
+    """
+    cdef multimap[int,int] mm = multimap[int,int]()
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    for v in vals:
+        mm.insert(v)
+    umm.insert(mm.begin(), mm.end())
+    return sorted([ (item.first, item.second) for item in umm ])
+
+def test_unordered_multimap_count(vals, to_find):
+    """
+    >>> test_unordered_multimap_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    1
+    >>> test_unordered_multimap_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    2
+    """
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    for v in vals:
+        umm.insert(v)
+    return umm.count(to_find)
+
+def test_unordered_multimap_erase(vals, int to_remove):
+    """
+    >>> test_unordered_multimap_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (2, 2), (3, 3)]
+    >>> test_unordered_multimap_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    for v in vals:
+        umm.insert(v)
+    cdef size_t ret = umm.erase(to_remove)
+    return sorted([ (item.first, item.second) for item in umm ])
+
+def test_unordered_multimap_find_erase(vals, to_remove):
+    """
+    >>> test_unordered_multimap_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (2, 2), (3, 3)]
+    >>> test_unordered_multimap_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef unordered_multimap[int,int] umm = unordered_multimap[int,int]()
+    cdef unordered_multimap[int,int].iterator it
+    for v in vals:
+        umm.insert(v)
+    it = umm.find(to_remove)
+    it = umm.erase(it)
+    return sorted([ item for item in umm ])