Re: Adding optional<T&> find like method to associative containers in boost.

From: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2024-12-18 13:19:03

On 12/18/24 16:01, Ivan Matek wrote:
> On Wed, Dec 18, 2024 at 10:33 AM Andrey Semashev via Boost
> <boost_at_[hidden] <mailto:boost_at_[hidden]>> wrote:
> 
>     On 12/18/24 12:12, Ivan Matek via Boost wrote:
>     std::list::size() had linear complexity in C++03 and std::list::empty()
>     was constant. It was definitely a reason to have it separate from
>     size().
> 
> I am not really convinced that this was motivation. I am not aware of C+
> +98 design discussions that are available online so hard to check.

I'm not saying this was *the* motivation, I'm saying this is definitely
*a* reason to have a dedicated empty(). A fairly significant one, IMHO.

> For std::list sure, but why for every other container? There could have
> easily been std::empty that does std::true_type/
> std::false_type equivalent of if constexpr using member empty if
> available, else compares size() to 0.
> But maybe during C++98 design time there was no use of SFINAE in STL? 

Let's say the support for SFINAE in compilers was not universal. Tag
dispatching is possible, but detecting a member function could be
problematic.

>     contains() is a specialized algorithm that is not equivalent to
>     `std::find() != end()` in each container's case. Historically, such
>     specialized algorithms were implemented as members, while the generic
>     algorithms were provided as free functions. Another such example is
>     swap().
> 
> I am aware contains() can be implemented faster, e.g. you could have
> SIMD logic for integer set where for example 8 integers are grouped
> together so you can compare them all with lookup value.
> But I do not believe this is motivation. contains() replaces  count()!= 0. 
> P0458 <https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/
> p0458r2.html> is pretty clear about contains() motivation:
> 
>     [...]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.

Yes, the motivation you quoted sounds reasonable, and it also applies to
empty().

However, I was talking of something else. contains() is not the best
example for it, but e.g. find() is. In order to implement this operation
efficiently, one has to rely on implementation details of the container.
For tree-based containers, it has to traverse the tree branches rather
than a linear view of the container. For hash-based containers, it has
to access the bucket list. And so on. Similarly, swap() members allow to
swap container instances without creating a copy of the container (which
would be needed in C++03 as there were no move constructors back then).
This requirement of knowledge of the container internals makes creating
a free function implementation impractical.