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.常規迭代器（還有++和--,>和<等）。

這是有趣的知道，但並不真正意味着對主要問題的答案。

如果你仔細閱讀的語言，它說：

迭代器失效和參考在或擦除的後點。

參考文獻沒有內置的方向感。因此，該語言清楚地指出了集裝箱自己的方向感。擦除點之後的位置是指數較高的位置。因此，這裏迭代器的方向是不相關的。