什么是迭代器？

Question

当我尝试使用接受"general iterator"的ctor编写C++类模板时,会出现此问题.我不知道在这里使用general这个词是否合适,但我的意思是它可以像STL容器一样接受迭代器.

换句话说,我对迭代器感到困惑.似乎所有STL容器都具有相同类型的迭代器,那么该类型是什么？它只是指针吗？还是更复杂的东西？但是STL容器确实接受普通指针.

(我想将它与Iterator<T>in 进行比较Java,这很简单,只是一个类)

Answer 1

在C++中,Iterator是一个概念,不是具体(或抽象)类型,而是任何遵循规则等迭代器的类型.

例如,迭代器通常可以递增++i.可以访问它们(取消引用)*i以获取它们当前指向的值.它们本质上是指针的抽象.

在标准库的容器和算法中,有不同类型的具有不同属性的迭代器.它们的属性列在这里:

https://en.cppreference.com/w/cpp/iterator

因此,当用C++编写接受迭代器的算法时,通常只接受通用模板参数并在函数中使用适当的迭代器属性.如果用户向您的函数传递了一些不遵守迭代器规则的东西,编译器会抱怨:

template<typename Iterator>
void my_algorithm(Iterator begin, Iterator end)
{
    for(; begin != end; ++begin)
        std::cout << *begin << '\n';
}

您可以添加一大堆特定的检查,以确保用户传递了一些合理的东西,但这对于这个问题来说太宽泛了.

注意:

虽然目前的概念(如Iterator)仅仅是程序员必须遵循的标准中一组商定的语义属性,但是将更准确地将这些概念(代码中)形式化的更全面的解决方案将用于标准的下一版本,C + +20.

Answer 2

作为一个概念的迭代器来自C++之前的标准.

C++最初是以C开头的.添加了更多功能,并且指数级增长的人对该语言感兴趣.

一项非常重要的工作被称为STL - 标准模板库 - 最初由Stepanov和Lee编写.1994年在惠普公司(Hewlett-Packard),后来由SGI维护.

该库以非常革命性的方式使用了C++的模板元编程部分.它被编写为允许接近裸机的性能与抽象类型,算法实现与容器实现分离,几乎任意类型.

迭代器是一种概念 - 一种更高级的类型

在其中,迭代器是一个概念.C++中的概念是一类类型(可以说是一种类型).编译器不强制执行C++中的概念(目前).

如果类型具有所需的操作,则类型满足概念,并且这些操作遵循概念的规则.

在STL和后来的C++标准中,围绕迭代器有一个层次的概念.它们从最少限制(迭代器)到最多(读写随机访问连续迭代器),并形成一个树.

模板函数编写函数

当模板算法要求Iterator时,它们要求的类型满足Iterator概念(如C++标准中所述).当他们要求RandomAccessIterator时,他们要求的类型满足RandomAccessIterator概念(其中还包括Iterator概念,ForwardIterator概念和其他一些概念).

所以template<class ForwardIterator> void std::sort( ForwardIterator, ForwardIterator )是需要满足的ForwardIterator概念相同类型的两个实例模板函数.

ForwardIterators必须支持多个操作(*it,++it,bool b = it != it,bool b = it == it,等),询问服务某些特性(iterator_traits<it>::iterator_category,iterator_traits<it>::reference,iterator_traits<it>::value_type等),而这些操作必须遵循一定的规则.

如果为它提供满足RandomAccessIterator的类型,则std::sort保证比传递a更好的性能ForwardIterator.

原始指针满足Forward RandomAccess迭代器而不做任何事情. std::vector<?>::iterator也满足两者,但往往不是一个原始指针(标准库做了一些工作).

两种类型 - 原始指针和std::vector<?>::iterator- 通常是不相关的类型.C++的模板和特征系统允许相同的模板算法理解不相关的类型,运行时开销为零.

在c ++ 2a中,计划引入语言中的概念,它实际上检查了诸如RandomAccessIterator之类的一些要求,并且记录了实际上无法检查的其他要求.

C++不是OO语言

您可能会因习惯面向对象的语言而感到困惑.C++支持面向对象编程,但不是面向对象的语言.它支持多态 - 处理多个类型相同 - 没有基于对象的继承以多种方式.

在面向对象语言中,每个迭代器都将从抽象迭代器类型继承.算法将通过该抽象接口与迭代器交互,通常通过某种虚函数表调度调用.类型的值是不可能的,因为算法代码将在不知道迭代器占用多少字节的情况下编译,因此会发生额外的间接.

在C++中,算法不是函数,除非您将迭代器的类型传递给它.此时,该函数是为该迭代器自定义编写的.C++标准规定,如果迭代器执行某些操作(遵守所需的概念),则模板编写的函数将具有某些行为.

这个模板编写的函数知道迭代器的大小,操作的作用,可以内联操作并将迭代器的实例存储在缓冲区或堆栈中作为值.除非迭代器强制它,否则没有虚拟分派,如果操作可见,则可以将它们内联到书面函数中.

编译器可以检查紧密循环,并且可以进行矢量化,就像您手动编写函数一样.

相同的模板可以对数据库条目或字符串或整数进行排序; 每种情况都会编写一个新函数,并告诉编译器尝试使其更快.

TL; DR

迭代器不是一种类型; 他们是一种类型.完全不相关的类型都可以是迭代器.迭代器没有基类; 只有某种方式可以保证他们的行为.

C++算法为您传递给的每种类型的迭代器生成自定义代码std::sort; 如果你对int的向量和字符串向量进行排序,那么两者之间不会共享二进制代码(除了comdat折叠的可能性).

Iterator/ForwardIterator/RandomAccessIterator的概念(类型)是传递给C++算法的类型的文档要求.没有强制执行,除了编译器可以自由地做任何事情,如果你不能满足要求.