Fix libcpp map/set/multiset/unordered type issues (GH-4410)

Fix insert return types, constness and input iterator templates.
Fix typing in iterators and add constructor to allow explicit conversion from iterator to const_iterator.

8 files changed, 485 insertions, 169 deletions

diff --git a/Cython/Includes/libcpp/map.pxd b/Cython/Includes/libcpp/map.pxd
index 67cfc1c25..c2c06b0c9 100644
--- a/Cython/Includes/libcpp/map.pxd
+++ b/Cython/Includes/libcpp/map.pxd
@@ -9,24 +9,34 @@ cdef extern from "<map>" namespace "std" nogil:
         ctypedef ALLOCATOR allocator_type
         cppclass iterator:
             pair[T, U]& operator*()
-            iterator operator++()
-            iterator operator--()
-            bint operator==(iterator)
-            bint operator!=(iterator)
+            iterator& operator++()
+            iterator& operator--()
+            bint operator==(const iterator&)
+            bint operator!=(const iterator&)
         cppclass reverse_iterator:
             pair[T, U]& 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
+            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&)
         map() except +
         map(map&) except +
         #map(key_compare&)
-        U& operator[](T&)
+        U& operator[](const T&)
         #map& operator=(map&)
         bint operator==(map&, map&)
         bint operator!=(map&, map&)
@@ -44,15 +54,16 @@ cdef extern from "<map>" namespace "std" nogil:
         iterator end()
         const_iterator const_end "end" ()
         pair[iterator, iterator] equal_range(const T&)
-        #pair[const_iterator, const_iterator] equal_range(key_type&)
-        void erase(iterator)
-        void erase(iterator, iterator)
+        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&)
-        pair[iterator, bint] insert(pair[T, U]) except + # XXX pair[T,U]&
-        iterator insert(iterator, pair[T, U]) except + # XXX pair[T,U]&
-        #void insert(input_iterator, input_iterator)
+        pair[iterator, bint] 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&)
diff --git a/Cython/Includes/libcpp/set.pxd b/Cython/Includes/libcpp/set.pxd
index 272509f78..abb00a6f6 100644
--- a/Cython/Includes/libcpp/set.pxd
+++ b/Cython/Includes/libcpp/set.pxd
@@ -5,20 +5,30 @@ cdef extern from "<set>" namespace "std" nogil:
         ctypedef T value_type
         cppclass iterator:
             T& operator*()
-            iterator operator++()
-            iterator operator--()
-            bint operator==(iterator)
-            bint operator!=(iterator)
+            iterator& operator++()
+            iterator& operator--()
+            bint operator==(const iterator &)
+            bint operator!=(const 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
+            reverse_iterator& operator++()
+            reverse_iterator& operator--()
+            bint operator==(const reverse_iterator&)
+            bint operator!=(const reverse_iterator&)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const T& 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 T& operator*()
+            const_reverse_iterator& operator++()
+            const_reverse_iterator& operator--()
+            bint operator==(const const_reverse_iterator&)
+            bint operator!=(const const_reverse_iterator&)
         set() except +
         set(set&) except +
         #set(key_compare&)
@@ -37,18 +47,20 @@ cdef extern from "<set>" namespace "std" nogil:
         iterator end()
         const_iterator const_end "end"()
         pair[iterator, iterator] equal_range(const T&)
-        #pair[const_iterator, const_iterator] equal_range(T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(const T&)
         iterator erase(iterator)
-        iterator erase(iterator, iterator)
-        size_t erase(T&)
-        iterator find(T&)
-        const_iterator const_find "find"(T&)
+        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&)
         pair[iterator, bint] insert(const T&) except +
         iterator insert(iterator, const T&) except +
-        void insert(iterator, iterator) except +
+        iterator const_insert "insert"(const_iterator, const T&) except +
+        void insert[InputIt](InputIt, InputIt) except +
         #key_compare key_comp()
-        iterator lower_bound(T&)
-        const_iterator const_lower_bound "lower_bound"(T&)
+        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"()
@@ -65,20 +77,30 @@ cdef extern from "<set>" namespace "std" nogil:
 
         cppclass iterator:
             T& operator*()
