成为一个 `stl` 算法兼容的容器需要什么条件？

Question

1) 对于给定的stl算法，如何找出需要实现哪些自定义容器/迭代器特性才能使用该容器？

2) 为使容器与所有stl算法完全兼容，需要实现什么？

- Michael

---

@RSahu 我不同意你的重复目标，因为原帖并不是在询问如何实现迭代器，而是在询问算法需要哪些迭代器类型以及如何支持所有算法与它们的容器。 - NathanOliver

@NathanOliver，如果容器具有正确的迭代器，那么在大多数（如果不是全部）算法中都可以使用它。这不是事实吗？ - R Sahu

@RSahu那在副本目标中是哪里？ 使一个类可迭代并不意味着它将与所有算法一起工作。该类的迭代器类型是并且没有讨论迭代器类型。 - NathanOliver

@NathanOliver，我理解你的观点。 - R Sahu

两个问题都是“无”，STL算法现在对容器一无所知，因此不对容器做任何要求。 - SergeyA

Answer 1

在C++11标准中，§25.1脚注3中指出：

所有算法都与数据结构的特定实现分离，并由迭代器类型参数化。因此，只要这些数据结构具有满足算法假设的迭代器类型，它们就可以使用程序定义的数据结构。

然后是:

在本条款中，模板参数的名称用于表示类型要求。如果算法的模板参数是InputIterator，InputIterator1或InputIterator2，则实际模板参数应满足输入迭代器的要求(24.2.3)。如果算法的模板参数是OutputIterator，OutputIterator1或OutputIterator2，则实际模板参数应满足输出迭代器的要求(§24.2.4)。如果算法的模板参数是ForwardIterator，ForwardIterator1或ForwardIterator2，则实际模板参数应满足前向迭代器的要求(§24.2.5)。如果算法的模板参数是BidirectionalIterator，Bidirectional-Iterator1或BidirectionalIterator2，则实际模板参数应满足双向迭代器的要求(§24.2.6)。如果算法的模板参数是RandomAccessIterator，Random- AccessIterator1或RandomAccessIterator2，则实际模板参数应满足随机访问迭代器的要求(§24.2.7)。

因此，基本上您需要为自定义类提供检索通常迭代器的方法，并且这些对象必须满足具体算法所需的要求。

例如，以std::any_of为例，可以看到它声明为:

template <class InputIterator, class Predicate> 
bool any_of(InputIterator first, InputIterator last, Predicate pred);

因此，您需要提供一个输入迭代器，然后可以在§24.2.3中查看其要求并实现它们：

• 上下文转换为bool（a != b）
• 可转换为T（*a）
• 可取消引用（a->m）
• 可递增

对于每种类型的迭代器，情况相同。

- Jack

Answer 2

STL算法使用模板类型来描述函数的要求。如果以std::sort为例。

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

我们可以看到我们需要传递一个符合随机访问的迭代器。只要您拥有的容器具有 RandomAccessIterator类型的迭代器或者支持RandomAccessIterator支持的所有操作，那么就可以与std::sort一起使用。

如果我们查看 cppreference上的迭代器层次结构，我们可以看到在当前标准中， RandomAccessIterator是所有其他迭代器类型的超集，并支持其他迭代器支持的所有操作。因此，如果函数调用需要一个InputIterator，我们仍然可以给它一个RandomAccessIterator。

所以现在，如果您的容器有一个RandomAccessIterator，您可以在任何STL算法中使用它。

- NathanOliver