vector :: xóa và đảo ngược_iterator

Question

Tôi có một tập hợp các phần tử trong một std :: vector được sắp xếp theo thứ tự giảm dần bắt đầu từ phần tử đầu tiên. Tôi phải sử dụng một vector vì tôi cần phải có các phần tử trong một bộ nhớ liền kề. Và tôi có một bộ sưu tập chứa nhiều trường hợp vectơ với các đặc tính được mô tả (luôn được sắp xếp theo thứ tự giảm dần). Bây giờ, đôi khi, khi tôi phát hiện ra rằng tôi có quá nhiều phần tử trong bộ sưu tập lớn hơn (bộ chứa các vectơ này), tôi loại bỏ các phần tử nhỏ nhất khỏi các vectơ này theo cách tương tự với mã giả này:

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()); 
     // ... 
    } 
} 

Bây giờ, sau khi chạy mã này, trong what_to_delete Tôi có một tập hợp các trình vòng lặp trỏ đến vectơ gốc mà tôi muốn xóa khỏi các vectơ này (tổng giá trị nhỏ nhất). Hãy nhớ rằng, các vectơ gốc được sắp xếp trước khi chúng đạt mã này, có nghĩa là đối với bất kỳ what_to_delete[0 - n] không có cách nào mà một trình lặp trên vị trí n - m sẽ trỏ đến một phần tử từ đầu của cùng một véc tơ hơn n, trong đó m > 0.

Khi xóa các phần tử khỏi vectơ gốc, tôi phải chuyển đổi trình đảo ngược thành bộ lặp. Để làm điều này, tôi dựa trên C++ của 11 §24.4.1/1:

Mối quan hệ giữa reverse_iterator và iterator là & * (reverse_iterator (i)) == & * (i- 1)

có nghĩa là để xóa một vect_rit, tôi sử dụng:

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

Bây giờ, theo C++ 11 tiêu chuẩn §23.3.6.5/3:

xóa vòng lặp (vị trí trình giữ nguyên); Hiệu ứng: Vô hiệu hóa trình lặp và tham chiếu tại hoặc sau thời điểm xóa.

