专门的 STL 算法，以便它们在可用时自动调用有效的容器成员函数 [英] Specializing STL algorithms so they automatically call efficient container member functions when available

问题描述

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

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

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

解决方案

不是在 remove_if 的情况下，因为语义不同.std::remove_if 实际上不会从容器中删除任何东西，而 list::remove_if 会，所以你绝对不希望前者调用后者.>

无论是你还是实现都不能从字面上特化容器的通用算法，因为算法是采用迭代器的函数模板，而容器本身就是类模板，其迭代器类型取决于模板参数.因此，为了将 std::remove_if 专门化为 list::iterator，您需要对 remove_if 进行部分专门化，并且没有函数模板的部分特化这样的东西.

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

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

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

如果还有其他适用于标准容器的情况(不考虑结果不同的情况或效率只需要特定迭代器类别的情况)，让我们来看看.

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?

解决方案

Not in the case of remove_if, since the semantics are different. std::remove_if doesn't actually erase anything from the container, whereas list::remove_if does, 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_if generically for list<T>::iterator you would need a partial specialization of remove_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 with using std::sort; sort(it1, it2); instead std::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 named sort that 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::distance which 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.

这篇关于专门的 STL 算法，以便它们在可用时自动调用有效的容器成员函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！