Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why don't std::algorithms work directly on containers as well?

Tags:

c++

algorithm

I have been looking at some algorithms and I am wondering why some of them don't also have a variation that takes in a container.

For example, find can take in a container and value and the algorithm can internally iterator over the container by calling begin and end of the container. Same with unique_copy where it seems more useful to me to pass a container and the algorithm use push_back instead of requiring an iterator where I would be forced to resize the array to the maximum element count. for_each is another such example.

I am sure there are good reasons I don't know about?

like image 234
Samaursa Avatar asked Sep 16 '12 00:09

Samaursa


3 Answers

There are two main reasons I can see:

  1. Adding overloads for containers would more than double the number of functions: For each algorithm taking just one range, the overloads would double. However, for something like std::copy() you have two ranges, each one of them independently wants to be specified either as range (the proper abstraction isn't containers, BTW, but rather rangers) or a pair of iterators, making it already 4 overloads.
  2. Once ranges enter the picture, it isn't entirely clear what needs to be returned. Your example uses std::find() which clearly returns an iterator when it gets iterators as arguments. When given a range, it may actually be much more reasonable to return another range. To make matters worse, unless you have a single pass range initially (e.g., something reading from a stream) there is even a choice of two different ranges, i.e., begin to found object, and found object to end. Another dimension could be a choice of getting a copy of the chosen range rather than a range delimited by iterators.

When STL was proposed initially, it was considered Crazy Talk in the first place! Trying to convince people to open another major can of worms to deal with ranges properly could have easily killed off the entire idea. The immediate follow-up question then becomes: Why wasn't this changed? ... and there are two answers to this question as well:

  1. I haven't proposed a changed interface although a draft version was considered to be reasonable when I presented it to the Library Working Group. The proposal I outlined wasn't met with great enthusiasm, however. Also, at the time I had no idea how to actually implement the interface I envisioned with acceptable effort (with C++ 2011 features I know how to do it). I have started to write a description of a new interface of STL but even this is incomplete and I haven't managed to take time to work on this recently.
  2. Although the algorithms are, in my opinion, the correct way to go, many people deliberately don't use them. I found cases where people have replaced uses of the algorithms because it is allegedly "more readable" to write a loop doing an operation than calling an algorithm. Unfortunately, this is, indeed, even true in some cases because the involved function objects are just hideous. Given that few people seem to use the algorithms there seems little incentive to change them.
like image 200
Dietmar Kühl Avatar answered Oct 20 '22 00:10

Dietmar Kühl


If you want to put the result into a container without preallocating the elements, use an insert iterator. For example:

std::vector<int> elements;
// ...
std::vector<int> uniqueElements;
std::unique_copy(elements.begin(), elements.end(),
    std::back_inserter(uniqueElements));
like image 32
Derek Ledbetter Avatar answered Oct 20 '22 00:10

Derek Ledbetter


The algorithms that take iterators are the most general purpose. There's nothing preventing you from creating your own convenience functions that call the standard algorithms with the proper parameters.

like image 2
Mark Ransom Avatar answered Oct 20 '22 01:10

Mark Ransom