1. Changelog
-
R0:
-
Initial revision.
-
2. Motivation and solution
The "classic STL" provides the following sets of related algorithms:
-
(returns iterator),is_sorted_until
(i.e.is_sorted
)is_sorted_until == end () -
(returns iterator),is_heap_until
(i.e.is_heap
)is_heap_until == end () -
(returns iterator), [blank] (i.e.adjacent_find
)adjacent_find == end () -
(returns iterators),mismatch
(i.e.equal
)mismatch == { end (), end ()} -
(returns iterator),search
(i.e.contains_subrange
)search != end ()
And these, too:
-
(i.e. make the input range satisfy [blank])unique
The missing algorithm is what would fill in the blank in the following invariant assertions:
std :: set < K > s = { ... }; std :: multiset < K > ms = { ... }; std :: map < K , V > m = { ... }; std :: multimap < K , V > mm = { ... }; std :: unordered_set < K > us = { ... }; std :: unordered_map < K , V > um = { ... }; template < class M , class P = M :: value_type > auto ValueEq ( const M & m ) { return [ eq = m . key_eq ()]( const P & a , const P & b ) { return eq ( a . first , b . first ); }; } assert ( std :: is_sorted ( s . begin (), s . end (), s . value_comp ())); assert ( std :: is_sorted ( ms . begin (), ms . end (), ms . value_comp ())); assert ( std :: is_sorted ( m . begin (), m . end (), m . value_comp ())); assert ( std :: is_sorted ( mm . begin (), mm . end (), mm . value_comp ())); assert ( std :: is______ed ( s . begin (), s . end (), std :: not_fn ( s . value_comp ()))); assert ( std :: is______ed ( m . begin (), m . end (), std :: not_fn ( m . value_comp ()))); assert ( std :: is______ed ( us . begin (), us . end (), us . key_eq ())); assert ( std :: is______ed ( um . begin (), um . end (), ValueEq ( um )));
We propose that this algorithm should exist, and should be spelled
.
2.1. Prior art in other languages
The C++ STL verb
is derived from Unix’s
filter,
which filters adjacent matching lines from the input.
The Swift language provides a transformation named
(corresponding to C++'s
), and a transformation named
.
The latter doesn’t quite correspond to the C++/Unix notion of "uniquing": it removes even non-adjacent
duplicates, by putting all the elements into a hashset and then pulling them out again.
Still, this is prior art for the idea of treating "unique, uniqued, uniquing" as a verb.
let animals = [ "dog" , "pig" , "cat" , "ox" , "dog" , "cat" ] let u = Array ( animals . uniqued ()) // 'u' is now ["dog", "pig", "cat", "ox"]
2.2. Should we require pred
to be an equivalence relation?
Currently,
has undefined behavior
if you pass it a predicate that is not an equivalence relation. Fortunately,
does not.
For example, the author of
might write:
container_type c ; key_compare compare ; std :: sort ( c . begin (), c . end (), compare ); c . erase ( std :: unique ( c . begin (), c . end (), std :: not_fn ( compare )), c . end ()); // UB assert ( std :: is_sorted ( c . begin (), c . end (), compare )); assert ( std :: adjacent_find ( c . begin (), c . end (), std :: not_fn ( compare )) == c . end ()); // OK
Both before and after this proposal, the line marked "UB" has undefined behavior (although
it will generally work in practice). We don’t propose to change the precondition
of
. The line marked "OK" has well-defined behavior. we don’t propose to
change the precondition of
either.
After this proposal, the following shorter line will be equivalent to the line marked "OK":
assert ( std :: is_uniqued ( c . begin (), c . end (), std :: not_fn ( compare ))); // OK
That is, the new algorithm
will have the same precondition as the
existing
algorithm (in terms of which it is defined). This differs
from the precondition of
, which is a little surprising, but we believe
it’s the correct choice.
3. Implementation experience
Arthur has implemented
and
in his fork of libc++;
see commit 490536e.
This implementation is available on Godbolt Compiler Explorer.
4. Proposed wording relative to C++23
Add a new section after [alg.adjacent.find].
Note: This wording is copied straight from [is.sorted],
with these mechanical replacements:
becomes
,
becomes
,
becomes
(cf. [alg.adjacent.find]),
becomes
(ditto), and
becomes
(ditto).
4.1. is_uniqued
[alg.is.uniqued]
template < class ForwardIterator > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last ); Effects: Equivalent to:
return adjacent_find ( first , last ) == last ; template < class ExecutionPolicy , class ForwardIterator > bool is_uniqued ( ExecutionPolicy && exec , ForwardIterator first , ForwardIterator last ); Effects: Equivalent to:
return adjacent_find ( std :: forward < ExecutionPolicy > ( exec ), first , last ) == last ; template < class ForwardIterator , class BinaryPredicate > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); Effects: Equivalent to:
return adjacent_find ( first , last , pred ) == last ; template < class ExecutionPolicy , class ForwardIterator , class BinaryPredicate > bool is_uniqued ( ExecutionPolicy && exec , ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); Effects: Equivalent to:
return adjacent_find ( std :: forward < ExecutionPolicy > ( exec ), first , last , pred ) == last ; template < forward_iterator I , sentinel_for < I > S , class Proj = identity , indirect_binary_predicate < projected < I , Proj > , projected < I , Proj >> Pred = ranges :: equal_to > constexpr bool ranges :: is_uniqued ( I first , S last , Pred pred = {}, Proj proj = {}); template < forward_range R , class Proj = identity , indirect_binary_predicate < projected < iterator_t < R > , Proj > , projected < iterator_t < R > , Proj >> Pred = ranges :: equal_to > constexpr bool ranges :: is_uniqued ( R && r , Pred pred = {}, Proj proj = {}); Effects: Equivalent to:
return ranges :: adjacent_find ( first , last , pred , proj ) == last ;