如何编写以通用方式接受迭代器或集合的函数？

Question

我在过去的8年左右一直是Java程序员，最近我一直在玩C++。以下是我在C++ STL和Java中针对迭代器提出的问题。

在Java中，你可以编写需要这样一个迭代的方法：

void someMethod(Iterator<String> data) { 
    // ... 
} 

传入一个Iterator和方法不需要知道什么是迭代器的底层集合是，这是好。

在C++中，没有用于迭代器的公共基类（据我所知）。我不得不写一个函数是这样的：

void some_function(std::vector<std::string>::const_iterator data) { 
    // ... 
} 

换句话说，some_function知道迭代器是在vector的迭代器。这并不好，因为我希望函数能够工作，而不管迭代器的底层集合是什么。

我该如何在C++中做到这一点？如果这不是真的可行，那么在C++中创建一个以集合为参数的函数的最佳方式是什么，但不需要知道确切种类的集合是什么？

附录

感谢您的答案。除了答案之外，我在The C++ Standard Library: A Tutorial and Reference（Nicolai M. Josuttis着）的第7.5段（迭代器特征）中找到了一些关于这方面的很好的信息。段落7.5.1解释了如何为不同的迭代器类别编写函数的专用版本。

Answer 1

它最好通过命名约定来指示迭代器的种类以及迭代器需要拥有的属性类型。下面是一些共同的命名惯例迭代：

 
template<typename Iterator> 
void foo_iterator(Iterator begin, Iterator end) 
{ 
    typedef typename std::iterator_traits<Iterator>::value_type T; 
    .... 
} 

template<typename RandomIterator> 
void foo_random_iterator(RandomIterator begin, RandomIterator end) 
{ 
    typedef typename std::iterator_traits<RandomIterator>::value_type T; 
    .... 
} 

template<typename ForwardIterator> 
void foo_forward_iterator(ForwardIterator begin, ForwardIterator end) 
{ 
    typedef typename std::iterator_traits<ForwardIterator>::value_type T; 
    .... 
} 

template<typename ReverseIterator> 
void foo_forward_iterator(ReverseIterator begin, ReverseIterator end) 
{ 
    typedef typename std::iterator_traits<ReverseIterator>::value_type T; 
    .... 
} 

template<typename InputIterator> 
void foo_input_iterator(InputIterator begin, InputIterator end) 
{ 
    typedef typename std::iterator_traits<InputIterator>::value_type T; 
    .... 
} 

template<typename OutputIterator> 
void foo_output_iterator(OutputIterator out) 
{ 
    // We don't have a type T, as we can't "always" 
    // know the type, as this type of iterator is a sink. 
    .... 
} 

以下是序列类型容器，其中包括载体和双端队列通用定义。

 
template <typename T, 
      class Allocator, 
      template <class,class> class Sequence> 
inline void foo_sequence(Sequence<T,Allocator>& sequence) 
{ 
    .... 
} 

Answer 2

你可能想要考虑一个函数模板。看一下std<algorithm>函数模板如何工作，如std::for_each。

例如

template< class Iterator > 
void some_function(Iterator first, Iterator last) 
{ 
    // ... 
} 

然后，您可以使用多种可迭代范围调用此模板生成的函数。

例如

std::vector<double> my_doubles; 
// ... populate doubles 
some_function(my_doubles.begin(), my_doubles.end()); 


std::set<Custom> my_custom_class_set; 
// ... populate ... 
some_function(my_custom_class_set.begin(), my_custom_class_set.end()); 

int raw_array[50]; 
// ... populate ... 
some_function(raw_array, raw_array + 50); 

Answer 3

您可以使用header file并指定迭代器必须支持的最低要求。

所以在上面的例子中，你可能要重写的功能，例如：

template<typename T> 
void some_function(std::forward_iterator<T> data) { 
    ... 
} 

的东西，要求能够只（++），通过收集向前移动迭代器。

Answer 4

这是C++和Java之间最大区别之一的例子。 Java唯一的抽象工具是运行时多态（接口和抽象类）。在C++中，你不仅限于此。您可以为类型创建别名，并让类具有其他关联/嵌套类型。它可以让你在很多情况下没有运行时多态。编译时类型的通用性具有相当快的优点（没有虚函数调用，内联可能性）。另外，当你没有垃圾收集器时，它可以简化生命周期管理。您可以简单地在堆栈上创建对象。

下面是一个（未经测试）例如：

template<typename Iter> 
typename std::iterator_traits<Iter>::value_type 
sum(Iter begin, Iter end) { 
    typedef typename std::iterator_traits<Iter>::value_type vt; 
    vt accum = vt(); 
    while (begin!=end) { 
     accum += *begin; 
     ++begin; 
    } 
    return accum; 
} 

这里， “Iter项目” 北京时间只是一个名字。它实际上并没有对该类型施加任何限制。如果你想用一个不是迭代器的类型实例化这个模板（至少在结构意义上），你会得到一个编译时错误（编译时鸭式键入）。所以，你的工作的一部分是记录你期望的类型。这通常通过选择一些模板参数（即ForwardIterator）和注释的描述性名称来完成。

我还要提到的是多个“和”功能将被“实例”，如果你使用这个函数模板与不同类型的迭代器。如果你不想要这种代码重复和/或真的需要运行时多态性，你可以应用一种称为“类型擦除”的技术。不过，迭代器的类型擦除不是标准库的一部分。另外，我从未觉得有必要将这种技术应用于迭代器。但是你会发现在其他类库如boost :: any和boost :: function中使用类型擦除。

有一对夫妇的其他模板的技巧，你可以使用不同的迭代器种类来区分（见“标签调度”）或限制你的函数模板（请参阅“SFINAE”）。如果您对类型删除感兴趣，请尝试使用Google搜索功能，输入erasure，iterator。你基本上创建了一个处理多态对象的句柄类（通过指针）。这个多态对象包装了一些你想要“擦除”（隐藏）的其他对象。