57

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.

lethal-guitar
  • 2,065
  • 2
  • 16
  • 19
  • 8
    Does the STL typically provide convenience wrappers, or does it follow the older C++ here's-the-tools-now-go-shoot-yourself-in-the-foot policy? – Kilian Foth Mar 05 '14 at 13:19
  • 2
    For the record: rather than write your own wrapper you should use the algorithm wrappers in Boost.Range; in this case, [`boost::accumulate`](http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/algorithms/numeric/accumulate.html) – ecatmur Mar 05 '14 at 15:14

5 Answers5

41

... 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.

Useless
  • 12,380
  • 2
  • 34
  • 46
  • 11
    I don't think anyone, OP included, is suggesting adding overloads for every single special case. Even if "whole container" was less common than "an arbitrary range", it's definitely far more common than "whole container, reversed". Restrict it to `f(c.begin(), c.end(), ...)`, and perhaps just the most commonly used overload (however you determine that) to prevent doubling the number of overloads. Also, iterator adapters are completely orthogonal (as you note, they work fine in Python, whose iterators work very differently and don't have most of the power you talk about). –  Mar 05 '14 at 14:56
  • 3
    I agree the _whole container, forwards_ case is very common, but wanted to point out that it's a much smaller subset of possible uses than the question suggested. Specifically because the choice isn't between whole container and partial container, but between whole container and partial container, possibly reversed or otherwise adapted. And I think it's fair to suggest that the _perceived_ complexity of using adapters is greater, if you also have to change your algorithm overload. – Useless Mar 05 '14 at 15:05
  • 27
    Note the container version *would* cover all cases if the STL offered a range object; e.g. `std::sort(std::range(start, stop))`. –  Mar 05 '14 at 15:19
  • 3
    On the contrary: the composable functional algorithms (like map and filter) take a single object that represents a collection and return a single object, they certainly don't use anything resembling a pair of iterators. – svick Mar 05 '14 at 15:22
  • 4
    a macro could do this: `#define MAKE_RANGE(container) (container).begin(), (container).end()` – ratchet freak Mar 05 '14 at 16:09
  • 1
    @Hurkyl that's true, and the motivation behind [Boost.Range](http://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/introduction.html). – Useless Mar 05 '14 at 17:09
  • @svick that single object may _reperesent_ a collection (or, again, some operation over a collection), but the OP was asking for it to _be_ a collection, which is different. The range approach seems like a more reasonable compromise in C++ than some lazily-evaluated collection facade. – Useless Mar 05 '14 at 17:10
  • 1
    @Useless I think the OP was asking to be able to use the collection directly. If all collections in C++ derived from or were implicitly castable to the `std::range` proposed above, that would still fit. (.Net does exactly that, all collections implement the `IEnumerable` interface and functional algorithms work with that.) I think that a range is quite different abstraction than an iterator and one that the C++ library doesn't recognize. – svick Mar 05 '14 at 17:44
  • 3
    @delnan Saying that Python iterators "don't have most of the power" talked about is a misleading statement. The power of Python iterators lies in their integration with the language, which includes constructs for easy construction of simple to complex iterators (the most powerful of which would probably be generators and generator expressions, though the standard library's `itertools` module provides a lot of nice convenience functions for common composition patterns too). (This applies to plenty of other languages with similar design principles, of course. diff. iterators != weaker iterators) – JAB Mar 05 '14 at 19:39
  • 1
    @JAB I know perfectly well just how useful Python's iterators, generators, etc. are, I use them every day. But Python only has the most humble member of C++'s iterator zoo, `Iterator`. No output iterators, no bidirectional iterator, random access iterators. What Python calls an iterator is simply much more narrow, many things C++ iterators do have no standardized Python equivalent. None of this diminishes its usefulness, quite the opposite, the simplicity makes it more effective in my experience, but it's still less general. –  Mar 05 '14 at 19:49
  • "already a lot of work to get the STL standardized" - ok, now that makes sense. Never thought about it that way.. – lethal-guitar Mar 05 '14 at 22:48
  • 1
    @delnan: That's because those things aren't really iterators, they're just kinds of views onto a collection. The power of an iterator comes from having one representation that can give you access to any kind of collection, be it ordered, unordered, finite, infinite, lazy, strict, local, remote, whatever. A "random access iterator" is just a proxy. Other languages don't *lack* those features, they just have other names for them. – Phoshi Mar 06 '14 at 14:06
  • 1
    I think this answer misses the point. As someone with little C++ background, the whole "pass two separate but totally related things around everywhere" notion is *very* odd. One could envision a design in which you have "slice" types, that present a collection interface over a portion of an existing collection. If you want to operate on your whole collection, just use that. If you want to operate over a slice of it, grab a slice and pass that into your algorithm. – Alexander Oct 08 '19 at 02:05
  • With respect @Alexander, I think this comment misses the point. The question I answered was about why the library doesn't operate on whole containers. I have _already_ agreed that there are good arguments for preferring ranges, or slices - but the question wasn't asking about those. Anyway, we can agree they're better while still understanding that they didn't meet the goals or constraints of standardizing C++98. – Useless Oct 08 '19 at 08:41
  • @Useless Upon reading that again, good point. I concur – Alexander Oct 08 '19 at 15:01
22

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.

lethal-guitar
  • 2,065
  • 2
  • 16
  • 19
  • 1
    Well, using just a `typename Iter` seems to be too duck-typed for a strict language. I would prefer e.g. `template void sort(typename Container::iterator, typename Container::iterator); // 1` and `template – Vlad Mar 10 '14 at 19:09
  • 1
    @Vlad: Unfortunately, this will not work for plain old arrays, as there is no `T[]::iterator` available. Also, proper iterator isn't obliged to be a nested type of any collection, it's enough to define [`std::iterator_traits`](http://en.cppreference.com/w/cpp/iterator/iterator_traits). – firegurafiku Oct 25 '15 at 17:50
  • @firegurafiku: Well, arrays are easy to special-case with some basic TMP tricks. – Vlad Oct 25 '15 at 18:12
14

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.

MSalters
  • 8,692
  • 1
  • 20
  • 32
5

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.

Michael Kohne
  • 10,038
  • 1
  • 36
  • 45
  • 10
    It wouldn't gain me power, that's true - but in the end, neither does `std::getline`, and still, it's in the library. One could go so far as to say that extended control structures don't gain me power, as I could do everything using only `if` and `goto`. Yeah, unfair comparison, I know ;) I think I can understand the specification/implementation/maintenance burden somehow, but it's only a tiny wrapper we're talking about here, so.. – lethal-guitar Mar 05 '14 at 15:04
  • A tiny wrapper costs nothing to code and maybe it does not make any sense to be in the library. – ebasconp Mar 05 '14 at 22:15
-1

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.

Firegun
  • 131
  • 4
  • 1
    How does this answer the question? – Dominique Jul 31 '23 at 06:34
  • Google provides convenience wrappers for those STL functions. This indicates whatever reason behind this STL design choice of not providing a convenient wrapper is not solid. If I have to say, it is due to either laziness or minimalism – Firegun Jul 31 '23 at 07:41
  • Argue that, and use the wrappers as a point to underscore it. Just linking the lib and letting us guess what you mean isn't an answer. No, the comment is not part of the answer, [edit]. – Deduplicator Jul 31 '23 at 15:48
  • thanks! updated – Firegun Aug 01 '23 at 06:38