1. Changelog
-
R1 (post-St Louis 2024):
-
Minor wording nits (thanks Tim Song!)
-
Add feature test macro
-
Add SG9’s naming ideas; also discuss the editorial section-naming question
-
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 and alternative names
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"]
SG9 Ranges discussed P2848R0 in St Louis (June 2024). Two participants expressed discomfort with "is uniqued"
as a verb form (although at least two others expressed that it was surely the correct name, given the names
nearby it semantically). Alternatives proposed, without full discussion, were
and
.
We believe that
is a dangerously wrong name, because the algorithm specifically does not
check whether the range is in some sense "unique," and certainly does not check whether the range contains
no duplicates. It checks specifically for adjacent duplicates, i.e., it checks that the range has had the
mutating algorithm
performed on it.
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
Note: The three other families are organized in umbrella sections:
[alg.partitions] contains
,
,
, and others, with no internal divisions.
[alg.sort] is internally divided into [sort]
, [is.sorted]
and
, and others.
[alg.heap.operations] is internally divided into [make.heap]
, [is.heap]
and
, and others.
Should we therefore extract
from [alg.nonmodifying]>[alg.adjacent.find] and
from [alg.modifying.operations]>[alg.unique]
into a new umbrella section [alg.uniquing] internally divided into [alg.unique], [alg.is.uniqued], and [alg.adjacent.find]?
That is an editorial question to be decided by LWG during wording review. The proposed wording below doesn’t do it (yet).
4.1. Header < algorithm >
synopsis [algorithm.syn]
Modify [algorithm.syn] as follows:
constexpr borrowed_iterator_t < R > adjacent_find ( R && r , Pred pred = {}, Proj proj = {}); } // [alg.is.uniqued], is uniqued template < class ForwardIterator > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last ); template < class ForwardIterator , class BinaryPredicate > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); template < class ExecutionPolicy , class ForwardIterator > bool is_uniqued ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] ForwardIterator first , ForwardIterator last ); template < class ExecutionPolicy , class ForwardIterator , class BinaryPredicate > bool is_uniqued ( ExecutionPolicy && exec , // see [algorithms.parallel.overloads] ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); namespace ranges { 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 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 is_uniqued ( R && r , Pred pred = {}, Proj proj = {}); } // [alg.count], count template < class InputIterator , class T = iterator_traits < InputIterator >:: value_type > constexpr typename iterator_traits < InputIterator >:: difference_type count ( InputIterator first , InputIterator last , const T & value );
4.2. is_uniqued
[alg.is.uniqued]
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).
Add this new section between [alg.adjacent.find] and [alg.count].
template < class ForwardIterator > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last ); Returns:
.
adjacent_find ( first , last ) == last template < class ExecutionPolicy , class ForwardIterator > bool is_uniqued ( ExecutionPolicy && exec , ForwardIterator first , ForwardIterator last ); Returns:
.
adjacent_find ( std :: forward < ExecutionPolicy > ( exec ), first , last ) == last template < class ForwardIterator , class BinaryPredicate > constexpr bool is_uniqued ( ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); Returns:
.
adjacent_find ( first , last , pred ) == last template < class ExecutionPolicy , class ForwardIterator , class BinaryPredicate > bool is_uniqued ( ExecutionPolicy && exec , ForwardIterator first , ForwardIterator last , BinaryPredicate pred ); Returns:
.
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 = {}); Returns:
.
ranges :: adjacent_find ( first , last , pred , proj ) == last
4.3. Header < version >
synopsis [version.syn]
Modify [version.syn] as follows:
#define __cpp_lib_is_swappable 201603L // freestanding, also in <type_traits> #define __cpp_lib_is_uniqued 20XXYYL // also in <algorithm> #define __cpp_lib_is_within_lifetime 202306L // also in <type_traits>