vector :: erase and 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_iterator，并引用了矢量的真实开始（vector[0]）并将该vect_rit转换为经典迭代器，然后擦除将是安全的？或者根本reverse_iterator的使用rbegin（）（这是vector[vector.size()]）作为参考点，并删除任何进一步的距离向量的0指数仍然会失效我的反向迭代器？

编辑：

貌似reverse_iterator的使用rbegin（）作为它的基准点。按照我描述的方式擦除元素在第一个元素被删除后给我提供了有关不可引用的迭代器的错误。而当存储经典迭代器（转换为const_iterator），而插入到what_to_delete正常工作。

现在，以供将来参考，不标准规定什么应该在随机存取reverse_iterator的情况下的参考点来处理？或者这是一个实现细节？

谢谢！

Answer 1

在你已经完全引用问题的标准说什么reverse_iterator是：

reverse_iterator的和迭代器之间的关系是& *（reverse_iterator的（I））== & *（I-1）

记住一个reverse_iterator仅仅是一个底层迭代器（reverse_iterator::current）“的顶部适配器”。正如你所说的，参考点reverse_iterator就是那个包装迭代器，current。 reverse_iterator上的所有操作确实发生在该基础迭代器上。您可以使用reverse_iterator::base()函数获取该迭代器。

如果您擦除--vect_rit.base()，则实际上擦除了--current，因此current将会失效。

作为一个附注，表达式--vect_rit.base()可能并不总是编译。如果迭代器实际上只是一个原始指针（vector的情况可能如此），那么vect_rit.base()返回一个右值（以C++ 11术语为前值），所以预递减运算符将无法工作，因为运营商需要一个可修改的左值。请参阅Scott Meyers的“Effective STL”中的“项目28：了解如何使用reverse_iterator的基地iterator”。 （该项目的早期版本可以在http://www.drdobbs.com/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)); 

Answer 2

从一个standardese点（我得承认，我不是在标准方面的专家）：从§24.5.1。1：

namespace std { 
    template <class Iterator> 
    class reverse_iterator ... 
    { 
     ... 
      Iterator base() const; // explicit 
     ... 
     protected: 
      Iterator current; 
     ... 
    }; 
} 

而且从§24.5.1.3.3：

Iterator base() const; // explicit 
    Returns: current. 

因此，在我看来，只要你不要在你的reverse_iterator S的什么人抹去的vector什么指出，reverse_iterator应该保持有效。

当然，根据你的描述，有一个问题：如果你的向量中有两个连续的元素，你最终想要删除，那么你的vector.erase(--vector_rit.base())意味着你已经使reverse_iterator“指向”直接前面的元素，所以你的下一个vector.erase(...)是未定义的行为。

万一是十分明显的泥，我要说的是不同的：

std::vector<T> v=...; 
... 
// it_1 and it_2 are contiguous 
std::vector<T>::reverse_iterator it_1=v.rend(); 
std::vector<T>::reverse_iterator it_2=it_1; 
--it_2; 

// Erase everything after it_1's pointee: 

// convert from reverse_iterator to iterator 
std::vector<T>::iterator tmp_it=it_1.base(); 

// but that points one too far in, so decrement; 
--tmp_it; 

// of course, now tmp_it points at it_2's base: 
assert(tmp_it == it_2.base()); 

// perform erasure 
v.erase(tmp_it); // invalidates all iterators pointing at or past *tmp_it 
        // (like, say it_2.base()...) 

// now delete it_2's pointee: 
std::vector<T>::iterator tmp_it_2=it_2.base(); // note, invalid iterator! 

// undefined behavior: 
--tmp_it_2; 
v.erase(tmp_it_2); 

---

在实践中，我怀疑你会碰到两种可能的实现：更常见的，底层的iterator会只不过是一个（适当包装的）原始指针，所以一切都会很愉快地工作。通常情况下，迭代器可能会尝试跟踪失效/执行边界检查（在调试模式下编译时，Dinkumware STL不会执行此类操作吗？），并且可能会对您大喊大叫。

Answer 3

reverse_iterator就像正常的iterator一样，指向向量中的某个位置。实现细节是不相关的，但如果你必须知道，它们都是（在典型的实现中）里面的普通旧指针。不同的是方向。反向迭代器的+和-颠倒了w.r.t.常规迭代器（还有++和--,>和<等）。

这是有趣的知道，但并不真正意味着对主要问题的答案。

如果你仔细阅读的语言，它说：

迭代器失效和参考在或擦除的后点。

参考文献没有内置的方向感。因此，该语言清楚地指出了集装箱自己的方向感。擦除点之后的位置是指数较高的位置。因此，这里迭代器的方向是不相关的。