Modul 1 [Standard Template Library] - lab-kcks/Modul-STRUKDAT GitHub Wiki

Standard Template Library Container

Container adalah sebuah obyek yang digunakan untuk menyimpan sekumpulan obyek lain (disebut sebagai elemen pada container tersebut). Container ini dimplementasikan dengan template class sehingga sudah tersedia fungsi-fungsi yang nantinya bisa digunakan untuk mengakses elemen-elemennya.

`std::array`

Masih ingat dengan Array?

std::array merupakan salah satu jenis struktur data yang dapat menyimpan data secara sekuensial dengan ukuran atau kapasitas yang tetap (fixed-size).

Berikut ini adalah operasi-operasi dari yang ada pada std::array:

operator[] - Mengakses elemen pada posisi tertentu yang spesifik.
at() - Mengakses elemen pada posisi tertentu yang spesifik sekaligus mengecek batas ukuran array. Perbedaan at() dengan operator[] ada ketika indeks elemen yang akan diakses melebihi batas ukuran array, pada at() program akan mengeluarkan error out_of_range sedangkan pada operator[] program akan mengeluarkan undefined behaviour.
front() - Mengakses elemen yang ada di posisi pertama.
back() - Mengakses elemen yang ada di posisi terakhir.
begin() - Iterator yang menunjuk awal sekuens dari array.
end() - Iterator yang menunjuk elemen setelah akhir sekuens array.
size() - Mendapatkan jumlah elemen yang ada pada array.
max_size() - Mendapatkan jumlah maksimal elemen yang dapat ditampung oleh array.
empty() - Memeriksa apakah array sedang kosong atau tidak. Jika ukuran array adalah 0, maka program akan mengembalikan nilai true, tetapi sebaliknya program akan mengembalikan false.
swap() - Menukar seluruh elemen pada sebuah array dengan seluruh elemen pada array lain yang memiliki tipe data dan ukuran yang sama.
fill() - Mengisi seluruh elemen pada array dengan nilai tertentu.

Contoh implementasi STL Array dapat dilihat di link berikut.

`std::vector`

Masih ingat dengan Dynamic Array?

std::vector adalah salah satu jenis struktur data yang merepresentasikan array dengan ukuran (kapasitas) yang dinamis sesuai dengan banyaknya data yang dimasukkan.

Operasi-operasi yang ada di std::vector:

operator[] - Mengakses elemen di posisi tertentu yang spesifik.
at() - Mengakses elemen di posisi tertentu yang spesifik sekaligus mengecek batas ukuran vector. Perbedaan at() dengan operator[] ada ketika indeks elemen yang akan diakses melebihi batas ukuran array, pada at() program akan mengeluarkan error out_of_range sedangkan pada operator[] program akan mengeluarkan undefined behaviour.
front() - Mengakses elemen yang ada di posisi pertama.
back() - Mengakses elemen yang ada di posisi terakhir.
begin() - Iterator yang menunjuk awal sekuens dari vector.
end() - Iterator yang menunjuk elemen setelah akhir sekuens vector.
size() - Mendapatkan jumlah elemen yang ada pada vector.
max_size() - Mendapatkan jumlah maksimal elemen yang dapat ditampung oleh vector.
resize() - Mengubah ukuran vector menjadi jumlah elemen tertentu. resize() juga dapat disertai dengan menetapkan nilai tertentu, namun tidak akan mengubah elemen yang sudah ada nilainya sebelumnya (berbeda dengan assign()).
assign() - Menetapkan ukuran vector menjadi jumlah elemen tertentu dengan nilai tertentu pada seluruh elemennya.
empty() - Memeriksa apakah vector sedang kosong atau tidak. Jika ukuran vector adalah 0, maka program akan mengembalikan nilai true, tetapi sebaliknya program akan mengembalikan false.
push_back() - Menambahkan elemen di posisi terakhir vector.
pop_back() - Menghapus elemen yang ada di posisi terakhir.
insert() - Memasukan nilai di posisi (atau range) tertentu.
erase() - Menghapus nilai di posisi (atau range) tertentu.
clear() - Menghapus seluruh elemen sehingga ukuran vector menjadi 0.
swap() - Menukar seluruh elemen pada sebuah vector dengan seluruh elemen pada vector lain yang memiliki tipe data (ukuran dapat berbeda).
sort(first, last) - Mengurutkan elemen pada vector secara ascending pada rentang [first, last].
lower_bound(first, last, val) - Mengembalikan iterator yang menunjuk pada elemen terkecil yang tidak kurang dari val pada rentang [first, last]. Jika tidak ada, maka akan mengembalikan iterator last.
upper_bound(first, last, val) - Mengembalikan iterator yang menunjuk pada elemen terkecil yang lebih dari val pada rentang [first, last]. Jika tidak ada, maka akan mengembalikan iterator last.

