8

I can't figure out why they have separated algorithms, iterators and containers in C++ STL. If it's a heavy use of templates everywhere, then we can have classes having all stuff in one place with template parameters.

Some text that I got explains that iterators helps algorithms to interact with containers data but what if containers expose some mechanism to access the data it possesses?

TemplateRex
  • 69,038
  • 19
  • 164
  • 304
Rahul
  • 1,401
  • 4
  • 17
  • 33
  • 1
    I didn't understand a word you wrote. :( – user541686 Aug 14 '12 at 06:51
  • Ok sorry for confusion caused, what I mean is we have different classes for containers, iterators etc. I want to figure what's wrong if we put all in one class using templates, containers have data and they can expose some interfaces to see it or modify. why they are separate? I mean why there are different iterators, algorithms etc. – Rahul Aug 14 '12 at 06:54
  • 3
    [This question](http://stackoverflow.com/questions/10380612/principles-behind-stl-design) might give you some pointers. [This interview](http://www.sgi.com/tech/stl/drdobbs-interview.html) with Alex Stephanov, the creator of the STL, also contains some insights. – Björn Pollex Aug 14 '12 at 06:56
  • Thank you Björn Pollex this will help me. – Rahul Aug 14 '12 at 06:59
  • 12
    The question might not be clearly worded, but it is a real question. And an answer would be that `M` containers + `N` algorithms would normally require `M * N` pieces of code, but with iterators acting as "glue", you can have only `M + N` pieces of code. – TemplateRex Aug 14 '12 at 06:59
  • 1
    @rhalbersma: Voted for reopen, and your comment is the best answer I could come up with myself. – DevSolar Aug 14 '12 at 08:16

1 Answers1

25

With M containers + N algorithms, one would normally need M * N pieces of code, but with iterators acting as "glue", this can be reduced to M + N pieces of code.

Example: run 2 algorithms on 3 containers

std::list<int> l = { 0, 2, 5, 6, 3, 1 }; // C++11 initializer lists
std::vector<int> v = { 0, 2, 5, 6, 3, 1 };  // C++11 initializer lists
std::array<int, 5> a = { 0, 2, 5, 6, 3, 1 };

auto l_contains1 = std::find(l.begin(), l.end(), 1) != l.end();
auto v_contains5 = std::find(v.begin(), v.end(), 5) != v.end();
auto a_contains3 = std::find(a.begin(), a.end(), 3) != a.end();

auto l_count1 = std::count(l.begin(), l.end(), 1);
auto v_count5 = std::count(v.begin(), v.end(), 5);
auto a_count3 = std::count(a.begin(), a.end(), 3);

You are calling only 2 different algorithms, and only have code for 3 containers. Each container passes the begin() and end() iterators to the container. Even though you have 3 * 2 lines of code to generate the answers, there are only 3 + 2 pieces of functionality that need to be written.

For more containers and algorithms, this separation is an enormous reduction in the combinatorial explosion in code that would otherwise ensue: there are 5 sequence containers, 8 associative containers and 3 container adapters in the STL, and there are almost 80 algorithms in <algorithm> alone (not even counting those in <numeric>) so that you have only 16 + 80 instead of 16 * 80, an 13-fold reduction in code! (Of course, not every algorithm makes sense on every container, but the point should be clear).

The iterators can be divided into 5 categories (input, output, forward, bidirectional and random access), and some algorithms will delegate to specialized versions depending on the iterator capabilities. This will diminish the code reduction somewhat, but greatly improve efficiency by selecting the best adapted algorithm to the iterator at hand.

Note that the STL is not completely consistent in the separation: std::list has its own sort member function that uses implementation specific details to sort itself, and std::string has an enormous number of member function algorithms, most of which could have been implemented as non-member functions.

TemplateRex
  • 69,038
  • 19
  • 164
  • 304