There are many useful functions in <algorithm>, but all of them operate on “sequences” – pairs of iterators. E.g., if I have a container and like to run std::accumulate on it, I need to write:
std::vector<int> myContainer = ...;
int sum = std::accumulate(myContainer.begin(), myContainer.end(), 0);
When all I intend to do is:
int sum = std::accumulate(myContainer, 0);
Which is a bit more readable and clearer, in my eyes.
Now I can see that there might be cases where you’d only want to operate on parts of a container, so it’s definitely useful to have the option of passing ranges. But at least in my experience, that’s a rare special case. I’ll usually want to operate on whole containers.
It’s easy to write a wrapper function which takes a container and calls begin() and end() on it, but such convenience functions are not included in the standard library.
I’d like to know the reasoning behind this STL design choice.
2
… it’s definitely useful to have the option of passing ranges. But at least in my experience, that’s a rare special case. I’ll usually want to operate on whole containers
It may be a rare special case in your experience, but in reality the whole container is the special case, and the arbitrary range is the general case.
You’ve already noticed that you can implement the whole container case using the current interface, but you can’t do the converse.
So, the library-writer had a choice between implementing two interfaces up front, or only implementing one which still covers all cases.
It’s easy to write a wrapper function which takes a container and calls begin() and end() on it, but such convenience functions are not included in the standard library
True, especially since the free functions std::begin and std::end are now included.
So, let’s say the library provides the convenience overload:
template <typename Container>
void sort(Container &c) {
sort(begin(c), end(c));
}
now it also needs to provide the equivalent overload taking a comparison functor, and we need to provide the equivalents for every other algorithm.
But we at least covered every case where we want to operate on a full container, right? Well, not quite. Consider
std::for_each(c.rbegin(), c.rend(), foo);
If we want to handle operating backwards on containers, we need another method (or pair of methods) per existing algorithm.
So, the range-based approach is more general in the simple sense that:
- it can do everything the whole-container version can
- the whole-container approach doubles or triples the number of overloads required, while still being less powerful
- the range-based algorithms are also composable (you can stack or chain iterator adaptors, although this is more commonly done in functional languages and Python)
There’s another valid reason, of course, which is that it was already a lot of work to get the STL standardized, and inflating it with convenience wrappers before it had been widely used wouldn’t be a great use of limited committee time. If you’re interested, you can find Stepanov & Lee’s technical report here
As mentioned in comments, Boost.Range provides a newer approach without requiring changes to the standard.
15
Turns out there’s an article by Herb Sutter on this very subject.
Basically, the problem is overload ambiguity. Given the following:
template<typename Iter>
void sort( Iter, Iter ); // 1
template<typename Iter, typename Pred>
void sort( Iter, Iter, Pred ); // 2
And adding the following:
template<typename Container>
void sort( Container& ); // 3
template<typename Container, typename Pred>
void sort( Container&, Pred ); // 4
Will make it hard to distinguish 4 and 1 properly.
Concepts, as proposed but ultimately not included in C++ 0x, would have solved that, and it’s also possible to circumvent it using enable_if. For some of the algorithms, it’s no problem at all. But they decided against it.
Now after reading all the comments and answers here, I think range objects would be the best solution. I think I’ll have a look at Boost.Range.
3
Basically a legacy decision. The iterator concept is modeled on pointers, but containers aren’t modeled on arrays. Furthermore, since arrays are hard to pass (need a non-type template parameter for length, in general), quite often a function only has pointers available.
But yeah, in hindsight the decision is wrong. We would have been better off with a range object constructible from either begin/end or begin/length; now we have multiple _n suffixed algorithms instead.
1
Adding them would gain you no power (you can already do the entire container by calling .begin() and .end() yourself), and it would add one more thing to the library that has to be properly specified, added to the libraries by the vendors, tested, maintained, etc, etc.
In short, it’s probably not there because it’s not worth the trouble to maintain a set of extra templates just to save whole-container users from typing one extra function call parameter.
2
The Abseil library (used by Google) provides container-based versions of algorithmic functions within the C++ standard library.
https://source.chromium.org/chromium/chromium/src/+/main:third_party/abseil-cpp/absl/algorithm/container.h
(I think) This is because the original iterator-based STL algorithm API is indeed inconvenient and less readable (sometimes). And that’s why Google provides a container-based wrapper.
3