Why there are no overloads of find/lower_bound for std::map and no overload of sort for std::list?

Question

I know that you should never use std::find(some_map.begin(), some_map.end()) or std::lower_bound, because it will take linear time instead of logarithmic provided by some_map.lower_bound. Similar thing happens with std::list: there is std::list::sort function for sorting, but you're unable to call std::sort(some_list.begin(), some_list.end()), because iterators are not random-access.

However, std::swap, for instance, has overloads for standard containers, so that call of swap(some_map, other_map) takes O(1), not O(n). Why doesn't C++ standard give us specialized versions of lower_bound and find for maps and sets? Is there are deep reason?

Answer 1

I don't think there's any deep reason, but it's more philosophical than anything. The free function forms of standard algorithms, including the ones you mention, take iterator pairs indicating the range over which they'll traverse. There's no way for the algorithm to determine the type of the underlying container from these iterators.

Providing specializations, or overloads, would be a departure from this model since you'd have to pass the container itself to the algorithm.

swap is different because it takes instances of the types involved as arguments, and not just iterators.

Answer 2

The rule followed by the STL is that the free-function algorithms operate on iterators and are generic, not caring about the type of range the iterators belong to (other than the iterator category). If a particular container type can implement an operation more efficiently than using std::algo(cont.begin(), cont.end()) then that operation is provided as a member function of the container and called as cont.algo().

So you have std::map<>::lower_bound() and std::map<>::find() and std::list<>::sort().