为什么在C++ STL中存在算法,迭代器和容器的分离

Question

我无法弄清楚为什么他们在C++ STL中分离了算法,迭代器和容器.如果在任何地方大量使用模板,那么我们可以使用模板参数将所有内容放在一个地方.

我得到的一些文本解释了迭代器有助于算法与容器数据交互,但是如果容器暴露了一些机制来访问它拥有的数据呢？

Answer 1

使用M容器+ N算法,通常需要M * N一些代码,但是迭代器充当"粘合剂",这可以简化为M + N代码片段.

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

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需要编写一些功能.

对于更多的容器和算法,这种分离大大减少了代码中的组合爆炸,否则会发生:STL中有5个序列容器,8个关联容器和3个容器适配器,并且<algorithm>单独有近80个算法(不是算上那些<numeric>),这样就只有16 + 80来代替16 * 80,一个13倍的减少代码!(当然,并非每个算法都适用于每个容器,但重点应该是明确的).

迭代器可以分为5类(输入,输出,转发,双向和随机访问),一些算法将根据迭代器功能委托给专用版本.这会稍微减少代码减少,但通过为手头的迭代器选择最适合的算法可以大大提高效率.

请注意,STL在分离中并不完全一致:std::list有自己的sort成员函数,它使用特定于实现的细节来自我排序,并且std::string具有大量的成员函数算法,其中大多数可以作为非成员函数实现.