C++ Logo

std-proposals

Advanced search

[std-proposals] We should allow to specialize algorithms

From: Nikl Kelbon <kelbonage_at_[hidden]>
Date: Tue, 12 Dec 2023 13:34:06 +0400
There are many algorithms, which may be more effective on concrete
container/range, but there are no functionality to specialize them.
Examples:
* lower_bound/binary_search/upper_bound with map/set/multimap/multiset:
Now, std::lower_bound on map is O(N) (!!!) which is rly scary and easy to
miss on code review

* destroy range of jthread
Let some code:

void foo() { vector<jthread> vec;
(add N jthreads to vec) }

This is uneffective code. Destructor of 'vec' will execute sequentially
.request_stop(). join() for each jthread in it. So, all threads will be
exected while we a blocked on .join()

More effective way: call .request_stop() on all jthreads *before* calling
.join() in second loop.
We can specialize 'destroy' algorithm for this (all containers use it)

* for_each unseq of map
Consider this code:
auto bar(std::map<int, int>& m, auto fn) {
    return std::accumulate(begin(m), end(m), fn, 0);
}

This is also uneffective. Iteration on map is a hard thing, iterating to
next element may cost O(logN) time, iterating over all map is ~ O(6*N).
While 'fn' is not dependent on order we can use unsequenced policy:of
'for_each' on map, which is may be specialized to be more effective (for
example use recursion instead of iterating and execute in O(1*N) instead of
6*N

Same logic can be applied to non standard ring buffers and other containers

* sort on list
'list' is sortable, it has method 'sort', but std::ranges::sort do not work
for it (not random access range). It can be confusing for new programmers
and may produce errors in template code. Why we not specialize sort for
list?

Received on 2023-12-12 09:34:20