vector :: erase和reverse_iterator

Question

我在std :: vector中有一个元素集合,它们从第一个元素开始按降序排序.我必须使用向量,因为我需要将元素放在连续的内存块中.我有一个集合,其中包含许多具有所述特征的向量实例(总是按降序排序).

现在,有时,当我发现我在更大的集合中有太多元素(持有这些向量的元素)时,我丢弃这些向量中的最小元素,类似于这个伪代码:

grand_collection: collection that holds these vectors
T: type argument of my vector
C: the type that is a member of T, that participates in the < comparison (this is what sorts data before they hit any of the vectors).

std::map<C, std::pair<T::const_reverse_iterator, std::vector<T>&>> what_to_delete;
iterate(it = grand_collection.begin() -> grand_collection.end())
{
     iterate(vect_rit = it->rbegin() -> it->rend())
     {
         // ...
          what_to_delete <- (vect_rit->C, pair(vect_rit, *it))
          if (what_to_delete.size() > threshold)
               what_to_delete.erase(what_to_delete.begin());
         // ...  
     }
}

现在,在运行此代码之后,what_to_delete我有一组迭代器指向我想从这些向量中移除的原始向量(总体最小值).请记住,原始向量在它们命中此代码之前进行排序,这意味着对于任何what_to_delete[0 - n]位置上的迭代器n - m都无法指向距离相同向量的开头更远的元素n,而不是在哪里m > 0.

从原始向量中删除元素时,我必须将reverse_iterator转换为迭代器.为此,我依赖于C++ 11的§24.4.1/ 1:

reverse_iterator和迭代器之间的关系是&*(reverse_iterator(i))==&*(i-1)

这意味着要删除一个vect_rit,我使用:

vector.erase(--vect_rit.base());

现在,根据C++ 11标准§23.3.6.5/3:

迭代器擦除(const_iterator位置); 效果:在擦除点处或之后使迭代器和引用无效.

这如何与reverse_iterators一起使用？reverse_iterators是在内部实现的,引用了向量的真实开头(vector[0])并将该vect_rit转换为经典迭代器,这样擦除是否安全？或者reverse_iterator使用rbegin()(它vector[vector.size()])作为参考点并删除任何远离vector 0-index的东西仍会使我的反向迭代器无效？

编辑:

看起来像reverse_iterator使用rbegin()作为其参考点.以我描述的方式擦除元素在删除第一个元素后给出了关于非可引用迭代器的错误.而在const_iterator插入时存储经典迭代器(转换为)以what_to_delete正常工作.

现在,为了将来参考,标准是否指定在随机访问reverse_iterator的情况下应该将哪些视为参考点？或者这是一个实现细节？

谢谢!

Answer 1

在问题中，您已经准确引用了标准所说的 areverse_iterator是什么：

verse_iterator 和 iterator 的关系是 &*(reverse_iterator(i)) == &*(i- 1)

请记住，areverse_iterator只是底层迭代器 ( ) 之上的一个“适配器” reverse_iterator::current。正如您所说， a 的“参考点”reverse_iterator是包装的迭代器current。对 的所有操作实际上都reverse_iterator发生在该底层迭代器上。您可以使用该函数获取该迭代器reverse_iterator::base()。

如果你擦除--vect_rit.base()，你实际上是在擦除--current，所以current会失效。

附带说明一下，该表达式--vect_rit.base()可能并不总是可以编译。如果迭代器实际上只是一个原始指针（a 可能就是这种情况vector），则vect_rit.base()返回一个右值（C++11 术语中的纯右值），因此预自减运算符将无法处理它，因为该运算符需要可修改的左值。请参阅Scott Meyers 的《Effective STL》中的“第 28 条：了解如何使用 areverse_iterator的基数”。（该项目的早期版本可以在http://www.drdobbs.com/iterator Three-guidelines-for- effective-iterator/184401406 的“指南 3”中找到）。

您可以使用更丑陋的表达式(++vect_rit).base()来避免该问题。或者因为您正在处理向量和随机访问迭代器：vect_rit.base() - 1

无论哪种方式，vect_rit都会因擦除而失效，因为vect_rit.current已失效。

但是，请记住，它vector::erase()会将一个有效的迭代器返回到刚刚被删除的元素后面的元素的新位置。您可以使用它来“重新同步” vect_rit：

vect_rit = vector_type::reverse_iterator( vector.erase(vect_rit.base() - 1));