Contoh implementasi STL Vector dapat dilihat di link berikut.

`std::list`

Masih ingat dengan Linked List?

std::list adalah salah satu jenis struktur data yang menampung elemen secara sekuensial dan mampu melakukan operasi insert() dan erase() secara constant time.

Operasi-operasi yang ada di std::list:

front() - Mengakses elemen yang ada di posisi pertama.
back() - Mengakses elemen yang ada di posisi terakhir.
begin() - Iterator yang menunjuk awal sekuens dari list.
end() - Iterator yang menunjuk elemen setelah akhir sekuens list.
size() - Mendapatkan jumlah elemen yang ada pada list.
max_size() - Mendapatkan jumlah maksimal elemen yang dapat ditampung oleh list.
resize() - Mengubah ukuran list menjadi jumlah elemen tertentu. resize() juga dapat disertai dengan menetapkan nilai tertentu, namun tidak akan mengubah elemen yang sudah ada nilainya sebelumnya (berbeda dengan assign()).
assign() - Menetapkan ukuran list menjadi jumlah elemen tertentu dengan nilai tertentu pada seluruh elemennya.
empty() - Memeriksa apakah list sedang kosong atau tidak. Jika ukuran list adalah 0, maka program akan mengembalikan nilai true, tetapi sebaliknya program akan mengembalikan false.
push_front() - Menambahkan elemen di posisi pertama list.
pop_front() - Menghapus elemen yang ada di posisi pertama list.
push_back() - Menambahkan elemen di posisi terakhir list.
pop_back() - Menghapus elemen yang ada di posisi terakhir list.
insert() - Memasukan nilai di posisi (atau range) tertentu.
erase() - Menghapus nilai di posisi (atau range) tertentu.
clear() - Menghapus seluruh elemen sehingga ukuran list menjadi 0.
swap() - Menukar seluruh elemen pada sebuah list dengan seluruh elemen pada vector lain yang memiliki tipe data (ukuran dapat berbeda).
sort() - Mengurutkan elemen pada list secara ascending.
reverse() - Membalikkan urutan posisi elemen.
merge() - Memindahkan seluruh elemen pada sebuah list ke list lain dengan syarat kedua list sudah terurut sehingga seluruh elemen pada list tujuan pun terurut.
splice() - Memindahkan seluruh elemen atau elemen tertentu pada sebuah posisi spesifik di list tersebut atau list lain.
unique() - Menghapus elemen duplikat pada sebuah list dan menyisakan sebuah list yang berisikan elemen-elemen unik.
remove() - Menghapus elemen dengan nilai tertentu. Berbeda dengan erase() yang menghapus berdasarkan posisi elemen, remove() menghapus elemen berdasarkan nilainya.
remove_if() - Menghapus elemen dengan nilai tertentu yang memenuhi syarat tertentu.

Contoh implementasi STL List dapat dilihat di link berikut.

`std::stack`

Masih ingat dengan Stack?

std::stack adalah salah satu jenis struktur data dinamis yang mengikuti prinsip LIFO (Last In First Out).

Operasi-operasi yang ada di std::stack:

top() - Mengakses elemen yang ada di posisi pertama.
size() - Mendapatkan jumlah elemen pada stack.
empty() - Memeriksa apakah stack kosong atau tidak. Jika ukuran stack adalah 0, mengembalikan nilai true tetapi sebaliknya program akan mengembalikan false.
push() - Menambahkan elemen di posisi pertama.
pop() - Menghapus elemen di posisi pertama.
swap() - Menukar seluruh elemen pada sebuah stack dengan seluruh elemen pada stack lain yang memiliki tipe data yang sama (ukuran dapat berbeda).

