Menghapus elemen dari std :: set saat iterasi

Saya perlu melalui satu set dan menghapus elemen yang memenuhi kriteria yang telah ditentukan.

Ini adalah kode tes yang saya tulis:

#include <set>
#include <algorithm>

void printElement(int value) {
    std::cout << value << " ";
}

int main() {
    int initNum[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    std::set<int> numbers(initNum, initNum + 10);
    // print '0 1 2 3 4 5 6 7 8 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    std::set<int>::iterator it = numbers.begin();

    // iterate through the set and erase all even numbers
    for (; it != numbers.end(); ++it) {
        int n = *it;
        if (n % 2 == 0) {
            // wouldn't invalidate the iterator?
            numbers.erase(it);
        }
    }

    // print '1 3 5 7 9'
    std::for_each(numbers.begin(), numbers.end(), printElement);

    return 0;
}

Pada awalnya, saya berpikir bahwa menghapus elemen dari set sementara iterasi melalui itu akan membatalkan iterator, dan kenaikan pada for loop akan memiliki perilaku yang tidak terdefinisi. Meskipun demikian, saya menjalankan kode tes ini dan semuanya berjalan dengan baik, dan saya tidak bisa menjelaskan mengapa.

Pertanyaan saya: Apakah ini perilaku yang ditentukan untuk set std atau apakah implementasi ini spesifik? Saya menggunakan gcc 4.3.3 di ubuntu 10.04 (versi 32-bit), omong-omong.

Terima kasih!

Solusi yang diusulkan:

Apakah ini cara yang benar untuk mengulang dan menghapus elemen dari set?

while(it != numbers.end()) {
    int n = *it;
    if (n % 2 == 0) {
        // post-increment operator returns a copy, then increment
        numbers.erase(it++);
    } else {
        // pre-increment operator increments, then return
        ++it;
    }
}

Sunting: SOLUSI YANG DITENTUKAN

Saya menemukan solusi yang tampaknya lebih elegan bagi saya, meskipun tidak persis sama.

while(it != numbers.end()) {
    // copy the current iterator then increment it
    std::set<int>::iterator current = it++;
    int n = *current;
    if (n % 2 == 0) {
        // don't invalidate iterator it, because it is already
        // pointing to the next element
        numbers.erase(current);
    }
}

Jika ada beberapa kondisi pengujian di dalam sementara, masing-masing harus meningkatkan iterator. Saya lebih suka kode ini karena iterator hanya bertambah di satu tempat , membuat kode lebih sedikit rawan kesalahan dan lebih mudah dibaca.

Ini tergantung pada implementasi:

Standar 23.1.2.8:

Anggota penyisipan tidak akan mempengaruhi validitas iterator dan referensi ke wadah, dan anggota yang dihapus hanya akan membatalkan iterator dan referensi untuk elemen yang dihapus.

Mungkin Anda bisa mencoba ini - ini sesuai standar:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        numbers.erase(it++);
    }
    else {
        ++it;
    }
}

Perhatikan bahwa ini ++ adalah postfix, karena itu ia melewatkan posisi lama untuk dihapus, tetapi pertama-tama melompat ke posisi yang lebih baru karena operator.

Pembaruan 2015.10.27: C ++ 11 telah menyelesaikan cacat. iterator erase (const_iterator position);kembalikan iterator ke elemen yang mengikuti elemen terakhir dihapus (atau set::end, jika elemen terakhir dihapus). Jadi gaya C ++ 11 adalah:

for (auto it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
        it = numbers.erase(it);
    }
    else {
        ++it;
    }
}

Jika Anda menjalankan program Anda melalui valgrind, Anda akan melihat banyak kesalahan baca. Dengan kata lain, ya, iterator sedang tidak valid, tetapi Anda beruntung dalam contoh Anda (atau benar-benar sial, karena Anda tidak melihat efek negatif dari perilaku yang tidak terdefinisi). Salah satu solusi untuk ini adalah membuat iterator sementara, menambah temp, menghapus iterator target, lalu mengatur target ke temp. Misalnya, tulis ulang loop Anda sebagai berikut:

std::set<int>::iterator it = numbers.begin();                               
std::set<int>::iterator tmp;                                                

// iterate through the set and erase all even numbers                       
for ( ; it != numbers.end(); )                                              
{                                                                           
    int n = *it;                                                            
    if (n % 2 == 0)                                                         
    {                                                                       
        tmp = it;                                                           
        ++tmp;                                                              
        numbers.erase(it);                                                  
        it = tmp;                                                           
    }                                                                       
    else                                                                    
    {                                                                       
        ++it;                                                               
    }                                                                       
} 

Anda salah mengerti apa arti "perilaku tidak terdefinisi". Perilaku yang tidak terdefinisi tidak berarti "jika Anda melakukan ini, program Anda akan macet atau menghasilkan hasil yang tidak terduga." Ini berarti "jika Anda melakukan ini, program Anda bisa crash atau menghasilkan hasil yang tidak terduga", atau melakukan hal lain, tergantung pada kompiler Anda, sistem operasi Anda, fase bulan, dll.

Jika sesuatu dijalankan tanpa menabrak dan berperilaku seperti yang Anda harapkan, itu bukan bukti bahwa itu bukan perilaku yang tidak terdefinisi. Semua itu membuktikan bahwa perilakunya kebetulan diamati selama menjalankan tertentu setelah dikompilasi dengan kompiler tertentu pada sistem operasi tertentu.

