STL algorithms: Why no additional interface for containers (additional to iterator pairs)?

Question

I'm wondering why the STL doesn't overload their algorithm functions such that I can call them by simply providing a container and not taking the more verbose way to pass begin + end iterators. I of course understand why we also want to use an iterator pair for processing subsequences of a container / array, however, almost all calls to these methods are using a whole container:

std::for_each(myVector.begin(), myVector.end(), doSomething);

I'd find it more convenient, readable and maintainable to just write

std::for_each(myVector, doSomething);

Is there a reason STL doesn't provide these overloads? [EDIT: I don't mean to replace the interface with this restricted one but to also provide a container-based iterface!] Do they introduce ambiguity? I'm thinking about something like this:

template<typename _Container, typename _Funct>
inline _Funct for_each(_Container c, _Funct f) {
    return for_each(begin(c), end(c), f);
}

Am I missing something?

Answer 1

They do introduce ambiguity for many algorithms. A lot of <algorithm> looks like

template<class iterator>
void do_something(iterator, iterator);

template<class iterator, class funct>
void do_something(iterator, iterator, funct);

If you add additional overloads

template<class container, class funct>
void do_something(container, funct);

the compiler will have some trouble figuring out what do_something(x, y) means. If x and y are of the same type, it will match both iterator = type and container = type, funct = type.^*)

C++11 tried to solve this with "concepts" that could recognize the difference between a container and an iterator. However, these "concepts" turned out to be too complicated to make it into the standard, so neither did these overloads.

^*) compilers disagree here, the Comeau compiler claims that it is ambiguous, g++ 4.5 and MSVC 10 calls the first function.

---

After an extremely long discussion in the comments, here is one example where it doesn't work as expected - using a container adapter that can also double as a predicate.

#include <iostream>
#include <vector>

template<class iterator>
void test(iterator, iterator)
{
   std::cout << "test iterator\n";
}

template<class iterator, class predicate>
void test(iterator, iterator, predicate)
{
   std::cout << "test iterator, predicate\n";
}

template<class container, class predicate>
void test(const container& cont, predicate compare)
{
   std::cout << "test container, predicate\n";

   test(cont.begin(), cont.end(), compare);
}

template<class container>
class adapter
{
public:
   typedef typename container::iterator   iterator;

   adapter(container* cont) : cont(cont)
   { }

   iterator begin() const
   { return cont->begin(); }

   iterator end() const
   { return cont->end(); }

   bool operator()(const iterator& one, const iterator& two)
   { return *one < *two; }

private:
   container* cont;
};

int main()
{
   std::vector<int>   v;

   adapter<std::vector<int>>   a(&v);

   test(a, a);

}

Output:

test iterator

http://ideone.com/wps2tZ

Answer 2

Unfortunately, this is a far more generic problem; namely, that iterators were designed to beat those crappy C APIs and Java-style "Put the algorithms as methods of each individual container" solutions. They are the first-generation generic solution and there's no surprise that, on reflection, they were not as good as other possible generic solutions obtainable after we spend twenty years thinking about it.

Adding these container overloads would be just band-aiding over a tiny part of the problem space; and it might even make things worse in the future. The solution is ranges, which C++ is looking to introduce ASAP.

Answer 3

To understand that I think one must have to understand the philosophy of C++ algorithms. Lets ask this question first:

Why C++ algorithms are implemented as free functions instead of member functions?

Well the answer is pretty much simple : to avoid implementation explosions. Suppose you have M containers and N algorithms, and if you implement them as members of the containers, then there will be M*N implementations. There are two (related) problems in this approach:

• First, it doesn't make use of code reuse. Most of the implementations will be repeated.
• Second, implementation explosions, which is a direct consequence of the above.

C++ solves these issues by implementing them as free functions, so that you have only N implementations. Each of the algorithm that operates on a container takes a pair of iterators, that defines the range. If you want overloads that take container, instead of pair of iterators, then the Standard have to provide such overloads for each of the algorithm, and there will be 2*N implementations which pretty much defeat the very purpose why C++ has separated the algorithms from the containers in the first place, and half of these functions don't do anything which cannot be done by the other half.

So I don't think it is that much an issue. Just to avoid one single argument, why implement N more functions (which also impose some restriction on its usage such as you cannot pass pointers to it)? However, if programmers want such functions in their utility, they can implement them anytime along with many others based on the Standard algorithm!

---

You commented:

Well, the 2*N implementations are in fact only N implementations. The other N ones are inlined overloads which directly call the "real" version of the algorithm, so they are a header-only thing. Providing container overloads doesn't defeat the purpose to separate algorithms from containers, as (as you can see in my example) they can use templates to handle all types of containers.

Based on this logic, one can very well argue for M*N algorithms. So make them member functions too (and call the free functions internally)? I'm sure many OOP guys would prefer

auto result = container.accumulate(val);

over

auto result = std::accumulate(container.begin(), container.end(), val);

Answer 4

Here is a relevant answer from Herb Sutter's blog: Why no container-based algorithms. It shows counterexamples just like Bo Persson did in his answer above.

Answer 5

There is a Range Operators library with intention to fix that. Verbosity was cut several times over.

Your example would look something like this:

auto newVector = myVector * doSomething;

Yes, doSomething - is without parenthesis.

Familiar idiom from shell (with std algorithm):

auto t = vector<int>{3,2,1,4} | sort | unique; 

Answer 6

It should be pointed out that it's very easy to define your own trivial wrappers to add containerized versions.

For example:

template<typename Container, typename Func>
Func for_each(Container& c, Func f) {
    return std::for_each(c.begin(), c.end(), f);
}

Now you can make the simple call you want. There's no ambiguity because your wrappers aren't in the std namespace. You can define overloads that take const Container&. If you want versions that call the C++-11 const iterator methods (e.g. cbegin()), I think you'll need to name the wrapper differently. I use for_each_const.

Answer 7

Obviously, as other users mentioned, it's a tricky problem, so unfortunately it's been a long time and there's still no solution in the standard library. There are, however, already range libraries available such as Boost::Range and the one in the Adobe Source Libraries that provide not only the simplicity of the interface you describe in your question, but some fancier features as well.

Your example works perfectly with Boost (we are using namespace boost::range::adaptors below):

boost::for_each(myVector, doSomething);

We can also slice myVector quickly and easily:

boost::for_each(myVector | sliced(10, 20), doSomething)

We can even zip myVector with another, filter by a predicate, and sample every other element of the resulting pairs in a single, simple statement (this requires that you unpack in doSomethingElse the tuples produced by boost::combined):

boost::for_each( boost::combined(myVector, myOtherVector) | strided(2), doSomethingElse)