remove_if setara dengan std :: map

Saya mencoba menghapus berbagai elemen dari peta berdasarkan kondisi tertentu. Bagaimana cara melakukannya menggunakan algoritma STL?

Awalnya saya berpikir untuk menggunakan remove_iftetapi tidak mungkin karena remove_if tidak berfungsi untuk wadah asosiatif.

Apakah ada algoritme setara "remove_if" yang berfungsi untuk peta?

Sebagai opsi sederhana, saya berpikir untuk mengulang melalui peta dan menghapus. Tetapi apakah perulangan melalui peta dan menghapus opsi yang aman? (Karena iterator menjadi tidak valid setelah dihapus)

Saya menggunakan contoh berikut:

bool predicate(const std::pair<int,std::string>& x)
{
    return x.first > 2;
}

int main(void) 
{

    std::map<int, std::string> aMap;

    aMap[2] = "two";
    aMap[3] = "three";
    aMap[4] = "four";
    aMap[5] = "five";
    aMap[6] = "six";

//      does not work, an error
//  std::remove_if(aMap.begin(), aMap.end(), predicate);

    std::map<int, std::string>::iterator iter = aMap.begin();
    std::map<int, std::string>::iterator endIter = aMap.end();

    for(; iter != endIter; ++iter)
    {
            if(Some Condition)
            {
                            // is it safe ?
                aMap.erase(iter++);
            }
    }

    return 0;
}

Hampir.

for(; iter != endIter; ) {
     if (Some Condition) {
          iter = aMap.erase(iter);
     } else {
          ++iter;
     }
}

Apa yang Anda semula akan menambah iterator dua kali jika Anda benar-benar menghapus elemen darinya; Anda berpotensi melewatkan elemen yang perlu dihapus.

Ini adalah algoritma umum yang pernah saya lihat digunakan dan didokumentasikan di banyak tempat.

[EDIT] Anda benar bahwa iterator tidak valid setelah penghapusan, tetapi hanya iterator yang mereferensikan elemen yang dihapus, iterator lain masih valid. Karenanya menggunakan iter++dalam erase()panggilan.

erase_if untuk std :: map (dan penampung lainnya)

Saya menggunakan template berikut untuk hal ini.

namespace stuff {
  template< typename ContainerT, typename PredicateT >
  void erase_if( ContainerT& items, const PredicateT& predicate ) {
    for( auto it = items.begin(); it != items.end(); ) {
      if( predicate(*it) ) it = items.erase(it);
      else ++it;
    }
  }
}

Ini tidak akan mengembalikan apa pun, tetapi akan menghapus item dari std :: map.

Contoh penggunaan:

// 'container' could be a std::map
// 'item_type' is what you might store in your container
using stuff::erase_if;
erase_if(container, []( item_type& item ) {
  return /* insert appropriate test */;
});

Contoh kedua (memungkinkan Anda untuk meneruskan nilai tes):

// 'test_value' is value that you might inject into your predicate.
// 'property' is just used to provide a stand-in test
using stuff::erase_if;
int test_value = 4;  // or use whatever appropriate type and value
erase_if(container, [&test_value]( item_type& item ) {
  return item.property < test_value;  // or whatever appropriate test
});

Sekarang, std::experimental::erase_iftersedia di header<experimental/map> .

Lihat: http://en.cppreference.com/w/cpp/experimental/map/erase_if

Dokumentasi ini saya dapatkan dari referensi SGI STL yang sangat baik :

Peta memiliki properti penting sehingga memasukkan elemen baru ke dalam peta tidak membatalkan iterator yang mengarah ke elemen yang ada. Menghapus elemen dari peta juga tidak membatalkan iterator apa pun, kecuali, tentu saja, untuk iterator yang benar-benar mengarah ke elemen yang sedang dihapus.

Jadi, iterator yang Anda miliki yang mengarah ke elemen yang akan dihapus tentu saja tidak valid. Lakukan sesuatu seperti ini:

