Kontainer Pustaka Standar C++

Artikel
10/12/2023

Pustaka Standar menyediakan berbagai kontainer jenis aman untuk menyimpan koleksi objek terkait. Kontainer adalah templat kelas. Saat Anda mendeklarasikan variabel kontainer, Anda menentukan jenis elemen yang akan dipegang kontainer. Kontainer dapat dibangun dengan daftar penginisialisasi. Mereka memiliki fungsi anggota untuk menambahkan dan menghapus elemen dan melakukan operasi lain.

Anda melakukan iterasi atas elemen dalam kontainer, dan mengakses elemen individual dengan menggunakan iterator. Anda dapat menggunakan iterator secara eksplisit dengan menggunakan fungsi dan operator anggota dan fungsi global mereka. Anda juga dapat menggunakannya secara implisit, misalnya dengan menggunakan rentang untuk perulangan. Iterator untuk semua kontainer Pustaka Standar C++ memiliki antarmuka umum tetapi setiap kontainer menentukan iterator khususnya sendiri.

Kontainer dapat dibagi menjadi tiga kategori: kontainer urutan, kontainer asosiatif, dan adaptor kontainer.

Kontainer Urutan

Kontainer urutan mempertahankan urutan elemen yang disisipkan yang Anda tentukan.

Kontainer vector berulah seperti array, tetapi dapat secara otomatis tumbuh sesuai kebutuhan. Ini adalah akses acak dan disimpan secara berdada, dan panjangnya sangat fleksibel. Untuk alasan ini dan banyak lagi, vector adalah kontainer urutan yang disukai untuk sebagian besar aplikasi. Ketika ragu tentang jenis kontainer urutan apa yang akan digunakan, mulailah dengan menggunakan vektor! Untuk informasi selengkapnya, lihat vector Kelas.

Kontainer array memiliki beberapa kekuatan vector, tetapi panjangnya tidak fleksibel. Untuk informasi selengkapnya, lihat array Kelas.

Kontainer deque (antrean berujung ganda) memungkinkan penyisipan dan penghapusan cepat di awal dan akhir kontainer. Ini berbagi keuntungan akses acak dan panjang fleksibel dari vector, tetapi tidak bersebelahan. Untuk informasi selengkapnya, lihat deque Kelas.

Kontainer list adalah daftar dua arah yang ditautkan yang memungkinkan akses dua arah, penyisipan cepat, dan penghapusan cepat di mana saja dalam kontainer, tetapi Anda tidak dapat mengakses elemen secara acak dalam kontainer. Untuk informasi selengkapnya, lihat list Kelas.

Kontainer forward_list adalah daftar yang ditautkan dengan nyanyian—versi akses maju dari list. Untuk informasi selengkapnya, lihat forward_list Kelas.

Kontainer Asosiatif

Dalam kontainer asosiatif, elemen disisipkan dalam urutan yang telah ditentukan sebelumnya—misalnya, sebagai naik yang diurutkan. Kontainer asosiatif yang tidak diurutkan juga tersedia. Kontainer asosiatif dapat dikelompokkan ke dalam dua subset: peta dan set.

, mapterkadang disebut sebagai kamus, terdiri dari pasangan kunci/nilai. Kunci digunakan untuk mengurutkan urutan, dan nilainya dikaitkan dengan kunci tersebut. Misalnya, map mungkin berisi kunci yang mewakili setiap kata unik dalam teks dan nilai terkait yang mewakili berapa kali setiap kata muncul dalam teks. Versi yang tidak diurutkan map adalah unordered_map. Untuk informasi selengkapnya, lihat map Kelas dan unordered_map Kelas.

set hanyalah kontainer elemen unik yang naik—nilainya juga merupakan kuncinya. Versi yang tidak diurutkan set adalah unordered_set. Untuk informasi selengkapnya, lihat set Kelas dan unordered_set Kelas.

