Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
3  
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 5 at 13:19
1  
For the record: rather than write your own wrapper you should use the algorithm wrappers in Boost.Range; in this case, boost::accumulate –  ecatmur Mar 5 at 15:14

4 Answers 4

up vote 17 down vote accepted

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

As mentioned in comments, Boost.Range provides a newer approach without requiring changes to the standard.

share|improve this answer
2  
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). –  delnan Mar 5 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 5 at 15:05
6  
Note the container version would cover all cases if the STL offered a range object; e.g. std::sort(std::range(start, stop)). –  Hurkyl Mar 5 at 15:19
    
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 5 at 15:22
1  
a macro could do this: #define MAKE_RANGE(container) (container).begin(), (container).end() </jk> –  ratchet freak Mar 5 at 16:09

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.

share|improve this answer

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.

share|improve this answer
5  
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 5 at 15:04
    
A tiny wrapper costs nothing to code and maybe it does not make any sense to be in the library. –  oopscene Mar 5 at 22: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.

share|improve this answer
    
Well, using just a typename Iter seems to be too duck-typed for a strict language. I would prefer e.g. template<typename Container> void sort(typename Container::iterator, typename Container::iterator); // 1 and template<template<class> Container, typename T> void sort( Container<T>&, std::function<bool(const T&)> ); // 4 etc. (which would perhaps solve the ambiguity problem) –  Vlad Mar 10 at 19:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.