专门化 STL 算法，以便它们在可用时自动调用高效的容器成员函数
STL 具有全局算法，可以在任意容器上运行，只要它们支持该算法的基本要求。例如，某些算法可能要求容器具有随机访问迭代器，例如向量而不是列表。
当容器具有比通用算法更快的处理方式时，它会提供具有相同名称的成员函数来实现相同的目标 - 就像提供自己的 remove_if() 的列表一样，因为它可以只需在恒定时间内执行指针操作即可删除元素。
我的问题是 - 是否可以/建议专门化通用算法，以便它们自动调用更高效的容器的成员函数版本？例如，在列表内部使用 std::remove_if 调用 list::remove_if 。这已经在STL中完成了吗？
The STL has global algorithms that can operate on arbitrary containers as long as they support the basic requirements of that algorithm. For example, some algorithms may require a container to have random access iterators like a vector rather than a list.
When a container has a faster way of doing something than the generic algorithm would, it provides a member function with the same name to achieve the same goal - like a list providing its own remove_if() since it can remove elements by just doing pointer operations in constant time.
My question is - is it possible/advisable to specialize the generic algorithms so they automatically call the member function version for containers where it's more efficient? E.g. have std::remove_if call list::remove_if internally for lists. Is this already done in the STL?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
remove_if的情况并非如此，因为语义不同。std::remove_if实际上不会从容器中删除任何内容，而list::remove_if会删除，因此您绝对不希望前者调用后者。您和实现都无法从字面上专门化容器的通用算法，因为算法是采用迭代器的函数模板，而容器本身就是类模板，其迭代器类型取决于模板参数。因此，为了将
std::remove_if专门化为list::iterator ，您需要对remove_if 进行部分专门化，并且不存在函数模板的部分特化之类的东西。我不记得是否允许实现重载特定迭代器类型的算法，但即使不是“官方”算法也可以调用可以重载的函数，或者它可以使用可以部分专业化的类。不幸的是，如果您编写了自己的容器，并且发现了一种使标准算法对其特别有效的方法，那么这些技术都无法帮助您。
例如，假设您有一个带有随机访问迭代器的容器，但您有一个特别有效的排序技术，可以与标准排序一起使用：也许是桶排序。那么你可能会考虑在模板中放置一个自由函数
templatevoid sort(MyContainer::iterator first, MyContainer::iterator last) 与类位于同一命名空间中，并允许人们使用using std::sort; 来调用它sort(it1, it2);而不是std::sort(it1, it2);。问题是，如果他们在通用代码中这样做，他们就会面临其他人编写其他容器类型的风险，该函数将具有名为sort的函数，该函数甚至不会对范围进行排序（英语单词“sort”）毕竟有不止一种含义）。因此基本上您不能以提高用户定义容器效率的方式对迭代器范围进行一般排序。当代码中的差异仅取决于迭代器的类别时（例如
std::distance对于随机访问迭代器来说速度很快，否则速度很慢），这是使用称为“迭代器标签调度”的东西来完成的”，这是最常见的情况，不同容器之间存在明显的效率差异。如果还有任何适用于标准容器的情况（不包括结果不同或效率仅需要特定迭代器类别的情况），让我们拥有它们。
Not in the case of
remove_if, since the semantics are different.std::remove_ifdoesn't actually erase anything from the container, whereaslist::remove_ifdoes, so you definitely don't want the former calling the latter.Neither you nor the implementation can literally specialize the generic algorithms for containers because the algorithms are function templates that take iterators, and the containers are themselves class templates, whose iterator type depends on the template parameter. So in order to specialize
std::remove_ifgenerically forlist<T>::iteratoryou would need a partial specialization ofremove_if, and there ain't no such thing as a partial specialization of a function template.I can't remember whether implementations are allowed to overload algorithms for particular iterator types, but even if not the "official" algorithm can call a function that could be overloaded, or it can use a class that could be partially specialized. Unfortunately none of these techniques help you if you've written your own container, and have spotted a way to make a standard algorithm especially efficient for it.
Suppose for example you have a container with a random-access iterator, but where you have an especially efficient sort technique that works with the standard ordering: a bucket sort, perhaps. Then you might think of putting a free function
template <typename T> void sort(MyContainer<T>::iterator first, MyContainer<T>::iterator last)in the same namespace as the class, and allow people to call it withusing std::sort; sort(it1, it2);insteadstd::sort(it1, it2);. The problem is that if they do that in generic code, they risk that someone else writing some other container type will have a function namedsortthat doesn't even sort the range (the English word "sort" has more than one meaning, after all). So basically you cannot generically sort an iterator range in a way that picks up on efficiencies for user-defined containers.When the difference in the code depends only on the category of the iterator (for example
std::distancewhich is fast for random access iterators and slow otherwise), this is done using something called "iterator tag dispatch", and that's the most common case where there's a clear efficiency difference between different containers.If there are any remaining cases that apply to standard containers (discounting ones where the result is different or where the efficiency only requires a particular iterator category), let's have them.
这是不可能的——算法与迭代器一起工作，而迭代器不知道它们引用的容器对象。即使他们这样做了，也无法在编译时确定给定的迭代器范围是否引用整个容器，因此不能仅通过专门化来完成；需要进行额外的运行时检查。
It is not possible - the algorithms work with iterators, and iterators have no knowledge of the container object they refer to. Even if they did, there would be no way to determine at compile time whether a given iterator range refers to the whole of a container, so it could not be done by specialisation alone; there would need to be an extra runtime check.
做到这一点的唯一方法是为每个算法创建自己的包装模板，采用一个容器而不是一对迭代器。然后，您可以针对可以优化的每种容器类型专门化您的包装器。不幸的是，这消除了标准算法的很多灵活性，并让你的程序充满了一堆非标准调用。
The only way to do this would be to create your own wrapper templates for each of the algorithms, taking a container rather than a pair of iterators. Then you could specialize your wrapper for each container type that could be optimized. Unfortunately this removes a lot of the flexibility of the standard algorithms, and litters your programs with a bunch of non-standard calls.
您所寻找的不是专业化，而是超载。您可以提供算法的替代版本（不过，合法地在命名空间
std中），将容器作为参数，而不是迭代器对，并且可以调用 STL 挂件在容器上调用begin()和end()，或者执行其他操作。不过，这种方法当然需要代码来调用函数而不是 STL 函数。这肯定以前已经完成过，因此您实际上可能会找到一组标头，从而节省您编写所有这些样板代码的工作。
What you are looking for isn't specialization, but overloading. You could provide alternative versions of the algorithms (not, legally, in namespace
std, though) that take containers as arguments, rather than iterator pairs, and either call the STL pendants callingbegin()andend()on the container, or do something else. Such an approach of course does require the code to call your functions instead of the STL functions, though.This has certainly been done before, so you might actually find a set of headers out there saving you the work to write all this boilerplate code.