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

29

简单介绍一下。在C++中,迭代器是"东西",你可以在其上写入至少解引用运算符 *it,自增运算符 ++it,对于更高级的双向迭代器,则需要自减运算符 --it,最后但并非最不重要的是,对于随机访问迭代器,我们需要索引运算符 it[],以及可能的加法和减法。

在C++中,这样的"东西"是具有相应运算符重载的类型对象,或者是普通的简单指针。

std::vector<> 是一个容器类,它包装了一个连续的数组,因此使用指针作为迭代器是有意义的。在网络上以及某些文献中,您可以找到将 vector.begin() 用作指针的写法。

使用指针的理由是开销小,性能更高,特别是如果优化编译器检测到迭代并执行相关操作(如矢量指令等)。而使用迭代器可能会更难于编译器进行优化。

了解了这些,我的问题是为什么现代STL实现(比如MSVC++ 2013或Mingw 4.7中的libstdc++)会为 vector 迭代器使用特殊的类?


14
问题是:为什么不呢?与你似乎认为的相反,使用类而不是指针并不意味着增加开销,而且使用类还有其他潜在的好处。 - Konrad Rudolph
5
一个原因是安全性:在解引用无效迭代器时,库有断言机制。 - Quentin
2
事实证明编译器足够聪明,能够理解向量迭代器类只包含指针,并从中进行优化。 - Bo Persson
6
我认为那是过时的知识。是的,标准库需要强大的内联能力。但是现代编译器已经提供了这个,并且更多。自2007年以来,编译器已经进化了很多。 - Konrad Rudolph
2
通用代码一般在进行良好的内联和comdat折叠时更加实用。现代良好编译器必须擅长这项任务以充分利用现代C++。如果没有这些功能,C++将变得无法高效。然而,现在已经存在着出色的现代编译器,并且它们也相对较为普遍。而且它们还在不断改进中。 - Yakk - Adam Nevraumont
显示剩余6条评论
7个回答

27

你说的没错,vector::iterator可以通过简单的指针实现(参见这里)-- 实际上,迭代器的概念基于指向数组元素的指针。但对于其他容器,比如maplist或者deque,指针根本行不通。那么为什么不采用指针呢?以下是三个使用类实现而不是原始指针的原因。

  1. Implementing an iterator as separate type allows additional functionality (beyond what is required by the standard), for example (added in edit following Quentins comment) the possibility to add assertions when dereferencing an iterator, for example, in debug mode.

  2. overload resolution If the iterator were a pointer T*, it could be passed as valid argument to a function taking T*, while this would not be possible with an iterator type. Thus making std::vector<>::iterator a pointer in fact changes the behaviour of existing code. Consider, for example,

    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?
    
  3. argument-dependent lookup (ADL; pointed out by juanchopanza) If you make an unqualified call, ADL ensures that functions in namespace std will be searched only if the arguments are types defined in namespace std. So,

    std::vector<double> vec;
    sort(vec.begin(), vec.end());             // calls std::sort
    sort(vec.data(), vec.data()+vec.size());  // fails to compile
    

    std::sort is not found if vector<>::iterator were a mere pointer.


6
重载解析可能是最重要的原因之一,+1。 - Ben Voigt
1
@BenVoigt 另一个问题是对于普通指针,ADL 不起作用。除非某个实现允许在 std 命名空间内定义自定义指针类型。 - juanchopanza
@juanchopanza 如果我没记错的话,ADL只有在某些std函数显式使用vector::iterator作为参数时才会相关。你有这样一个函数的例子吗? - Walter
@Walter 任何接受一对迭代器的函数。std::vector<int> v; sort(v.begin(), v.end());除非迭代器在std命名空间中,否则无法正常工作。 - juanchopanza
2
如果调试配置使用了已检查的迭代器(一种类类型),而发布配置没有使用,则重载决议可能会更糟。 - dyp
显示剩余3条评论

