[libc++] Simple contains for associative containers

[jloser]

Summary

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0458r2.html

This patch adds partial support for p0458, adding a contains member function
for associative containers. This feature allows users to query whether
a key type exists in an associative container.

Note:

• This patch does not add support for heterogeneous key overloads for contains. A future patch will follow for support this. Currently, the unordered associative containers do not yet have a notion of transparent lookups.
• This patch does not add support for contains with precomputed hashes. A future patch will follow for support for this.

[mclow.lists]

How does this compare to D59344 ?

[jloser]

Sorry, I did not notice https://reviews.llvm.org/D59344 was in flight. That one looks like a superset of these changes, though I think we should only provide the declaration/definitions of contains in the case of #if _LIBCPP_STD_VER > 17. I will post a comment to that effect in https://reviews.llvm.org/D59344.

Going to abandon these changes since it's effectively a duplicate.

[zoecarver]

@jloser Sorry about the duplication of code here. As for custom hash support, I already have a partial implementation of that just FYI. If you already have written one though, just let me know and I will abandon mine.

[jloser]

@zoecarver no worries; no I have not written one. Why do we need a custom hash implementation? We should be able to support contains with precomputed hashes without a custom hasher.

[zoecarver]

I was talking about P0920R2 (nothing really to do with contains). There is another patch I am waiting to be accepted before I put the finishing touches on it. I thought you mentioned it in the details, so I wanted to make sure we didn't make duplicated patches again :)

[jloser]

Ah right. Yeah, the commit does mention how this patch didn't touch the precalculated hash lookups at all. Now your comment makes sense. :)

libcxx/include/unordered_map

public:
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
     mapped_type& operator[](const key_type& k);
     mapped_type& operator[](key_type&& k);
 
     mapped_type&       at(const key_type& k);
     const mapped_type& at(const key_type& k) const;
 
+    bool contains(const key_type& k) const; // C++20
+
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);
     local_iterator       end(size_type n);
public:
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
     size_type count(const key_type& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
+    bool contains(const key_type& k) const; // C++20
+
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);
     local_iterator       end(size_type n);
#endif
     mapped_type& operator[](const key_type& __k);
 #ifndef _LIBCPP_CXX03_LANG
     mapped_type& operator[](key_type&& __k);
 #endif
 
     mapped_type&       at(const key_type& __k);
     const mapped_type& at(const key_type& __k) const;
 
+#if _LIBCPP_STD_VER > 17
+    _LIBCPP_INLINE_VISIBILITY
+    bool contains(const key_type& __k) const { return  __table_.find(__k) !=  __table_.end(); }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_size(size_type __n) const
         {return __table_.bucket_size(__n);}
#endif
     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
         {return __table_.__equal_range_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
         {return __table_.__equal_range_multi(__k);}
 
+#if _LIBCPP_STD_VER > 17
+    _LIBCPP_INLINE_VISIBILITY
+    bool contains(const key_type& __k) const
+        { return  __table_.find(__k) !=  __table_.end(); }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const _NOEXCEPT
         {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_size(size_type __n) const

libcxx/include/unordered_set

public:
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
     size_type count(const key_type& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
+    bool contains(const key_type& k) const; // C++20
+
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);
     local_iterator       end(size_type n);
public:
     key_equal key_eq() const;
 
     iterator       find(const key_type& k);
     const_iterator find(const key_type& k) const;
     size_type count(const key_type& k) const;
     pair<iterator, iterator>             equal_range(const key_type& k);
     pair<const_iterator, const_iterator> equal_range(const key_type& k) const;
 
+    bool contains(const key_type& k) const; // C++20
+
     size_type bucket_count() const noexcept;
     size_type max_bucket_count() const noexcept;
 
     size_type bucket_size(size_type n) const;
     size_type bucket(const key_type& k) const;
 
     local_iterator       begin(size_type n);
     local_iterator       end(size_type n);
#endif
     size_type count(const key_type& __k) const {return __table_.__count_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
         {return __table_.__equal_range_unique(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
         {return __table_.__equal_range_unique(__k);}
 
+#if _LIBCPP_STD_VER > 17
+    _LIBCPP_INLINE_VISIBILITY
+    bool contains(const key_type& __k) const
+        { return __table_.find(__k) != __table_.end(); }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
     _LIBCPP_INLINE_VISIBILITY
#endif
     size_type count(const key_type& __k) const {return __table_.__count_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<iterator, iterator>             equal_range(const key_type& __k)
         {return __table_.__equal_range_multi(__k);}
     _LIBCPP_INLINE_VISIBILITY
     pair<const_iterator, const_iterator> equal_range(const key_type& __k) const
         {return __table_.__equal_range_multi(__k);}
 
+#if _LIBCPP_STD_VER > 17
+    _LIBCPP_INLINE_VISIBILITY
+    bool contains(const key_type& __k) const
+        { return __table_.find(__k) != __table_.end(); }
+#endif
+
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_count() const _NOEXCEPT {return __table_.bucket_count();}
     _LIBCPP_INLINE_VISIBILITY
     size_type max_bucket_count() const _NOEXCEPT {return __table_.max_bucket_count();}
 
     _LIBCPP_INLINE_VISIBILITY
     size_type bucket_size(size_type __n) const {return __table_.bucket_size(__n);}
     _LIBCPP_INLINE_VISIBILITY

libcxx/test/std/containers/unord/unord.map/contains.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+// <unordered_map>
+
+// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
+//           class Alloc = allocator<pair<const Key, T>>>
+// class unordered_map
+
+// bool contains(const key_type& k) const;
+
+#include <unordered_map>
+#include <string>
+#include <cassert>
+
+int main(int, char**)
+{
+    std::unordered_map<int, std::string> c{};
+    assert(!c.contains(1));
+
+    c[1] = "one";
+    assert(c.contains(1));
+
+    return 0;
+}

libcxx/test/std/containers/unord/unord.multimap/contains.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+// <unordered_map>
+
+// template <class Key, class T, class Hash = hash<Key>, class Pred = equal_to<Key>,
+//           class Alloc = allocator<pair<const Key, T>>>
+// class unordered_multimap
+
+// bool contains(const key_type& k) const;
+
+#include <unordered_map>
+#include <string>
+#include <cassert>
+
+int main(int, char**)
+{
+    std::unordered_multimap<int, std::string> c{};
+    assert(!c.contains(1));
+
+    c.insert({1, "one"});
+    assert(c.contains(1));
+
+    return 0;
+}

libcxx/test/std/containers/unord/unord.multiset/contains.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+// <unordered_set>
+
+// template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
+//           class Alloc = allocator<Value>>
+// class unordered_multiset
+
+// bool contains(const key_type& k) const;
+
+#include <unordered_set>
+#include <cassert>
+
+int main(int, char**)
+{
+    std::unordered_multiset<int> c{};
+    assert(!c.contains(1));
+
+    c.insert(1);
+    assert(c.contains(1));
+
+    return 0;
+}

libcxx/test/std/containers/unord/unord.set/contains.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+// <unordered_set>
+
+// template <class Value, class Hash = hash<Value>, class Pred = equal_to<Value>,
+//           class Alloc = allocator<Value>>
+// class unordered_set
+
+// bool contains(const key_type& k) const;
+
+#include <unordered_set>
+#include <cassert>
+
+int main(int, char**)
+{
+    std::unordered_set<int> c{};
+    assert(!c.contains(1));
+
+    c.insert(1);
+    assert(c.contains(1));
+
+    return 0;
+}