| Document number: | P0458R0 |
| Date: | 2016-10-09 |
| Project: | LEWG |
| Reply-to: | Mikhail Maltsev <maltsevm@gmail.com> |
This paper proposes to add a member function contains, which checks, whether or not a given element exists in a container, to standard associative containers.
The common idiom for checking whether an element exists in an associative container involves doing a lookup and checking the returned iterator:
if (some_set.find(element) != some_set.end()) {
// ...
}
This idiom suffers from excessive boilerplate code and is inferior to if (some_set.contains(element)) in terms of expressing intent in code.
It is also not obvious for beginners. Quoting a question from Stack Overflow [1]:
How to check if std::map contains a key without doing insert?
The only way I have found to check for duplicates is by inserting and checking the std::pair.second for false, but the problem is that this still inserts something if the key is unused, whereas what I want is a map.contains(key); function.
Another (a little less common) way to perform the same task is using the count method. Unfortunately, it's use is suboptimal for multisets and multimaps (it has greater complexity than find). In some sense it is similar to the size method of the standard library containers: it does not replace the empty method.
The idea of this proposal is not new. It was discussed on "std-proposals" forum [2], but unfortunately that discussion did not result in a formal proposal.
Qt library includes QSet and QMap class templates, similar to the standard ones, but they also provide contains member function [3].
As Thiago Macieira (one of Qt developers) pointed out in [2], in Qt itself, contains method is used much more widely than find.
Arguably, for sets (std::set and std::unordered_set) testing a key for existence is much more common than using the find method for any other purpose, yet it has less obvious API.
contains could as well be added as a free function. One might even argue, that decoupling of algorithms and containers is one of the core principles of the standard library. Nevertheless, lookup by key is inherent to associative containers, i.e. find member function is not equivalent to std::find. So, if we were to add std::contains, it should work on ranges and be equivalent to std::find(first, last, element) != last for consistency.
Another (non-)option would be to make iterators returned by associative
containers contextually convertible to bool, i.e. make
if (some_set.find(element))
equivalent to
if (some_set.find(element) != some_set.end())
In some implementations adding such a conversion would be possible without breaking the ABI. For example, this would definitely be possible for unordered associative containers in GCC (libstdc++'s unordered_set::iterator consists of a single pointer and for unordered_set::end this pointer is nullptr). Unfortunately this might not be the case in general, so this option is not proposed
In [associative.reqmts], "Table 86 — Associative container requirements (in addition to container)", add:
| Expression | Return type | Assertion/note pre-/post-condition | Complexity |
|---|---|---|---|
| b.contains(k) | bool | equivalent to b.find(k) != b.end() | logarithmic |
In [unord.req], "Table 87 — Unordered associative container requirements (in addition to container)", add:
| Expression | Return type | Assertion/note pre-/post-condition | Complexity |
|---|---|---|---|
| b.contains(k) | bool | equivalent to b.find(k) != b.end() | Average case O(1), worst case O(b.size()) |
In [map.overview], in section "map operations" add:
bool contains(const key_type& x) const; template <class K> bool contains(const K& x) const;
In [multimap.overview], in section "map operations" add:
bool contains(const key_type& x) const; template <class K> bool contains(const K& x) const;
In [set.overview], in section "set operations" add:
bool contains(const key_type& x); template <class K> bool contains(const K& x) const;
In [multiset.overview], in section "set operations" add:
bool contains(const key_type& x); template <class K> bool contains(const K& x) const;
In [unord.map.overview], in section "map operations" add:
bool contains(const key_type& k) const;
In [unord.multimap.overview], in section "map operations" add:
bool contains(const key_type& k) const;
In [unord.set.overview], in section "set operations" add:
bool contains(const key_type& k) const;
In [unord.multiset.overview], in section "set operations" add:
bool contains(const key_type& k) const;