Menghapus elemen dari set akan membatalkan iterator ke elemen yang terhapus. Menggunakan iterator yang tidak valid adalah perilaku yang tidak terdefinisi. Kebetulan bahwa perilaku yang diamati adalah apa yang Anda maksudkan dalam contoh khusus ini; itu tidak berarti bahwa kodenya benar.

Hanya untuk memperingatkan, bahwa dalam kasus wadah deque, semua solusi yang memeriksa kesetaraan deer iterator untuk angka.end () kemungkinan akan gagal pada gcc 4.8.4. Yaitu, menghapus elemen dari deque umumnya membatalkan pointer ke numbers.end ():

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  //numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Keluaran:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is not anymore pointing to numbers.end()

Perhatikan bahwa sementara transformasi deque benar dalam kasus khusus ini, penunjuk akhir telah dibatalkan di sepanjang jalan. Dengan deque dengan ukuran berbeda kesalahannya lebih jelas:

int main() 
{

  deque<int> numbers;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  deque<int>::iterator  it_end = numbers.end();

  for (deque<int>::iterator it = numbers.begin(); it != numbers.end(); ) {
    if (*it % 2 == 0) {
      cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      if (it_end == numbers.end()) {
    cout << "it_end is still pointing to numbers.end()\n";
      } else {
    cout << "it_end is not anymore pointing to numbers.end()\n";
      }
    }
    else {
      cout << "Skipping element: " << *it << "\n";
      ++it;
    }
  }
}

Keluaran:

Erasing element: 0
it_end is still pointing to numbers.end()
Skipping element: 1
Erasing element: 2
it_end is still pointing to numbers.end()
Skipping element: 3
Erasing element: 4
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
Erasing element: 0
it_end is not anymore pointing to numbers.end()
...
Segmentation fault (core dumped)

Berikut adalah salah satu cara untuk memperbaikinya:

#include <iostream>
#include <deque>

using namespace std;
int main() 
{

  deque<int> numbers;
  bool done_iterating = false;

  numbers.push_back(0);
  numbers.push_back(1);
  numbers.push_back(2);
  numbers.push_back(3);
  numbers.push_back(4);

  if (!numbers.empty()) {
    deque<int>::iterator it = numbers.begin();
    while (!done_iterating) {
      if (it + 1 == numbers.end()) {
    done_iterating = true;
      } 
      if (*it % 2 == 0) {
    cout << "Erasing element: " << *it << "\n";
      numbers.erase(it++);
      }
      else {
    cout << "Skipping element: " << *it << "\n";
    ++it;
      }
    }
  }
}

C ++ 20 akan memiliki "penghapusan kontainer seragam", dan Anda akan dapat menulis:

std::erase_if(numbers, [](int n){ return n % 2 == 0 });

Dan yang akan bekerja untuk vector, set, deque, dll Lihat cppReference untuk info lebih lanjut.

Perilaku ini spesifik untuk implementasi. Untuk menjamin kebenaran iterator Anda harus menggunakan "it = numbers.erase (it);" pernyataan jika Anda perlu menghapus elemen dan hanya menambahkan iterator dalam kasus lain.

Saya pikir menggunakan metode STL ' remove_if' dari dapat membantu untuk mencegah beberapa masalah aneh ketika mencoba untuk mencoba menghapus objek yang dibungkus oleh iterator.

Solusi ini mungkin kurang efisien.

Katakanlah kita memiliki beberapa jenis wadah, seperti vektor atau daftar yang disebut m_bullets:

Bullet::Ptr is a shared_pr<Bullet>

' it' adalah iterator yang ' remove_if' kembali, argumen ketiga adalah fungsi lambda yang dieksekusi pada setiap elemen wadah. Karena wadah berisi Bullet::Ptr, fungsi lambda perlu mendapatkan tipe itu (atau referensi ke tipe itu) diteruskan sebagai argumen.

 auto it = std::remove_if(m_bullets.begin(), m_bullets.end(), [](Bullet::Ptr bullet){
    // dead bullets need to be removed from the container
    if (!bullet->isAlive()) {
        // lambda function returns true, thus this element is 'removed'
        return true;
    }
    else{
        // in the other case, that the bullet is still alive and we can do
        // stuff with it, like rendering and what not.
        bullet->render(); // while checking, we do render work at the same time
        // then we could either do another check or directly say that we don't
        // want the bullet to be removed.
        return false;
    }
});
// The interesting part is, that all of those objects were not really
// completely removed, as the space of the deleted objects does still 
// exist and needs to be removed if you do not want to manually fill it later 
// on with any other objects.
// erase dead bullets
m_bullets.erase(it, m_bullets.end());

' remove_if' menghapus wadah tempat fungsi lambda mengembalikan true dan menggeser konten itu ke awal wadah. The ' it' menunjuk ke objek yang tidak didefinisikan yang dapat dianggap sampah. Objek dari 'it' ke m_bullets.end () dapat dihapus, karena mereka menempati memori, tetapi mengandung sampah, sehingga metode 'erase' dipanggil pada rentang itu.

Saya menemukan masalah lama yang sama dan menemukan kode di bawah ini lebih dimengerti yang dengan cara per solusi di atas.

std::set<int*>::iterator beginIt = listOfInts.begin();
while(beginIt != listOfInts.end())
{
    // Use your member
    std::cout<<(*beginIt)<<std::endl;

    // delete the object
    delete (*beginIt);

    // erase item from vector
    listOfInts.erase(beginIt );

    // re-calculate the begin
    beginIt = listOfInts.begin();
}