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

On 12/18/24 16:01, Ivan Matek wrote:

On Wed, Dec 18, 2024 at 10:33 AM Andrey Semashev via Boost mailto:boost@lists.boost.org> 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.