-            iterator operator++()
-            iterator operator--()
-            bint operator==(iterator)
-            bint operator!=(iterator)
+            iterator& operator++()
+            iterator& operator--()
+            bint operator==(const iterator&)
+            bint operator!=(const 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
+            reverse_iterator& operator++()
+            reverse_iterator& operator--()
+            bint operator==(const reverse_iterator&)
+            bint operator!=(const reverse_iterator&)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const T& 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 T& operator*()
+            const_reverse_iterator& operator++()
+            const_reverse_iterator& operator--()
+            bint operator==(const const_reverse_iterator&)
+            bint operator!=(const const_reverse_iterator&)
 
         multiset() except +
         multiset(multiset&) except +
@@ -98,18 +120,20 @@ cdef extern from "<set>" namespace "std" nogil:
         iterator end()
         const_iterator const_end "end"()
         pair[iterator, iterator] equal_range(const T&)
-        #pair[const_iterator, const_iterator] equal_range(T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(const 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 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 T&) except +
         iterator insert(iterator, const T&) except +
-        void insert(iterator, iterator) except +
+        iterator const_insert "insert"(const_iterator, const T&) except +
+        void insert[InputIt](InputIt, InputIt) except +
         #key_compare key_comp()
-        iterator lower_bound(T&)
-        const_iterator const_lower_bound "lower_bound"(T&)
+        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"()
diff --git a/Cython/Includes/libcpp/unordered_map.pxd b/Cython/Includes/libcpp/unordered_map.pxd
index 8edf44482..be7713821 100644
--- a/Cython/Includes/libcpp/unordered_map.pxd
+++ b/Cython/Includes/libcpp/unordered_map.pxd
@@ -5,26 +5,22 @@ cdef extern from "<unordered_map>" namespace "std" nogil:
         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++()
-            iterator operator--()
-            bint operator==(iterator)
-            bint operator!=(iterator)
-        cppclass reverse_iterator:
-            pair[T, U]& 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
+            iterator& operator++()
+            bint operator==(const iterator&)
+            bint operator!=(const 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_map() except +
         unordered_map(unordered_map&) except +
         #unordered_map(key_compare&)
-        U& operator[](T&)
+        U& operator[](const T&)
         #unordered_map& operator=(unordered_map&)
         bint operator==(unordered_map&, unordered_map&)
         bint operator!=(unordered_map&, unordered_map&)
@@ -32,37 +28,34 @@ cdef extern from "<unordered_map>" namespace "std" nogil:
         bint operator>(unordered_map&, unordered_map&)
         bint operator<=(unordered_map&, unordered_map&)
         bint operator>=(unordered_map&, unordered_map&)
-        U& at(const T&)
-        const U& const_at "at"(const T&)
+        U& at(const T&) except +
+        const U& const_at "at"(const T&) except +
         iterator begin()
         const_iterator const_begin "begin"()
         void clear()
-        size_t count(T&)
+        size_t count(const T&)
         bint empty()
         iterator end()
         const_iterator const_end "end"()
-        pair[iterator, iterator] equal_range(T&)
+        pair[iterator, iterator] equal_range(const T&)
         pair[const_iterator, const_iterator] const_equal_range "equal_range"(const 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(pair[T, U]) # XXX pair[T,U]&
-        iterator insert(iterator, pair[T, U]) # XXX pair[T,U]&
-        iterator insert(iterator, 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&)
+        pair[iterator, bint] 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(T&)
-        const_iterator const_lower_bound "lower_bound"(T&)
+        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(unordered_map&)
-        iterator upper_bound(T&)
-        const_iterator const_upper_bound "upper_bound"(T&)
+        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()
diff --git a/Cython/Includes/libcpp/unordered_set.pxd b/Cython/Includes/libcpp/unordered_set.pxd
index 1418f9e28..feb5adf63 100644
--- a/Cython/Includes/libcpp/unordered_set.pxd
+++ b/Cython/Includes/libcpp/unordered_set.pxd
@@ -5,20 +5,15 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
         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
+            iterator& operator++()
+            bint operator==(const iterator&)
+            bint operator!=(const iterator&)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const T& operator*()
+            const_iterator& operator++()
+            bint operator==(const const_iterator&)
+            bint operator!=(const const_iterator&)
         unordered_set() except +
         unordered_set(unordered_set&) except +
         #unordered_set& operator=(unordered_set&)
@@ -27,25 +22,22 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
         iterator begin()
         const_iterator const_begin "begin"()
         void clear()
-        size_t count(T&)
+        size_t count(const 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&)
+        pair[iterator, iterator] equal_range(const T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(const 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)
+        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&)
+        pair[iterator, bint] insert(const T&) except +
+        iterator insert(const_iterator, const T&) except +
+        void insert[InputIt](InputIt, InputIt) except +
         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()
@@ -64,20 +56,15 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
 
         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
+            iterator& operator++()
+            bint operator==(const iterator&)
+            bint operator!=(const iterator&)
+        cppclass const_iterator:
+            const_iterator(iterator)
+            const T& operator*()
+            const_iterator& operator++()
+            bint operator==(const const_iterator&)
+            bint operator!=(const const_iterator&)
 
         unordered_multiset() except +
         unordered_multiset(unordered_multiset&) except +
@@ -87,25 +74,22 @@ cdef extern from "<unordered_set>" namespace "std" nogil:
         iterator begin()
         const_iterator const_begin "begin"()
         void clear()
-        size_t count(T&)
+        size_t count(const 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&)
+        pair[iterator, iterator] equal_range(const T&)
+        pair[const_iterator, const_iterator] const_equal_range "equal_range"(const 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)
+        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 T&) except +
+        iterator insert(const_iterator, const T&) except +
+        void insert[InputIt](InputIt, InputIt) except +
         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_multiset&)
         #value_compare value_comp()
diff --git a/tests/run/cpp_stl_cpp11.pyx b/tests/run/cpp_stl_cpp11.pyx
index ffeafdb3c..087d9b1aa 100644
--- a/tests/run/cpp_stl_cpp11.pyx
+++ b/tests/run/cpp_stl_cpp11.pyx
@@ -113,7 +113,7 @@ def test_unordered_set_functionality():
         unordered_set[int].iterator iterator = int_set.begin()
     int_set.insert(1)
     assert int_set.size() == 1
-    int_set.erase(int_set.begin(), int_set.end())
+    int_set.erase(unordered_set[int].const_iterator(int_set.begin()), unordered_set[int].const_iterator(int_set.end()))
     assert int_set.size() == 0
     int_set.insert(1)
     assert int_set.erase(1) == 1 # returns number of elements erased
@@ -176,7 +176,7 @@ def test_unordered_map_functionality():
     int_map.clear()
     int_map.insert(int_map2.begin(), int_map2.end())
     assert int_map.size() == 2
-    assert int_map.erase(int_map.begin(), int_map.end()) == int_map.end()
+    assert int_map.erase(unordered_map[int,int].const_iterator(int_map.begin()), unordered_map[int,int].const_iterator(int_map.end())) == int_map.end()
 
     int_map.max_load_factor(0.5)
     assert int_map.max_load_factor() == 0.5
diff --git a/tests/run/cpp_stl_map.pyx b/tests/run/cpp_stl_map.pyx
new file mode 100644
index 000000000..dc352a166
--- /dev/null
+++ b/tests/run/cpp_stl_map.pyx
@@ -0,0 +1,137 @@
+# mode: run
+# tag: cpp, cpp11
+
+# cython: language_level=3
+
+from libcpp.map cimport map
+from libcpp.unordered_map cimport unordered_map
+from libcpp.utility cimport pair
+
+def test_map_insert(vals):
+    """
+    >>> test_map_insert([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef map[int,int] m = map[int, int]()
+    cdef pair[map[int, int].iterator, bint] ret
+    for v in vals:
+        ret = m.insert(v)
+    return [ (item.first, item.second) for item in m ]
+
+def test_map_insert_it(vals):
+    """
+    >>> test_map_insert_it([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    cdef map[int,int] m = map[int,int]()
+    for k, v in vals:
+        um.insert(pair[int,int](k, v))
+    m.insert(um.begin(), um.end())
+    return [ (item.first, item.second) for item in m ]
+
+def test_map_count(vals, to_find):
+    """
+    >>> test_map_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    1
+    >>> test_map_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    1
+    """
+    cdef map[int,int] m = map[int,int]()
+    for v in vals:
+        m.insert(v)
+    return m.count(to_find)
+
+def test_map_erase(vals, int to_remove):
+    """
+    >>> test_map_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (3, 3)]
+    >>> test_map_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef map[int,int] m = map[int,int]()
+    cdef size_t ret
+    for v in vals:
+        m.insert(v)
+    ret = m.erase(to_remove)
+    return [ (item.first, item.second) for item in m ]
+
+def test_map_find_erase(vals, to_remove):
+    """
+    >>> test_map_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (3, 3)]
+    >>> test_map_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef map[int,int] m = map[int,int]()
+    cdef map[int,int].iterator it
+    for v in vals:
+        m.insert(v)
+    it = m.find(to_remove)
+    it = m.erase(it)
+    return [ (item.first, item.second) for item in m ]
+
+
+def test_unordered_map_insert(vals):
+    """
+    >>> test_unordered_map_insert([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    cdef pair[unordered_map[int,int].iterator, bint] ret
+    for v in vals:
+        ret = um.insert(v)
+    return sorted([ (item.first, item.second) for item in um ])
+
+def test_unordered_map_insert_it(vals):
+    """
+    >>> test_unordered_map_insert_it([(1,1),(2,2),(2,2),(3,3),(-1,-1)])
+    [(-1, -1), (1, 1), (2, 2), (3, 3)]
+    """
+    cdef map[int,int] m = map[int,int]()
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    for v in vals:
+        m.insert(v)
+    um.insert(m.begin(), m.end())
+    return sorted([ (item.first, item.second) for item in um ])
+
+def test_unordered_map_count(vals, to_find):
+    """
+    >>> test_unordered_map_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    1
+    >>> test_unordered_map_count([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    1
+    """
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    for v in vals:
+        um.insert(v)
+    return um.count(to_find)
+
+def test_unordered_map_erase(vals, int to_remove):
+    """
+    >>> test_unordered_map_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (3, 3)]
+    >>> test_unordered_map_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    cdef size_t ret
+    for v in vals:
+        um.insert(v)
+    ret = um.erase(to_remove)
+    return sorted([ (item.first, item.second) for item in um ])
+
+def test_unordered_map_find_erase(vals, to_remove):
+    """
+    >>> test_unordered_map_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 1)
+    [(-1, -1), (2, 2), (3, 3)]
+    >>> test_unordered_map_find_erase([(1,1),(2,2),(2,2),(3,3),(-1,-1)], 2)
+    [(-1, -1), (1, 1), (3, 3)]
+    """
+    cdef unordered_map[int,int] um = unordered_map[int,int]()
+    cdef unordered_map[int,int].iterator it
+    for v in vals:
+        um.insert(v)
+    it = um.find(to_remove)
+    it = um.erase(it)
+    return sorted([ item for item in um ])
diff --git a/tests/run/cpp_stl_multiset.pyx b/tests/run/cpp_stl_multiset.pyx
index 66842e04e..50bdbca96 100644
--- a/tests/run/cpp_stl_multiset.pyx
+++ b/tests/run/cpp_stl_multiset.pyx
@@ -12,8 +12,21 @@ def test_multiset_insert(vals):
     [-1, 1, 2, 2, 3]
     """
     cdef multiset[int] ms = multiset[int]()
+    cdef multiset[int].iterator it
     for v in vals:
-        ms.insert(v)
+        it = ms.insert(v)
+    return [ item for item in ms ]
+
+def test_multiset_insert_it(vals):
+    """
+    >>> test_multiset_insert_it([1,2,2,3, -1])
+    [-1, 1, 2, 2, 3]
+    """
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
+    cdef multiset[int] ms = multiset[int]()
+    for v in vals:
+        ums.insert(v)
+    ms.insert(ums.begin(), ums.end())
     return [ item for item in ms ]
 
 def test_multiset_count(vals, to_find):
@@ -36,9 +49,10 @@ def test_multiset_erase(vals, int to_remove):
     [-1, 1, 3]
     """
     cdef multiset[int] ms = multiset[int]()
+    cdef size_t ret
     for v in vals:
         ms.insert(v)
-    ms.erase(to_remove)
+    ret = ms.erase(to_remove)
     return [ item for item in ms ]
 
 def test_multiset_find_erase(vals, to_remove):
@@ -49,10 +63,11 @@ def test_multiset_find_erase(vals, to_remove):
     [-1, 1, 2, 3]
     """
     cdef multiset[int] ms = multiset[int]()
+    cdef multiset[int].iterator it
     for v in vals:
         ms.insert(v)
     it = ms.find(to_remove)
-    ms.erase(it)
+    it = ms.erase(it)
     return [ item for item in ms ]
 
 
@@ -61,10 +76,23 @@ 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]()
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
+    cdef unordered_multiset[int].iterator it
+    for v in vals:
+        it = ums.insert(v)
+    return sorted([ item for item in ums ])
+
+def test_unordered_multiset_insert_it(vals):
+    """
+    >>> test_unordered_multiset_insert_it([1,2,2,3, -1])
+    [-1, 1, 2, 2, 3]
+    """
+    cdef multiset[int] ms = multiset[int]()
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
     for v in vals:
         ms.insert(v)
-    return sorted([ item for item in ms ])
+    ums.insert(ms.begin(), ms.end())
+    return sorted([ item for item in ums ])
 
 def test_unordered_multiset_count(vals, to_find):
     """
@@ -73,10 +101,10 @@ def test_unordered_multiset_count(vals, to_find):
     >>> test_unordered_multiset_count([1,2,2,3, -1], 2)
     2
     """
-    cdef unordered_multiset[int] ms = unordered_multiset[int]()
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
     for v in vals:
-        ms.insert(v)
-    return ms.count(to_find)
+        ums.insert(v)
+    return ums.count(to_find)
 
 def test_unordered_multiset_erase(vals, int to_remove):
     """
@@ -85,11 +113,12 @@ def test_unordered_multiset_erase(vals, int to_remove):
     >>> 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]()
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
+    cdef size_t ret
     for v in vals:
-        ms.insert(v)
-    ms.erase(to_remove)
-    return sorted([ item for item in ms ])
+        ums.insert(v)
+    ret = ums.erase(to_remove)
+    return sorted([ item for item in ums ])
 
 def test_unordered_multiset_find_erase(vals, to_remove):
     """
@@ -98,12 +127,13 @@ def test_unordered_multiset_find_erase(vals, to_remove):
     >>> 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]()
+    cdef unordered_multiset[int] ums = unordered_multiset[int]()
+    cdef unordered_multiset[int].iterator it
     for v in vals:
-        ms.insert(v)
-    it = ms.find(to_remove)
-    ms.erase(it)
-    return sorted([ item for item in ms ])
+        ums.insert(v)
+    it = ums.find(to_remove)
+    it = ums.erase(it)
+    return sorted([ item for item in ums ])
 
 
 def test_unordered_multiset_misc():
diff --git a/tests/run/cpp_stl_set.pyx b/tests/run/cpp_stl_set.pyx
new file mode 100644
index 000000000..1b9debc76
--- /dev/null
+++ b/tests/run/cpp_stl_set.pyx
@@ -0,0 +1,137 @@
+# mode: run
+# tag: cpp, cpp11
+
+# cython: language_level=3
+
+from libcpp.set cimport set
+from libcpp.unordered_set cimport unordered_set
+from libcpp.utility cimport pair
+
+def test_set_insert(vals):
+    """
+    >>> test_set_insert([1,2,2,3, -1])
+    [-1, 1, 2, 3]
+    """
+    cdef set[int] s = set[int]()
+    cdef pair[set[int].iterator, bint] ret
+    for v in vals:
+        ret = s.insert(v)
+    return [item for item in s]
+
+def test_set_insert_it(vals):
+    """
+    >>> test_set_insert_it([1,2,2,3, -1])
+    [-1, 1, 2, 3]
+    """
+    cdef unordered_set[int] us = unordered_set[int]()
+    cdef set[int] s = set[int]()
+    for v in vals:
+        us.insert(v)
+    s.insert(us.begin(), us.end())
+    return [item for item in s]
+
+def test_set_count(vals, to_find):
+    """
+    >>> test_set_count([1,2,2,3, -1], 1)
+    1
+    >>> test_set_count([1,2,2,3, -1], 2)
+    1
+    """
+    cdef set[int] s = set[int]()
+    for v in vals:
+        s.insert(v)
+    return s.count(to_find)
+
+def test_set_erase(vals, int to_remove):
+    """
+    >>> test_set_erase([1,2,2,3, -1], 1)
+    [-1, 2, 3]
+    >>> test_set_erase([1,2,2,3, -1], 2)
+    [-1, 1, 3]
+    """
+    cdef set[int] s = set[int]()
+    cdef size_t ret
+    for v in vals:
+        s.insert(v)
+    ret = s.erase(to_remove)
+    return [item for item in s]
+
+def test_set_find_erase(vals, to_remove):
+    """
+    >>> test_set_find_erase([1,2,2,3, -1], 1)
+    [-1, 2, 3]
+    >>> test_set_find_erase([1,2,2,3, -1], 2)
+    [-1, 1, 3]
+    """
+    cdef set[int] s = set[int]()
+    cdef set[int].iterator it
+    for v in vals:
+        s.insert(v)
+    it = s.find(to_remove)
+    it = s.erase(it)
+    return [item for item in s]
+
+
+def test_unordered_set_insert(vals):
+    """
+    >>> test_unordered_set_insert([1,2,2,3, -1])
+    [-1, 1, 2, 3]
+    """
+    cdef unordered_set[int] us = unordered_set[int]()
+    cdef pair[unordered_set[int].iterator, bint] ret
+    for v in vals:
+        ret = us.insert(v)
+    return sorted([item for item in us])
+
+def test_unordered_set_insert_it(vals):
+    """
+    >>> test_unordered_set_insert_it([1,2,2,3, -1])
+    [-1, 1, 2, 3]
+    """
+    cdef set[int] s = set[int]()
+    cdef unordered_set[int] us = unordered_set[int]()
+    for v in vals:
+        s.insert(v)
+    us.insert(s.begin(), s.end())
+    return sorted([item for item in us])
+
+def test_unordered_set_count(vals, to_find):
+    """
+    >>> test_unordered_set_count([1,2,2,3, -1], 1)
+    1
+    >>> test_unordered_set_count([1,2,2,3, -1], 2)
+    1
+    """
+    cdef unordered_set[int] us = unordered_set[int]()
+    for v in vals:
+        us.insert(v)
+    return us.count(to_find)
+
+def test_unordered_set_erase(vals, int to_remove):
+    """
+    >>> test_unordered_set_erase([1,2,2,3, -1], 1)
+    [-1, 2, 3]
+    >>> test_unordered_set_erase([1,2,2,3, -1], 2)
+    [-1, 1, 3]
+    """
+    cdef unordered_set[int] us = unordered_set[int]()
+    cdef size_t ret
+    for v in vals:
+        us.insert(v)
+    ret = us.erase(to_remove)
+    return sorted([item for item in us])
+
+def test_unordered_set_find_erase(vals, to_remove):
+    """
+    >>> test_unordered_set_find_erase([1,2,2,3, -1], 1)
+    [-1, 2, 3]
+    >>> test_unordered_set_find_erase([1,2,2,3, -1], 2)
+    [-1, 1, 3]
+    """
+    cdef unordered_set[int] us = unordered_set[int]()
+    cdef unordered_set[int].iterator it
+    for v in vals:
+        us.insert(v)
+    it = us.find(to_remove)
+    it = us.erase(it)
+    return sorted([item for item in us])