为什么在 C++ STL 中有算法、迭代器和容器的分离 [英] Why is there a separation of algorithms, iterators and containers in C++ STL

问题描述

我不明白为什么他们在 C++ STL 中分离了算法、迭代器和容器.如果到处都大量使用模板，那么我们可以让类在一个地方使用模板参数将所有东西都放在一个地方.

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?

推荐答案

使用 M 容器 + N 算法，通常需要 M * N 段代码，但迭代器充当胶水"，这可以简化为 M + N 段代码.

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.

示例:在 3 个容器上运行 2 个算法

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);

您只调用了 2 种不同的算法，并且只有 3 个容器的代码.每个容器将 begin() 和 end() 迭代器传递给容器.即使您有 3 * 2 行代码来生成答案，也只有 3 + 2 行代码需要编写.

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.

对于更多的容器和算法，这种分离极大地减少了代码中的组合爆炸，否则会出现:STL 中有 5 个序列容器、8 个关联容器和 3 个容器适配器，并且在 STL 中有近 80 个算法<algorithm> 单独(甚至不包括 <numeric> 中的那些)，因此您只有 16 + 80 而不是 16 * 80，代码减少13倍！(当然，并不是每个算法都适用于每个容器，但重点应该很清楚).

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).

迭代器可以分为 5 类(输入、输出、转发、双向和随机访问)，一些算法会根据迭代器的能力委托给专门的版本.这将在一定程度上减少代码减少，但通过选择最适合手头的迭代器的算法来大大提高效率.

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.

请注意，STL 在分离上并不完全一致:std::list 有自己的 sort 成员函数，该函数使用特定于实现的细节对自身进行排序，并且 std::string 有大量的成员函数算法，其中大部分可以实现为非成员函数.

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.

这篇关于为什么在 C++ STL 中有算法、迭代器和容器的分离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！