一尘不染

为什么在C ++ STL中将算法,迭代器和容器分开

algorithm

我不知道为什么他们在C ++ STL中将算法,迭代器和容器分开。如果到处都在大量使用模板,那么我们可以使用类将具有所有参数的类放在一个位置。

我得到的一些文字解释说,迭代器有助于算法与容器数据进行交互,但是如果容器公开某种访问其拥有的数据的机制,该怎么办?


阅读 272

收藏
2020-07-28

共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具有大量的成员函数算法,其中大多数可以实现为非成员函数。

2020-07-28