Contoh implementasi STL Stack dapat dilihat di link berikut.

`std::queue`

Masih ingat dengan Queue?

std::queue adalah salah satu jenis struktur data dinamis yang mengikuti prinsip FIFO (First In First Out).

Operasi-operasi yang ada di std::queue:

front() - Mengakses elemen yang ada di posisi pertama.
back() - Mengakses elemen yang ada di posisi terakhir.
size() - Mendapatkan jumlah elemen pada queue.
empty() - Memeriksa apakah queue kosong atau tidak. Jika ukuran queue adalah 0, mengembalikan nilai true tetapi sebaliknya program akan mengembalikan false.
push() - Menambahkan elemen di posisi pertama.
pop() - Menghapus elemen di posisi terakhir.
swap() - Menukar seluruh elemen pada sebuah stack dengan seluruh elemen pada stack lain yang memiliki tipe data yang sama (ukuran dapat berbeda).

Contoh implementasi STL Queue dapat dilihat di link berikut.

`std::deque`

Masih ingat dengan Deque?

std::deque adalah salah satu jenis struktur data dinamis yang dapat menambahkan atau mengurangi data baik di posisi awal maupun di posisi akhir.

Operasi-operasi yang ada di std::deque:

operator[] - Mengakses elemen pada posisi tertentu yang spesifik.
at() - Mengakses elemen pada posisi tertentu yang spesifik sekaligus mengecek batas ukuran deque. Perbedaan at() dengan operator[] ada ketika indeks elemen yang akan diakses melebihi batas ukuran deque, pada at() program akan mengeluarkan error out_of_range sedangkan pada operator[] program akan mengeluarkan undefined behaviour.
front() - Mengakses elemen yang ada di posisi pertama.
back() - Mengakses elemen yang ada di posisi terakhir.
begin() - Iterator yang menunjuk awal sekuens dari deque.
end() - Iterator yang menunjuk elemen setelah akhir sekuens deque.
size() - Mendapatkan jumlah elemen yang ada pada deque.
max_size() - Mendapatkan jumlah maksimal elemen yang dapat ditampung oleh deque.
resize() - Mengubah ukuran deque menjadi jumlah elemen tertentu. resize() juga dapat disertai dengan menetapkan nilai tertentu, namun tidak akan mengubah elemen yang sudah ada nilainya sebelumnya (berbeda dengan assign()).
assign() - Menetapkan ukuran deque menjadi jumlah elemen tertentu dengan nilai tertentu pada seluruh elemennya.
empty() - Memeriksa apakah deque sedang kosong atau tidak. Jika ukuran list adalah 0, maka program akan mengembalikan nilai true, tetapi sebaliknya program akan mengembalikan false.
push_front() - Menambahkan elemen di posisi pertama deque.
pop_front() - Menghapus elemen yang ada di posisi pertama deque.
push_back() - Menambahkan elemen di posisi terakhir deque.
pop_back() - Menghapus elemen yang ada di posisi terakhir deque.
insert() - Memasukan nilai di posisi (atau range) tertentu.
erase() - Menghapus nilai di posisi (atau range) tertentu.
clear() - Menghapus seluruh elemen sehingga ukuran list menjadi 0.
swap() - Menukar seluruh elemen pada sebuah list dengan seluruh elemen pada vector lain yang memiliki tipe data (ukuran dapat berbeda).

Contoh implementasi STL Deque dapat dilihat di link berikut.

`std::priority_queue`

Masih ingat dengan Priority Queue?

std::priority_queue adalah salah satu jenis struktur data dinamis yang dapat dengan otomatis menampung elemen dengan susunan terurut secara descending.

Operasi-operasi yang ada di std::priority_queue:

top() - Mengakses elemen yang ada di posisi pertama.
size() - Mendapatkan jumlah elemen pada priority queue.
empty() - Memeriksa apakah priority queue kosong atau tidak. Jika ukuran priority queue adalah 0, mengembalikan nilai true tetapi sebaliknya program akan mengembalikan false.
push() - Menambahkan elemen di posisi pertama.
pop() - Menghapus elemen di posisi pertama.
swap() - Menukar seluruh elemen pada sebuah priority queue dengan seluruh elemen pada priority queue lain yang memiliki tipe data yang sama (ukuran dapat berbeda).