7
迭代器的实现是“实现定义”的,只要满足标准的要求即可。它可以是一个指针,例如对于vector,这将起作用。不使用指针有以下几个原因:
  • 与其他容器保持一致性。
  • 调试和错误检查支持。
  • 重载解析,基于类的迭代器允许重载工作,使其与简单的指针区分开来。
如果所有的迭代器都是指针,那么在map上进行++it操作将无法将其增加到下一个元素,因为内存不需要是非连续的。超出std::vector的连续内存,大多数标准容器需要“更智能”的指针 - 因此需要使用迭代器。
迭代器的物理要求非常契合逻辑需求,即在元素之间移动是迭代它们的一个明确定义的“习语”,而不仅仅是移动到下一个内存位置。
这是STL的最初设计要求和目标之一;容器、算法之间的正交关系,以及通过迭代器将二者连接起来。
现在它们是类,你可以添加很多错误检查和健全性检查来调试代码(然后将其删除以获得更优化的发布代码)。
鉴于基于类的迭代器带来的积极方面,为什么应该或者不应该只使用指针作为std::vector的迭代器 - 一致性。早期实现的std::vector确实使用了简单的指针,你可以使用它们来进行vector操作。一旦你必须为其他迭代器使用类,考虑到它们带来的好处,将这种方法应用于vector是一个好主意。

4
楼主明确询问了 vector::iterator,而非 map::iterator - Walter
2
@Walter。一致性。早期的std::vector实现确实使用了普通指针,您可以将它们用于vector。一旦您必须为其他迭代器使用类,考虑到它们带来的优点,将其应用于vector是一个好主意。 - Niall
1
@Walter:现在明白了吗?使用迭代器的东西可以与几乎所有STL容器一起使用,而使用指针仅适用于向量/数组,并且并不更快! - Marcus Müller
4
你没有理解。你说的并没有回答问题。问题不是“为什么不使用指针作为迭代器?”,而是“为什么 vector::iterator 的实现与指针不同,当指针可以满足所有 RandomAccessIterator 的要求时?” - Walter
@Walter:但是它不能满足所有的要求!一个双向访问迭代器必须具有特性,这只能通过一个包装指针的类来实现。 - Marcus Müller
8
@MarcusMüller 不,指针有迭代器特性。它是有效的实现随机访问迭代器的方法,据我所知(除非在C++11中发生了变化)。 - juanchopanza

3
使用指针的原因在于减少开销,提高性能,尤其是如果优化编译器检测到迭代并进行优化(矢量指令等)。使用迭代器可能更难为编译器优化。但实际上并非如此。如果你的实现不是完全糟糕的话,一个包装指针的结构体将达到相同的速度。
考虑到这一点,很容易看出像更好的诊断消息(命名迭代器而不是T *),更好的重载分辨率,ADL和调试检查使结构体比指针成为明显的赢家。裸指针没有任何优势。

2
使用指针的理由是减少开销,提高性能,特别是如果优化编译器检测到迭代并执行其操作(矢量指令等)。使用迭代器可能更难为编译器优化。
这就是问题的核心误解。一个良好的类实现不会有任何开销,并且具有相同的性能,因为编译器可以优化掉抽象,并将迭代器类视为std::vector中的指针。
话虽如此,
因为他们认为在定义对std::vector进行迭代的概念时,添加一个抽象层class iterator比使用普通指针更有益。
抽象具有不同的成本与收益,通常增加设计复杂性(不一定与性能或开销相关),以换取灵活性、未来证明和隐藏实现细节。上述编译器决定,这种增加的复杂性是为了获得抽象的好处而付出的适当代价。

1
因为STL的设计理念是,你可以编写一个迭代器来迭代所有类型的迭代器,无论这个迭代器是否等价于指向内存连续数组元素的指针(例如std::array或std::vector),还是像链表、一组键、在访问时动态生成的内容等。此外,不要被骗:在向量的情况下,解引用可能会(没有调试选项的情况下)只会崩溃为可内联的指针解引用,因此即使在编译后也不会有开销!

