成为`stl`算法兼容容器需要什么？

Question

1)对于给定的stl算法,如何找出为了使用所述容器需要实现的自定义容器/迭代器功能？

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

Answer 1

在C++ 11标准中,脚注中的§25.1中对此进行了说明:

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

然后:

5在整个条款中,模板参数的名称用于表示类型要求.如果算法的模板参数是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)
• 递增的

每种迭代器都有相同的故事.