Stl Algorithms: Why No Additional Interface for Containers (Additional to Iterator Pairs)

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

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

STL algorithms taking the whole container rather than .begin(), end() as arg?

There is a nice blog-post by Herb Sutter discussing the question. The gist is that adding container-based overloads for algorithms can create ambiguities if an overload for that algorithm with the same number of template-parameters already exists. Concepts were intended to fix that problem.

Why do some STL algorithms provide an additional '_if' function instead of overloading?

Those algorithms provide a named version rather than an overloaded one because both versions of the algorithm take the same number of arguments. Overloading ambiguities would therefore be possible.

To avoid any possible ambiguities, the library provides separate named versions for those algorithms, find_if is one of those.

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

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.

Container-based overloads in STL

See here for a good answer: STL algorithms: Why no additional interface for containers (additional to iterator pairs)?

(apologies, I cannot mark as duplicate)

Providing an iterator for the first element of a container of pairs

I've looked around and found boost::transform_iterator. I've come up with this code. Surprising how well it works:

#include <map>
#include <algorithm>
#include <iostream>
#include <string>
#include <iterator>
#include <boost/iterator/transform_iterator.hpp>
#include <boost/bind.hpp>
#include <boost/function.hpp>

int main() {
    typedef std::map<std::string, int>::value_type value_type;
    std::map<std::string, int> a;
    a["one"] = 1;
    a["two"] = 2;

    // returns the second element 
    boost::function<int(value_type&)> f = boost::bind(&value_type::second, _1);
    std::copy(boost::make_transform_iterator(a.begin(), f), 
              boost::make_transform_iterator(a.end(), f),
              std::ostream_iterator<int>(std::cout, " "));

}

It's printing "1 2 " to the standard output.

How to write a STL-compliant container but its size is unknown?

There's a bit of confusion around container "requirements" in the C++ standard. While the requirements on iterators are true requirements (e.g., standard algorithms expect that iterators will have certain properties that are defined by the requirements), there is nothing in the standard library that depends on any container satisfying the "container requirements". Those requirements are, in fact, design statements about the particular containers defined in the standard, not requirements in the sense that not meeting them will break code.

Think of containers as a way of providing iterators over a sequence of values. That's important, but it's not the only way to create useful iterators. Input streams, for example, are not containers (and in general don't have a way of determining their size) but they do provide iterators (in the form of istream_iterator) that can be passed to standard algorithms. There's nothing wrong with that. Just do it.

STL algorithms such as for_each applied to more than one arguments

What you are looking for is std::bind or its twin boost::bind. They are used like this:

std::vector<int> v = {1,2,3,4};
std::transform(begin(v), end(v), begin(v), std::bind(std::plus<int>(), _1, 23 ));

Also have a look at as many broken ways to iterate as possible https://stackoverflow.com/a/8378613/105672

---

Related Topics