Điều này hoạt động như thế nào với trình đảo ngược? Là reverse_iterators nội bộ thực hiện với một tham chiếu đến một bắt đầu thực sự của vector (vector[0]) và chuyển đổi vect_rit đó để một iterator cổ điển để sau đó tẩy xoá sẽ được an toàn? Hoặc không reverse_iterator sử dụng rbegin() (là (vector[vector.size()]) như là một điểm tham chiếu và xóa bất cứ điều gì đó là xa hơn từ 0-chỉ số của vector sẽ vẫn làm mất hiệu lực iterator đảo ngược của tôi?

Edit:

Hình như reverse_iterator sử dụng rbegin() là điểm tham chiếu của nó. Việc xóa các phần tử theo cách tôi mô tả đã cho tôi lỗi về một trình lặp không thể tránh khỏi sau khi phần tử đầu tiên bị xóa. Trong khi khi lưu trữ các trình vòng lặp cổ điển (chuyển đổi thành const_iterator) trong khi chèn vào what_to_delete hoạt động chính xác.

Bây giờ, để tham khảo trong tương lai, tiêu chuẩn có quy định cụ thể những gì cần được coi là điểm tham chiếu trong trường hợp của reverse_iterator truy cập ngẫu nhiên không? Hoặc đây là một chi tiết thực hiện?

Cảm ơn!

Answer 1

Trong câu hỏi mà bạn đã trích dẫn chính xác những gì tiêu chuẩn nói một reverse_iterator là:

Mối quan hệ giữa reverse_iterator và iterator là & * (reverse_iterator (i)) == & * (i- 1)

Hãy nhớ rằng reverse_iterator chỉ là 'bộ điều hợp' trên đầu trình lặp cơ bản (reverse_iterator::current). 'Điểm tham chiếu', khi bạn đặt nó, cho một reverse_iterator là trình vòng lặp được bọc, current. Tất cả các hoạt động trên reverse_iterator thực sự xảy ra trên trình lặp lặp cơ bản đó.Bạn có thể lấy trình lặp đó bằng cách sử dụng hàm reverse_iterator::base().

Nếu bạn xóa --vect_rit.base(), bạn đang có hiệu lực xóa --current, vì vậy current sẽ bị vô hiệu.

Lưu ý phụ, biểu thức --vect_rit.base() có thể không phải lúc nào cũng biên dịch. Nếu trình vòng lặp thực sự chỉ là một con trỏ thô (có thể là trường hợp cho một vector), thì vect_rit.base() trả về một giá trị (một giá trị bằng các thuật ngữ C++ 11), vì vậy toán tử giảm trước sẽ không hoạt động vì nó toán tử cần một giá trị thay đổi. Xem "Mục 28: Hiểu cách sử dụng cơ sở iterator" trong "Hiệu quả STL" của Scott Meyers. (một phiên bản đầu tiên của mục có thể được tìm thấy trực tuyến trong "Hướng dẫn 3" của http://www.drdobbs.com/three-guidelines-for-effective-iterator/184401406).

Bạn có thể sử dụng biểu thức thậm chí xấu hơn, (++vect_rit).base(), để tránh sự cố đó. Hoặc vì bạn đang xử lý một véc tơ và các trình vòng lặp truy cập ngẫu nhiên: vect_rit.base() - 1

Dù bằng cách nào, vect_rit bị vô hiệu hóa do xóa vì vect_rit.current không hợp lệ.

Tuy nhiên, hãy nhớ rằng vector::erase() trả về trình lặp lại hợp lệ cho vị trí mới của phần tử theo sau phần tử vừa bị xóa. Bạn có thể sử dụng tính năng đó để 'đồng bộ hóa lại' vect_rit:

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

Answer 2

Từ quan điểm tiêu chuẩn (và tôi sẽ thừa nhận, tôi không phải là chuyên gia về tiêu chuẩn): Từ §24.5.1.1:

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

Và từ §24.5.1.3.3:

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

Như vậy có vẻ như với tôi rằng chừng nào bạn không xóa bất cứ điều gì trong vector trước những gì một trong reverse_iterator của bạn trỏ đến, cho biết reverse_iterator sẽ vẫn hợp lệ. Tất nhiên, với mô tả của bạn, có một sự bắt giữ: nếu bạn có hai phần tử tiếp giáp trong vectơ mà bạn muốn xóa, thực tế là bạn vector.erase(--vector_rit.base()) có nghĩa là bạn đã vô hiệu hóa số reverse_iterator "trỏ" đến yếu tố preceeding ngay lập tức, và vì vậy vector.erase(...) tiếp theo của bạn là hành vi không xác định.

Chỉ trong trường hợp đó là rõ ràng như bùn, hãy để tôi nói rằng cách khác nhau:

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); 

---

Trong thực tế, tôi nghi ngờ rằng bạn sẽ chạy thành hai thực hiện khác nhau: thường hơn, tiềm ẩn iterator sẽ ít hơn một con trỏ thô (được bọc một cách thích hợp), và vì vậy mọi thứ sẽ hoạt động hoàn hảo một cách hạnh phúc. Ít phổ biến, các iterator thực sự có thể cố gắng theo dõi vô hiệu hóa/thực hiện kiểm tra giới hạn (không Dinkumware STL làm những việc như vậy khi biên dịch trong chế độ gỡ lỗi tại một thời điểm?), Và chỉ có thể la lên với bạn.

Answer 3

reverse_iterator, giống như bình thường iterator, trỏ đến một vị trí nhất định trong vectơ. Chi tiết thực hiện không liên quan, nhưng nếu bạn phải biết, cả hai đều là (trong một thực hiện điển hình) chỉ là con trỏ cũ đồng bằng bên trong. Sự khác biệt là hướng. Trình lặp ngược lại có + và - đảo ngược w.r.t. trình lặp thường xuyên (và cũng là ++ và --, > và < v.v.).

Điều này thật thú vị khi biết, nhưng không thực sự hàm ý câu trả lời cho câu hỏi chính.

Nếu bạn đọc các ngôn ngữ một cách cẩn thận, nó nói:

làm mất hiệu lực lặp và tài liệu tham khảo tại hoặc sau điểm của xóa.

Tài liệu tham khảo không có ý nghĩa về hướng. Do đó, ngôn ngữ rõ ràng đề cập đến ý nghĩa riêng của container. Vị trí sau điểm xóa là những vị trí có chỉ số cao hơn. Do đó, hướng của trình vòng lặp không liên quan ở đây.