vector :: erase和reverse_iterator-Java 学习之路

我在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的内容仍然会使我的反向迭代器无效？

Edit:

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

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

谢谢！

3 回答

2
在这个问题中你已经引用了标准所说的 reverse_iterator ：

reverse_iterator和迭代器之间的关系是＆（reverse_iterator（i））==＆（i-1）

请记住， reverse_iterator 只是底层迭代器（ reverse_iterator::current ）之上的'adaptor' . 'reference point'，正如你所说， reverse_iterator 是包装的迭代器， current . reverse_iterator 上的所有操作都发生在该底层迭代器上 . 您可以使用 reverse_iterator::base() 函数获取该迭代器 .

如果删除 --vect_rit.base() ，则表示您正在删除 --current ，因此 current 将无效 .

作为旁注，表达式 --vect_rit.base() 可能并不总是编译 . 如果迭代器实际上只是一个原始指针（可能是 vector 的情况），则 vect_rit.base() 返回一个rvalue（以C 11术语表示的prvalue），因此预递减运算符将不会对它起作用，因为该运算符需要一个可修改的左值 . 参见“项目28：了解如何使用 iterator 的基础 iterator " in "有效STL " by Scott Meyers. (an early version of the item can be found online in "指南3”http://www.drdobbs.com/three-guidelines-for-effective-iterator/184401406） .

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

无论哪种方式， vect_rit 都被擦除无效，因为 vect_rit.current 无效 .

但是，请记住 vector::erase() 将有效迭代器返回到刚删除的元素之后的元素的新位置 . 您可以使用它来're-synchronize' vect_rit ：
```
vect_rit = vector_type::reverse_iterator( vector.erase(vect_rit.base() - 1));
```
回复于 2024-04-27T08:01:14+08:00
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.
```
因此，在我看来，只要你在 reverse_iterator 指向之前没有删除_2896733中的任何内容，就说 reverse_iterator 应该仍然有效 .

当然，根据你的描述，有一个问题：如果你的向量中有两个连续的元素，你最终想要删除，那么你 vector.erase(--vector_rit.base()) 意味着你已经使 reverse_iterator "pointing"无效到了前一个元素，所以你的下一个 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在调试模式下一次编译时没有这样做吗？），并且可能会对你大喊大叫 .
回复于 2024-04-27T08:01:14+08:00
0

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

这很有趣，但并不能真正暗示对主要问题的回答 .

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

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

参考文献没有内置的方向感 . 因此，语言清楚地指的是容器自身的方向感 . 擦除点之后的位置是具有较高索引的位置 . 因此，迭代器的方向在这里是无关紧要的 .

回复于 2024-04-27T08:01:14+08:00

vector :: erase和reverse_iterator

3 回答

相关问题