只是一点介绍,用简单的文字。在 C 中,迭代器是“事物”,您至少可以在其上编写取消引用运算符 *
it,增量运算符 it,对于更高级的双向迭代器,递减 --it
,最后但并非最不重要的一点是,对于随机访问迭代器,我们需要运算符索引它[]
,并且可能需要加减法。
C 中的此类“事物”是具有相应运算符重载或简单指针的类型对象。
标准::矢量
使用指针的基本原理是更少的开销,更高的性能,特别是如果优化编译器检测到迭代并执行其操作(矢量指令等)。编译器可能更难优化使用迭代器。
知道了这一点,我的问题是为什么现代 STL 实现,比如 MSVC 2013 或 Mingw 4.7 中的 libstdc,对向量迭代器使用一个特殊的类?
你完全正确,vector::itrator
可以通过一个简单的指针来实现(见这里)——事实上,迭代器的概念是基于指向数组元素的指针的概念。但是,对于其他容器(如映射
、列表
或双端
面),指针根本不起作用。那么为什么不这样做呢?下面是类实现可优先于原始指针的三个原因。
>
将迭代器实现为单独的类型允许其他功能(超出标准要求),例如(在 Quentins 注释后的编辑中添加)在取消引用迭代器时添加断言的可能性,例如,在调试模式下。
重载分辨率 如果迭代器是指针 T*
,则可以将其作为有效参数传递给采用 T*
的函数,而这对于迭代器类型是不可能的。从而使 std::vector
template<typename It>
void foo(It begin, It end);
void foo(const double*a, const double*b, size_t n=0);
std::vector<double> vec;
foo(vec.begin(), vec.end()); // which foo is called?
依赖于参数的查找(ADL;由juanchopanza指出) 如果进行非限定调用,ADL 可确保仅当参数是在命名空间 std 中定义的类型时,才会搜索命名空间 std
中的函数。所以
std::vector<double> vec;
sort(vec.begin(), vec.end()); // calls std::sort
sort(vec.data(), vec.data()+vec.size()); // fails to compile
std::排序
找不到,如果向量
迭代器的实现是定义的实现,只要满足标准的要求。它可以是矢量
的指针,这将起作用。不使用指针有几个原因;
如果所有迭代器都是指针,那么
它
在地图上不会递增到下一个元素,因为内存不需要不连续。除了 std:::vector
的连续内存之外,大多数标准容器都需要“更智能”的指针 - 因此需要迭代器。
迭代器的物理要求与逻辑要求非常吻合,即元素之间的移动是迭代它们的明确定义的“习惯用语”,而不仅仅是移动到下一个内存位置。
这是STL最初的设计要求和目标之一;容器、算法之间的正交关系以及通过迭代器连接两者。
现在它们是类,您可以添加大量错误检查和健全性检查来调试代码(然后删除它以获得更优化的发布代码)。
鉴于基于类的迭代器带来的积极方面,为什么你应该或不应该只使用 std::vector
迭代器的指针 - 一致性。std::vector
的早期实现确实使用了普通指针,您可以将它们用于 vector
。一旦你必须为其他迭代器使用类,考虑到它们带来的积极因素,将其应用于向量
成为一个好主意。
使用指针的基本原理是更少的开销,更高的性能,特别是如果优化编译器检测到迭代并执行其操作(矢量指令等)。编译器可能更难优化使用迭代器。
可能是,但事实并非如此。如果你的实现不是完全的狗屎,那么包装指针的结构将达到相同的速度。
考虑到这一点,很容易看出,更好的诊断消息(命名迭代器而不是 T*)、更好的重载分辨率、ADL 和调试检查等简单的好处使结构成为指针的明显赢家。原始指针没有任何优点。