Baik map dan set hanya mengizinkan satu instans kunci atau elemen dimasukkan ke dalam kontainer. Jika beberapa instans elemen diperlukan, gunakan multimap atau multiset. Versi yang tidak diurutkan adalah unordered_multimap dan unordered_multiset. Untuk informasi selengkapnya, lihat multimap Kelas, unordered_multimap Kelas, multiset Kelas, dan unordered_multiset Kelas.

Peta dan set yang diurutkan mendukung iterator dua arah, dan mitranya yang tidak diurutkan mendukung iterator ke depan. Untuk informasi selengkapnya, lihat Iterator.

Pencarian Heterogen dalam Kontainer Asosiatif (C++14)

Kontainer asosiatif yang diurutkan (peta, multimap, set, dan multiset) sekarang mendukung pencarian heterogen, yang berarti Anda tidak lagi diharuskan untuk meneruskan jenis objek yang sama persis dengan kunci atau elemen dalam fungsi anggota seperti find() dan lower_bound(). Sebagai gantinya, Anda dapat meneruskan jenis apa pun yang didefinisikan operator< kelebihan beban yang memungkinkan perbandingan dengan jenis kunci.

Pencarian heterogen diaktifkan berdasarkan keikutsertaan saat Anda menentukan std::less<> komparator atau std::greater<> "diamond functor" saat mendeklarasikan variabel kontainer, seperti yang ditunjukkan di sini:

std::set<BigObject, std::less<>> myNewSet;

Jika Anda menggunakan komparator default, maka kontainer berperilaku persis seperti yang terjadi di C++11 dan yang lebih lama.

Contoh berikut menunjukkan cara kelebihan beban operator< untuk memungkinkan pengguna std::set melakukan pencarian hanya dengan meneruskan string kecil yang dapat dibandingkan dengan setiap anggota objek BigObject::id .

#include <set>
#include <string>
#include <iostream>
#include <functional>

using namespace std;

class BigObject
{
public:
    string id;
    explicit BigObject(const string& s) : id(s) {}
    bool operator< (const BigObject& other) const
    {
        return this->id < other.id;
    }

    // Other members....
};

inline bool operator<(const string& otherId, const BigObject& obj)
{
    return otherId < obj.id;
}

inline bool operator<(const BigObject& obj, const string& otherId)
{
    return obj.id < otherId;
}

int main()
{
    // Use C++14 brace-init syntax to invoke BigObject(string).
    // The s suffix invokes string ctor. It is a C++14 user-defined
    // literal defined in <string>
    BigObject b1{ "42F"s };
    BigObject b2{ "52F"s };
    BigObject b3{ "62F"s };
    set<BigObject, less<>> myNewSet; // C++14
    myNewSet.insert(b1);
    myNewSet.insert(b2);
    myNewSet.insert(b3);
    auto it = myNewSet.find(string("62F"));
    if (it != myNewSet.end())
        cout << "myNewSet element = " << it->id << endl;
    else
        cout << "element not found " << endl;

    // Keep console open in debug mode:
    cout << endl << "Press Enter to exit.";
    string s;
    getline(cin, s);
    return 0;
}

//Output: myNewSet element = 62F

Anggota berikut berfungsi dalam peta, multimap, set, dan multiset telah kelebihan beban untuk mendukung pencarian heterogen:

cari
jumlah
lower_bound
upper_bound
equal_range

Adapter Kontainer

Adaptor kontainer adalah variasi dari urutan atau kontainer asosiatif yang membatasi antarmuka untuk kesederhanaan dan kejelasan. Adaptor kontainer tidak mendukung iterator.

Kontainer queue mengikuti semantik FIFO (pertama masuk, pertama keluar). Elemen pertama yang didorong—yaitu, dimasukkan ke dalam antrean—adalah elemen pertama yang diisi—yaitu, dihapus dari antrean. Untuk informasi selengkapnya, lihat queue Kelas.

