STL Algorithms: Why is there no additional interface for containers (in addition to pairs of iterators)?

Question

I am wondering why STL does not overload its algorithm functions, so I can call them just by providing a container and not taking a more detailed way to pass begin + end iterators. Of course, I understand why we also want to use a pair of iterators to process the subsequences of the container / array, however, almost all calls to these methods use the whole container:

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

I would find it more convenient, easy to read and easy to write

 std::for_each(myVector, doSomething); 

Is there a reason STL does not provide these overloads ? [EDIT: I do not want to replace the interface with this limited one, but also provide a container platform!] Do they introduce ambiguity? I am thinking of something like this:

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

Did I miss something?

Answer 1

They do 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 extra overloads

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

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

C ++ 11 tried to solve this problem with “concepts” that could recognize the difference between a container and an iterator. However, these "concepts" turned out to be too complex to turn it into a standard, therefore, these overloads were not.

^{*) the} compilers do not agree with this, the Comeau compiler claims that it is ambiguous, g ++ 4.5 and MSVC 10 calls the first function.

---

After an extremely lengthy discussion of comments, here is one example where it does not work as expected - using a container adapter, which can also be 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 much more general problem; namely, that iterators were designed to defeat these crap APIs and the Java-style "Put algorithms as methods of each individual container." This is a universal solution of the first generation, and it is not surprising that when reflected, they were not as good as other possible general solutions that could be obtained after we spent twenty years thinking about it.

Adding these container overloads would be just bandwidth support in a tiny fraction of the problem space; and this may even worsen the situation in the future. The solution is the ranges that C ++ wants to present as soon as possible.

Answer 3

To understand what I think, you need to understand the philosophy of C ++ algorithms. Let's first ask this question:

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

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

• First, it does not use code reuse. Most implementations will be repeated.
• Secondly, explosions of implementation, which is a direct consequence of the foregoing.

C ++ solves these problems by implementing them as free functions, so you only have N implementations. Each of the algorithms running on the container accepts a pair of iterators that define the range. If you need overloads that accept a container, and not a couple of iterators, then the Standard should provide such overloads for each of the algorithms, and 2*N implementations will be implemented that will largely defeat the very reason why C ++ separated the algorithms from containers first of all, and half of these functions does nothing that cannot be done by the other half.

Therefore, I do not think this is such a problem. To avoid one single argument, why implement N more functions (which also impose some restrictions on its use, for example, you cannot pass pointers to it)? However, if programmers need such functions in their utility, they can implement them at any time along with many others based on a standard algorithm!

---

You commented:

Well, 2 * N implementations are actually only N implementations. The remaining N are built-in overloads, which directly call the "real" version of the algorithm, so they are only headers. Providing container overloads does not negate the goal of separating algorithms from containers, because (as you can see in my example) they can use templates to process all types of containers.

Based on this logic, one can argue very well about M*N algorithms. So do they also perform member functions (and call internal functions)? 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 the correct answer from the Herb Sutter blog: Why there are no container-based algorithms . He shows counterexamples, as Bo Persson did in his answer above.

Answer 5

There is a library of range operators with the intention of fixing this. The verbosity has been cut several times.

Your example would look something like this:

 auto newVector = myVector * doSomething; 

Yes, doSomething - without parentheses.

The familiar idiom from the shell (using the std algorithm):

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

Answer 6

It should be noted that it is 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 need. There is no ambiguity because your wrappers are not in the std namespace. You can define overloads that accept const Container &. If you need versions that invoke the C ++ - 11 const iterator methods (e.g. cbegin ()), I think you will need to name the shell differently. I am using for_each_const.

Answer 7

Obviously, as other users have noted, this is a complex problem, so unfortunately it has been a long time and there is still no solution in the standard library. However, there are already existing library libraries, such as Boost :: Range and one in the Adobe library libraries, which provide not only the simplicity of the interface that you describe in your question, but also some additional functions.

Your example works fine with Boost (below using namespace boost::range::adaptors ):

boost::for_each(myVector, doSomething);

We can also cut myVector quickly and easily:

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

We can even zip myVector with another one, filter by predicate and try each other element of the resulting pairs in one simple statement (this requires you to unpack the tuples created by boost::combined in doSomethingElse):

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