5
我不明白这如何回答问题。使用指针同样可以很好地执行所有迭代操作。对于许多容器来说,迭代器不能是一个简单的指针,但在 std::vector 中,这实际上是可能的。 - Walter
2
@MarcusMüller 这仍然没有回答问题。指针作为随机访问迭代器可以很好地工作。实现可以很好地使用指针,我所能想到的唯一变化的是 ADL 将不起作用,除非实现可以在 std 命名空间内定义指针类型。但据我所知,并没有任何东西说指针不能被使用。 - juanchopanza
3
@MarcusMüller 好的,你在这里没有提出那个论点。 - juanchopanza
1
@juanchopanza:我非常确定,“无论该迭代器只是等同于指针[...]还是类似于链表[...]”都意味着一致性的参数! - Marcus Müller
2
我相信可以提出一个很好的论点,即它意味着普通指针是可以的,因为它满足前向迭代器的所有要求。你的第一段没有解释为什么在大多数最新、流行的实现中std::vector::iterator不是指针。正如已经提到的,它并没有回答这个问题。 - juanchopanza
显示剩余5条评论

0
我认为原因很简单:最初未要求用连续的内存块实现std::vector。因此,接口不能只提供指针。
来源:https://dev59.com/g3RA5IYBdhLWcg3wuAcp#849190 稍后修复了这个问题,并要求std::vector在连续内存中实现,但可能为时已晚,无法将std::vector<T> :: iterator 设置为指针。也许有些代码已经依赖于iterator是一个class/struct
有趣的是,我发现了一些实现std::vector<T> :: iterator的方法,其中这是有效的并且生成了“null”迭代器(就像空指针一样)it = {}; 。
    std::vector<double>::iterator it = {};
    assert( &*it == nullptr );

此外,我看到的实现中std::array<T>::iteratorstd::initializer_list<T>::iterator 指针T*
理论上,一个普通指针像std::vector<T>::iterator是完全可以的。但在实践中,作为内置类型对元编程有可观察的影响(例如std::vector<T>::iterator::difference_type将无效,应该使用iterator_traits)。
不作为原始指针具有(非常)微小的优势,可以禁止null性(it == nullptr)或默认行为(如果您喜欢的话)。(这个论点从泛型编程的角度来看并不重要。)

同时,专用类迭代器在其他元编程方面的成本很高,因为如果::iterator是一个指针,就不需要有特定的方法来检测连续内存(请参见https://en.cppreference.com/w/cpp/iterator/iterator_tags中的contiguous_iterator_tag),并且可以直接将通用代码传递到遗留C函数。

仅出于这个原因,我认为迭代器不是指针是一个昂贵的错误。这使得与C代码交互变得困难(因为您需要另一层函数和类型检测来安全地将内容转发到C)。

话虽如此,我认为我们仍然可以通过允许从迭代器自动转换为指针以及可能的显式(?)从指针转换为vector :: iterators来改进事情。


-1

我通过对迭代器进行解引用并立即重新引用来绕过这个讨厌的障碍。看起来很荒谬,但它满足了MSVC...

class Thing {
  . . .
};

void handleThing(Thing* thing) {
  // do stuff
}

vector<Thing> vec;
// put some elements into vec now

for (auto it = vec.begin(); it != vec.end(); ++it)
  // handleThing(it);   // this doesn't work, would have been elegant ..
  handleThing(&*it);    // this DOES work

1
这并没有回答问题。这不是一个“讨厌的障碍”,而是确保您实际获得指针所需做的事情,因为迭代器不一定是指针,并且其他(实际)答案已经提供了非常好的理由来解释为什么不应该这样做。显然,更好的模式是取Thing&并传递*it。还要注意,在元素类型可能重载operator&(不建议)的通用情况下,您的代码将无法工作。 - underscore_d
这个方案可行且合理。不过需要稍微澄清一下术语:一旦您对迭代器进行解引用(*),您现在就是在引用对象本身。因此,取地址符(&)是指向对象的指针,但不是迭代器。 - Jonathan Lidbeck

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接