c++ - 专门化 STL 算法，以便它们在可用时自动调用高效的容器成员函数

Question

STL 具有可以在任意容器上运行的全局算法，只要它们支持该算法的基本要求即可。例如，某些算法可能要求容器具有随机访问迭代器，例如 vector 而不是列表。

当一个容器有比通用算法更快的方法做某事时，它会提供一个同名的成员函数来实现相同的目标——就像一个列表提供它自己的 remove_if()因为它可以通过在恒定时间内进行指针操作来删除元素。

我的问题是 - 是否可以/建议专门化通用算法，以便它们自动调用更高效的容器的成员函数版本？例如。让 std::remove_if 在内部为列表调用 list::remove_if。这已经在 STL 中完成了吗？

Answer 1

不是 remove_if 的情况，因为语义不同。 std::remove_if实际上并没有从容器中删除任何东西，而 list::remove_if确实如此，所以您绝对不希望前者调用后者。

您和实现都不能从字面上专门化容器的通用算法，因为算法是采用迭代器的函数模板，而容器本身是类模板，其迭代器类型取决于模板参数。所以为了专std::remove_if一般为 list<T>::iterator你需要对 remove_if 进行部分特化，并且不存在函数模板的部分特化之类的东西。

我不记得是否允许实现为特定迭代器类型重载算法，但即使不允许，“官方”算法也可以调用可以重载的函数，或者它可以使用可以部分特化的类。不幸的是，如果您已经编写了自己的容器，并且发现了一种使标准算法对其特别高效的方法，那么这些技术都无法帮助您。

例如，假设您有一个带有随机访问迭代器的容器，但您有一种特别有效的排序技术，它适用于标准排序:也许是桶排序。那么你可能会想到放一个免费的功能 template <typename T> void sort(MyContainer<T>::iterator first, MyContainer<T>::iterator last)在与类相同的命名空间中，并允许人们用 using std::sort; sort(it1, it2); 调用它相反 std::sort(it1, it2); .问题是，如果他们在通用代码中这样做，他们冒着其他人编写其他容器类型的风险，这些容器类型将有一个名为 sort 的函数。甚至不对范围进行排序(毕竟，英语单词“排序”有不止一种含义)。因此，基本上您不能以提高用户定义容器效率的方式对迭代器范围进行一般排序。

当代码中的差异仅取决于迭代器的类别时(例如 std::distance 对于随机访问迭代器来说很快，否则很慢)，这是使用称为“迭代器标签分派(dispatch)”的东西来完成的，这就是不同容器之间存在明显效率差异的最常见情况。

如果还有任何适用于标准容器的情况(折扣结果不同或效率只需要特定迭代器类别的情况)，让我们拥有它们。