8

我在 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]情况，位置上的迭代器都不会指向比, wheren - m更远离同一向量开头的元素。nm > 0

从原始向量中擦除元素时，我必须将 reverse_iterator 转换为迭代器。为此，我依赖 C++11 的 §24.4.1/1：

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

这意味着要删除 a vect_rit，我使用：

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

现在，根据 C++11 标准§23.3.6.5/3：

迭代器擦除（const_iterator 位置）；效果：在擦除点或擦除点之后使迭代器和引用无效。

这如何与 reverse_iterators 一起使用？vector[0]reverse_iterators是否在内部通过引用向量的真实开始（或者 reverse_iterator 是否使用 rbegin() （即vector[vector.size()]）作为参考点并删除任何远离向量 0-index 的内容仍然会使我的反向迭代器无效？

编辑：

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

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

谢谢！

4

3 回答 3

3

从标准的角度来看（我承认，我不是该标准的专家）：来自 §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.

因此，在我看来，只要您在您的某个s 指向的内容vector之前不删除任何内容，就应该保持有效。reverse_iteratorreverse_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 没有做过这样的事情吗？），并且可能会对你大喊大叫。

于 2012-07-15T08:01:18.987 回答
3

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

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

请记住，a只是底层迭代器 ( )reverse_iterator之上的“适配器” 。reverse_iterator::current正如你所说，'参考点'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的基数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));
于 2012-07-15T09:21:56.237 回答
0

reverse_iterator就像 normal 一样iterator，指向向量中的某个位置。实现细节无关紧要，但如果您必须知道，它们（在典型实现中）都只是内部的普通旧指针。不同的是方向。反向迭代器+与-常规迭代器（以及++and --，>等等<）相反。

这很有趣，但并不意味着对主要问题的回答。

如果您仔细阅读该语言，它会说：

在擦除点或之后使迭代器和引用无效。

引用没有内置的方向感。因此，语言显然是指容器自身的方向感。擦除点之后的位置是具有较高索引的位置。因此，迭代器的方向在这里是无关紧要的。

于 2012-07-15T09:09:03.887 回答