Daftar C ++ dengan pencarian cepat

Question

Saya bekerja dengan a std::list.

Elemen muncul dalam "urutan penyisipan" ke dalam daftar, bukan sesuai dengan nilai elemen.

Ketika std::find()-ing sebuah elemen, seluruh daftar harus dicari.

Untuk mempercepat "menemukan" dari O (n) ke O (log (n)) Saya sendiri dapat menerapkan peta hash untuk menyimpan std::listposisi elemen, atau saya dapat menggunakan boost Multi Indexes,https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookup.

Pertanyaan: Hari ini, dengan C ++ 17, apakah ada cara standar / umum atau praktik terbaik untuk mengimplementasikan wadah yang memiliki semua properti dari daftar PLUS cepat find(dan, misalnya remove)? Atau, apakah jenis wadah seperti itu sudah ada? C ++ 20 mungkin?

Edit / Nb: Urutan elemen dalam daftar relevan dan dengan demikian std :: map tidak bisa langsung digunakan.

Answer 1

Karena iterator untuk std::listtetap valid di seluruh penyisipan dan penghapusan (kecuali untuk elemen yang Anda hapus, tentu saja), Anda dapat mempertahankan tipe struktur data baris kedua std::map <my_key, my_list_iterator>(atau std::unordered_mapjika itu lebih cocok).

Kemudian, setiap kali Anda menambah atau menghapus entri daftar, lakukan hal yang sama ke Anda std::map / unordered_mapdan selesai. Anda dapat, tentu saja, mencarinya dengan kompleksitas O (log (n)) (atau O (1)).

Answer 2

Panduan yang sangat singkat dan mudah dipahami (berdasarkan satu contoh) tentang cara mengimplementasikan container dengan kapabilitas yang diinginkan menggunakan Boost MultiIndex https://stackoverflow.com/a/39510606/11608725

Bagi saya, ini lebih bersifat langsung, lebih mudah dipahami, daripada gaya yang lebih formal https://www.boost.org/doc/libs/release/libs/multi_index/doc/tutorial/basics.html#list_fast_lookupyang mencakup setiap kemungkinan penggunaan (meskipun itu juga menggunakan contoh).

Answer 3

Implementasi sebagian dan SANGAT primitif (prototipe) dari jawaban ini https://stackoverflow.com/a/64539693/11608725 (oleh Paul Sanders):

 #include <unordered_map>
 #include <list>
 #include <iterator>
 #include <iostream>

 using std::unordered_map;
 using std::list;
 using std::make_pair;
 using std::begin;
 using std::end;
 using std::prev;
 using std::cout;

 template <typename T>
 struct fastlist {
    list<T> l;
    unordered_map<T, typename list<T>::iterator> m;
     
    void push_front(T e) {
        l.push_front(e);
        m.insert(make_pair(e, begin(l)));
    }

    void push_back(T e) {
        l.push_back(e);
        m.insert(make_pair(e, prev(end(l))));
    }

    auto find(T e) {
        return m[e];
    }

    void remove(T e) {
        auto it = m[e];
        m.erase(*it);
        l.erase(it);
    }
};

int main() {          // Giving it a spin
    fastlist<int> f;

    f.push_back(3);
    f.push_back(4);
    f.push_back(5);
    f.push_front(2);
    f.push_front(1);
    f.remove(3);
    f.remove(5);
    f.remove(1); 
    f.push_back(200); 
    f.push_front(-100);
    cout << *f.find(4);
}

demo: https://godbolt.org/z/jdnvdM

Di antara banyak hal lainnya, prototipe ini kehilangan metode iterator untuk mengimplementasikan container kustom, info tentang ini di sini: Bagaimana cara mengimplementasikan iterator gaya STL dan menghindari kesalahan umum? .

(Sunting: Ted Lyngmo dalam komentarnya di bawah ini memberikan versi yang lebih baik di sini: https://godbolt.org/z/6xfbq7).

Akan sangat rapi jika wadah semacam ini disediakan di luar kotak. Serta penampung lain yang dimodelkan / diturunkan dari penampung yang lebih mendasar, tetapi menambahkan keunggulan kinerja tertentu yang mencerminkan situasi penggunaan tertentu. Jika ada yang mengetahui perpustakaan yang menyediakan wadah khusus semacam itu, beri tahu ;-)