提问者:小点点

C std::vector<>::iterator 不是指针,为什么?


只是一点介绍,用简单的文字。在 C 中,迭代器是“事物”,您至少可以在其上编写取消引用运算符 *it,增量运算符 it,对于更高级的双向迭代器,递减 --it,最后但并非最不重要的一点是,对于随机访问迭代器,我们需要运算符索引它[],并且可能需要加减法。

C 中的此类“事物”是具有相应运算符重载或简单指针的类型对象。

标准::矢量

使用指针的基本原理是更少的开销,更高的性能,特别是如果优化编译器检测到迭代并执行其操作(矢量指令等)。编译器可能更难优化使用迭代器。

知道了这一点,我的问题是为什么现代 STL 实现,比如 MSVC 2013 或 Mingw 4.7 中的 libstdc,对向量迭代器使用一个特殊的类?


共3个答案

匿名用户

你完全正确,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 和调试检查等简单的好处使结构成为指针的明显赢家。原始指针没有任何优点。

    相关问题