Kontainer priority_queue diatur skema sehingga elemen yang memiliki nilai tertinggi selalu terlebih dahulu dalam antrean. Untuk informasi selengkapnya, lihat priority_queue Kelas.

Kontainer stack mengikuti semantik LIFO (terakhir masuk, pertama keluar). Elemen terakhir yang didorong pada tumpukan adalah elemen pertama yang muncul. Untuk informasi selengkapnya, lihat stack Kelas.

Karena adaptor kontainer tidak mendukung iterator, adaptor kontainer tidak dapat digunakan dengan algoritma Pustaka Standar C++. Untuk informasi selengkapnya, lihat Algoritma.

Persyaratan untuk Elemen Kontainer

Secara umum, elemen yang dimasukkan ke dalam kontainer Pustaka Standar C++ dapat berupa hampir semua jenis objek jika dapat disalin. Elemen khusus movable—misalnya, elemen seperti vector<unique_ptr<T>> yang dibuat dengan menggunakan unique_ptr<> akan berfungsi selama Anda tidak memanggil fungsi anggota yang mencoba menyalinnya.

Destruktor tidak diizinkan untuk melemparkan pengecualian.

Kontainer asosiatif yang diurutkan—dijelaskan sebelumnya dalam artikel ini—harus memiliki operator perbandingan publik yang ditentukan. Secara default, operator adalah operator<, tetapi bahkan jenis yang tidak berfungsi didukung operator< .

Beberapa operasi pada kontainer mungkin juga memerlukan konstruktor default publik dan operator kesetaraan publik. Misalnya, kontainer asosiatif yang tidak diurutkan memerlukan dukungan untuk kesetaraan dan hashing.

Mengakses Elemen Kontainer

Elemen kontainer diakses dengan menggunakan iterator. Untuk informasi selengkapnya, lihat Iterator.

Catatan

Anda juga dapat menggunakan berbasis rentang untuk perulangan untuk melakukan iterasi melalui koleksi Pustaka Standar C++.

Membandingkan kontainer

Semua kontainer kelebihan beban operator== untuk membandingkan dua kontainer dengan jenis yang sama yang memiliki jenis elemen yang sama. Anda dapat menggunakan == untuk membandingkan string vektor<dengan string> vektor<lain, tetapi Anda tidak dapat menggunakannya untuk membandingkan string> vektor<dengan string> daftar<atau string> vektor<dengan karakter vektor<*>.> Di C++98/03, Anda dapat menggunakan std::equal atau std::mismatch untuk membandingkan jenis kontainer dan/atau jenis elemen yang berbeda. Di C++11, Anda juga dapat menggunakan std::is_permutation. Tetapi dalam semua kasus ini fungsi mengasumsikan kontainer memiliki panjang yang sama. Jika rentang kedua lebih pendek dari yang pertama, maka hasil perilaku yang tidak ditentukan. Jika rentang kedua lebih panjang, hasilnya masih bisa salah karena perbandingan tidak pernah berlanjut melewati akhir rentang pertama.

Membandingkan kontainer yang berbeda (C++14)

Di C++14 dan yang lebih baru, Anda dapat membandingkan jenis kontainer dan/atau elemen yang berbeda berbeda dengan menggunakan salah std::equalsatu kelebihan fungsi , std::mismatch, atau std::is_permutation yang membutuhkan dua rentang lengkap. Kelebihan beban ini memungkinkan Anda membandingkan kontainer dengan panjang yang berbeda. Kelebihan beban ini jauh lebih rentan terhadap kesalahan pengguna, dan dioptimalkan untuk mengembalikan false dalam waktu konstan ketika kontainer panjang yang berbeda dibandingkan. Oleh karena itu, kami sarankan Anda menggunakan kelebihan beban ini kecuali Anda memiliki alasan yang jelas untuk tidak, atau Anda menggunakan std::list kontainer, yang tidak mendapat manfaat dari pengoptimalan rentang ganda.

Bagikan melalui