C++(stl)与Java中的迭代器是否存在概念上的差异？

Question

我离开了一会儿,试图把老瓜弄脏之后回到c ++.

在Java中,Iterator是具有方法的容器的接口:hasNext(),next()和remove().hasNext()的存在意味着它具有对遍历容器的限制的概念.

//with an Iterator
Iterator<String> iter = trees.iterator();
while (iter.hasNext()) 
{
    System.out.println(iter.next());
}

在C++标准模板库中,迭代器似乎表示支持operator ++和operator ==的数据类型或类,但没有内置限制的概念,因此在前进到下一个项目之前需要进行比较.用户必须检查限制,比较正常情况下的两个迭代器,第二个迭代器是容器端.

vector<int> vec;
vector<int>::iterator iter;

// Add some elements to vector
v.push_back(1);
v.push_back(4);
v.push_back(8);

for(iter= v.begin(); iter != v.end(); iter++)
{
    cout << *i << " "; //Should output 1 4 8
}

这里有趣的部分是在C++中,指针是数组的迭代器.STL采用了现有的并围绕它构建惯例.

有什么进一步的细微之处,我失踪了吗？

Answer 1

也许更理论化一点.在数学上,C++中的集合可以描述为迭代器的半开区间,即一个指向集合开头的迭代器和一个指向最后一个元素后面的迭代器.

这一惯例开辟了许多可能性.算法在C++中的工作方式,它们都可以应用于更大集合的子序列.要使这样的东西在Java中工作,你必须围绕一个返回不同迭代器的现有集合创建一个包装器.

Frank已经提到了迭代器的另一个重要方面.迭代器有不同的概念.Java迭代器对应于C++的输入迭代器,即它们是只读迭代器,它们一次只能递增一步而不能倒退.

另一方面,你有C指针,它们完全符合C++的随机访问迭代器概念.

总而言之,C++提供了更丰富,更纯粹的概念,可以应用于比C指针或Java迭代器更广泛的任务.

Answer 2

是的,存在很大的概念差异.C++使用不同的"类"迭代器.一些用于随机访问(与Java不同),一些用于前向访问(如java).甚至其他人也用于写数据(例如,用于transform).

请参阅C++文档中的迭代器概念:

• 输入迭代器
• 输出迭代器
• 转发迭代器
• 双向迭代器
• 随机访问迭代器

与Java/C#的微弱迭代器相比,它们更有趣,更强大.希望这些约定将使用C++ 0x的概念进行编码.

Answer 3

如前所述,Java和C#迭代器描述了混合位置(状态)和范围(值),而C++迭代器分隔了位置和范围的概念.C++迭代器代表'我现在在哪里'与"我可以去哪里？"分开.

Java和C#迭代器无法复制.你无法恢复以前的位置.常见的C++迭代器可以.

考虑这个例子:

// for each element in vec
for(iter a = vec.begin(); a != vec.end(); ++a){
  // critical step!  We will revisit 'a' later.
  iter cur = a; 
  unsigned i = 0;
  // print 3 elements
  for(; cur != vec.end() && i < 3; ++cur, ++i){
      cout << *cur << " ";
  }
  cout << "\n";
}

单击上面的链接以查看程序输出.

这个相当愚蠢的循环遍历一个序列(仅使用前向迭代器语义),只打印3个元素的每个连续子序列一次(以及最后几个较短的子序列).但是假设N个元素和每行M个元素而不是3个,这个算法仍然是O(N*M)迭代器增量和O(1)空间.

Java样式迭代器缺乏独立存储位置的能力.你要么

• 丢失O(1)空间,使用(例如)大小为M的数组来存储迭代时的历史记录
• 将需要遍历列表N次,使O(N ^ 2 + N*M)时间
• 或者使用具有GetAt成员函数的具体Array类型,失去泛型和使用链表容器类型的能力.

由于在此示例中仅使用了正向迭代机制,因此我能够在列表中交换没有问题.这对于编写通用算法至关重要,例如搜索,延迟初始化和评估,排序等.

无法保留状态最接近于C++ STL输入迭代器,在该迭代器上构建的算法非常少.

Answer 4

指向数组元素的指针确实是数组的迭代器.

正如您所说,在Java中,迭代器比C++更了解底层容器.C++迭代器是通用的,一对迭代器可以表示任何范围:这可以是容器的子范围,多个容器的范围(参见http://www.justsoftwaresolutions.co.uk/articles/pair_iterators.pdf)或者http://www.boost.org/doc/libs/1_36_0/libs/iterator/doc/zip_iterator.html)甚至是一系列数字(参见http://www.boost.org/doc/libs/1_36_0) /libs/iterator/doc/counting_iterator.html)

迭代器类别标识了给定迭代器可以做什么和不做什么.