Contoh implementasi STL Priority Queue dapat dilihat di link berikut.

`std::map`

std::map adalah sebuah associative container yang menampung elemen dalam bentuk key-value.

Operasi-operasi yang ada di std::map:

operator[] - Mengakses value dari suatu key tertentu.
begin() - Iterator yang menunjuk awal sekuens dari map.
end() - Iterator yang menunjuk elemen setelah akhir sekuens map.
size() - Mendapatkan jumlah elemen pada map.
max_size() - Mendapakan jumlah maksimal elemen yang dapat ditampung oleh map.
empty() - Memeriksa apakah map kosong atau tidak. Jika ukuran map adalah 0, mengembalikan nilai true tetapi sebaliknya program akan mengembalikan false.
insert() - Memasukkan nilai di posisi (atau range) tertentu.
erase() - Menghapus nilai di posisi (atau range) tertentu.
clear() - Menghapus seluruh elemen sehingga ukuran map menjadi 0.
swap() - Menukar seluruh elemen pada sebuah map dengan seluruh elemen pada map lain yang memiliki tipe data yang sama (ukuran dapat berbeda).
find() - Menemukan elemen berdasarkan key.
count() - Mencari jumlah elemen dengan nilai yang sama.

Contoh implementasi STL Map dapat dilihat di link berikut.

`std::set`

std::set adalah sebuah associative container yang menampung elemen dalam bentuk key-value dimana value-nya merupakan key-nya sehingga setiap elemen merupakan elemen yang unik.

Operasi-operasi yang ada di std::set:

begin() - Iterator yang menunjuk awal sekuens dari set.
end() - Iterator yang menunjuk elemen setelah akhir sekuens set.
size() - Mendapatkan jumlah elemen pada set.
max_size() - Mendapakan jumlah maksimal elemen yang dapat ditampung oleh set.
empty() - Memeriksa apakah set kosong atau tidak. Jika ukuran set adalah 0, mengembalikan nilai true tetapi sebaliknya program akan mengembalikan false.
insert() - Memasukkan nilai di posisi (atau range) tertentu.
erase() - Menghapus nilai di posisi (atau range) tertentu.
clear() - Menghapus seluruh elemen sehingga ukuran map menjadi 0.
swap() - Menukar seluruh elemen pada sebuah set dengan seluruh elemen pada set lain yang memiliki tipe data yang sama (ukuran dapat berbeda).
find() - Menemukan elemen berdasarkan key.
count() - Mencari jumlah elemen dengan nilai yang sama. Karena setiap elemen di set merupakan elemen yang unik, maka jika elemen ditemukan akan mengembalikan nilai 1 sedangkan jika tidak, maka program akan mengembalikan nilai 0.
lower_bound(val) - mengembalikan iterator yang menunjuk ke key yang memiliki nilai terkecil yang tidak lebih kecil dari va;. Jika tidak ada, maka akan mengembalikan iterator end().
upper_bound(val) - mengembalikan iterator yang menunjuk ke key yang memiliki nilai terkecil yang lebih besar dari val. Jika tidak ada, maka akan mengembalikan iterator end().

Contoh implementasi STL Set dapat dilihat di link berikut.

`PBDS`

Kurang lebih, struktur data ini berfungsi sama seperti std::set tetapi, memiliki tambahan fungsi lain, yaitu:

find_by_order(k) - Mengembalikan bilangan pada urutan ke - K jika diurutkan secara ascending.
order_of_key(val) - Mengembalikan banyaknya bilangan yang memiliki nilai lebih kecil dari.

Implementasi map, set, priority_queue, dan PBDS menggunakan struktur data balanced binary search tree atau heap yang menyebabkan pengaksesan elemen pada STL tersebut membutuhkan waktu yang logaritmik terhadap jumlah elemennya O(lgN). Sedangkan STL lain yang dijelaskan di modul ini membutuhkan waktu konstan untuk mengakses elemen-elemennya O(1).

Contoh implementasi STL PBDS dapat dilihat di link berikut.

Untuk informasi lebih detail mengenai STL dapat dibaca di : cplusplus.com Khusus untuk PBDS dapat dilihat di : https://codeforces.com/blog/entry/11080.