if (some condition)
{
  iterator here=iter++;
  aMap.erase(here)
}

Kode asli hanya memiliki satu masalah:

for(; iter != endIter; ++iter)
{
    if(Some Condition)
    {
        // is it safe ?
        aMap.erase(iter++);
    }
}

Di sini, iterbertambah sekali dalam perulangan for dan waktu lain dalam penghapusan, yang mungkin akan berakhir dalam beberapa perulangan tak terbatas.

Inilah beberapa solusi elegan.

for (auto it = map.begin(); it != map.end();)
{   
    (SomeCondition) ? map.erase(it++) : (++it);
}

Dari catatan bawah:

http://www.sgi.com/tech/stl/PairAssociativeContainer.html

Pair Associative Container tidak dapat menyediakan iterator yang dapat diubah (seperti yang didefinisikan dalam persyaratan Trivial Iterator), karena tipe nilai dari iterator yang dapat berubah harus dapat ditetapkan, dan pasangan tidak dapat ditetapkan. Namun, Pair Associative Container dapat menyediakan iterator yang tidak sepenuhnya konstan: iterator sedemikian rupa sehingga ekspresi (* i) .second = d valid.

Pertama

Peta memiliki properti penting sehingga memasukkan elemen baru ke dalam peta tidak membatalkan iterator yang mengarah ke elemen yang ada. Menghapus elemen dari peta juga tidak membatalkan iterator apa pun, kecuali, tentu saja, untuk iterator yang benar-benar mengarah ke elemen yang sedang dihapus.

Kedua, kode berikut ini bagus

for(; iter != endIter; )
{
    if(Some Condition)
    {
        aMap.erase(iter++);
    }
    else
    {
        ++iter;
    }
}

Saat memanggil suatu fungsi, parameter dievaluasi sebelum panggilan ke fungsi itu.

Jadi, ketika iter ++ dievaluasi sebelum panggilan untuk dihapus, operator ++ dari iterator akan mengembalikan item saat ini dan akan menunjuk ke item berikutnya setelah panggilan.

IMHO tidak ada yang remove_if()setara.
Anda tidak dapat menyusun ulang peta.
Jadi remove_if()tidak bisa menempatkan pasangan Anda di akhir yang dapat Anda panggil erase().

Berdasarkan jawaban Iron Savior Bagi mereka yang ingin memberikan lebih banyak rentang di sepanjang garis iterator pengambilan fungsional std.

template< typename ContainerT, class FwdIt, class Pr >
void erase_if(ContainerT& items, FwdIt it, FwdIt Last, Pr Pred) {
    for (; it != Last; ) {
        if (Pred(*it)) it = items.erase(it);
        else ++it;
    }
}

Penasaran apakah ada cara untuk kehilangan ContainerTitem dan mendapatkannya dari iterator.

Jawaban Steve Folly saya rasa lebih efisien.

Berikut adalah solusi lain yang mudah tetapi kurang efisien :

Solusi yang digunakan remove_copy_ifuntuk menyalin nilai yang kita inginkan ke dalam wadah baru, lalu menukar isi wadah asli dengan yang baru:

std::map<int, std::string> aMap;

...
//Temporary map to hold the unremoved elements
std::map<int, std::string> aTempMap;

//copy unremoved values from aMap to aTempMap
std::remove_copy_if(aMap.begin(), aMap.end(), 
                    inserter(aTempMap, aTempMap.end()),
                    predicate);

//Swap the contents of aMap and aTempMap
aMap.swap(aTempMap);

Jika Anda ingin menghapus semua elemen dengan kunci lebih besar dari 2, maka cara terbaik adalah

map.erase(map.upper_bound(2), map.end());

Hanya berfungsi untuk rentang, bukan untuk predikat apa pun.

Saya menggunakan seperti ini

 std::map<int, std::string> users;    
 for(auto it = users.begin(); it <= users.end()) {
    if(<condition>){
      it = users.erase(it);
    } else {
    ++it;
    }
 }