Standard Template LibrarySTL

STLSTL => Standard Template Library

Adalah merupakan kumpulan library yang melengkapi library standard C++.

Berisi kumpulan class-class yang umum digunakan, seperti container, algorithm, dan iterator.

Menyediakan algoritma dan struktur data dasar untuk permasalahan komputasi.

STLSTL (meliputi)Container

Sequence Container : vector, deque, listAssociative containers : set, multiset, multimap,

mapContainer adapters :stack, queue, priority queue

Algorithm : equal, mismatch, lexicographical_compare, remove, remove_if, replace, replace_if, random_shuffle, count, count_if, min_element, max_element, accumulate, for_each , dll

Iterator

ContainerAdalah sebuah class, data structure, atau

sebuah ADT (abstract Data Type) yang akan menjadi instance dari koleksi object lain.

Digunakan untuk menyimpan object-object dalam bentuk yang terorganisasi diikuti dengan aturan akses tertentu.

ContainerSebuah struktur data dapat

dipandang sebagai tempat penyimpanan benda (container).

Beberapa hal yang dapat dilakukan:Membuat container

baru(konstruktor)Menaruh bendaMengambil bendaMencari benda tertentuMengosongkannya (atau

periksa apakah kosong)Mendapatkan jumlah benda

dalam container (size)

Container

Data

ContainerTerdiri dari 3 macamSequence containers => Container yang

tersusun berdere-deret.Associative containers => merupakan

container yang key-nya diasosiasikan dengan suatu value.

Container adapters => merupakan containers dengan interface spesifik, memanfaatkan containers lain untuk implementasinya.

Sequence containersvector

rapid insertions and deletions at back direct access to any element

dequerapid insertions and deletions at front or back direct access to any element

listdoubly linked list, rapid insertion and deletion anywhere

Associative containersset

rapid lookup, no duplicates allowedmultiset

rapid lookup, duplicates allowedmap

one-to-one mapping, no duplicates allowed, rapid key-based lookup

multimapone-to-many mapping, duplicates allowed, rapid key-based lookup

Container adaptersstack

last-in, first-out (LIFO)queue

first-in, first-out (FIFO)priority_queue

highest-priority element is always the first element out

Container: List

Sebuah List adalah kumpulan benda di mana setiap benda memiliki posisi.

Setiap benda dalam List dapat diakses melalui indeks-nya.

Contoh paling gampang: array!

1 2 3 4Indeks

Container: Vector

Sebuah Vector adalah kumpulan benda di mana setiap benda memiliki posisi dan size-nya dinamis.

Setiap benda dalam List dapat diakses melalui indeks-nya.

Contoh paling gampang: dynamic array!

1 2 3 4Indeks

Vector - Overview of functionsinformative

vector::front - Returns reference to first element of vector.

vector::back - Returns reference to last element of vector.

vector::size - Returns number of elements in the vector.

vector::empty - Returns true if vector has no elements.

vector::capacity - Returns current capacity (allocated memory) of vector.

Vector - Overview of functionsstandard operations

vector::insert - Inserts elements into a vector (single & range), shifts later elements up. O(n) time.

vector::push_back - Appends (inserts) an element to the end of a vector, allocating memory for it if necessary. Amortized O(1) time.

vector::erase - Deletes elements from a vector (single & range), shifts later elements down. O(n) time.

vector::pop_back - Erases the last element of the vector, O(1) time. Does not usually reduce the memory overhead of the vector. Amortized O(1) time.

vector::clear - Erases all of the elements. (For most STL implementations this is O(n) time and does not reduce capacity)

Vector - Overview of functionsallocation/size modification

vector::reserve - Changes capacity (allocates more memory) of the vector, if needed. In many STL implementations capacity can only grow, and is never reduced. O(n) if the vector expands. O(1) if not.

vector::resize - Changes the vector size. O(n) time.

Vector - Overview of functionsiteration

vector::begin - Returns an iterator to start traversal of the vector.

vector::end - Returns an iterator that points just beyond the end of the vector.

Container : StackSebuah Stack adalah kumpulan

benda di mana hanya benda yang most recently inserted dapat diakses.

Bayangkan setumpuk koran.Benda yang paling terakhir

ditambahkan ditaruh di atas tumpukan (top).

Operasi pada Stack membutuhkan waktu konstan (O(1)).

Least recent

Most recent

push

pop,top

Container : Queue

Sebuah Queue adalah kumpulan benda di mana hanya benda yang least recently inserted dapat diakses.

Bayangkan antrian printer job pada jaringan.Benda yang paling awal ditambahkan berada di depan

antrian (front).Operasi pada Queue membutuhkan waktu konstan (O(1)).

enqueue

Most recent

Least recent

dequeuegetFront

Container : Set

Set adalah struktur data yang tidak mengizinkan duplikasi data.

Bandingkan dengan struktur data lain yang mengizinkan kita menyimpan dua data yang sama.

Bayangkan peserta kuliah ini: Setiap peserta unik, tidak ada yang terdaftar dua kali!

tambah

Container : Map

Map adalah struktur data yang berisi sekumpulan pasangan nama (keys) dan nilai (values) dari nama tersebut.

Nama (Keys) harus unik, tapi nilai (values) tidak. Bayangkan basis-data yang berisi informasi peserta kuliah.

Apa yang menjadi “nama” (keys)?

Abdul Betty Chairul DianNama:

Nilai:

Map – member functions

Container : Priority Queue

Priority Queue adalah struktur data queue yang tiap elemen data dapat miliki nilai prioritas. Data dengan nilai prioritas tertinggilah yang dapat diakses terlebih dulu.

Bayangkan sebuah antrian pada printer jaringan. Misalkan ada sebuah permintaan cetak untuk 100 halaman hanya beberapa detik lebih awal dari permintaan cetak selembar halaman.

Highest priority

insert deleteMin

findMin

STL : AlgorithmSebuah method yang efektif untuk problem

solving yang dinyatakan/diungkapkan dalam rangkaian/rentetan instruksi yang terbatas.

Digunakan untuk melakukan kalkulasi, data processing

Iterator

Sebuah object yang mengizinkan programmer melintasi semua element data dari sebuah collection, tanpa memperhatikan bagaimana sebuah collection diimplementasikan

Objek iterator mengendalikan iterasi pembacaan data pada collection c.

Secara umum Iterator bekerja sebagai berikut: Mulai dengan mengatur iterator pada elemen pertama pada

collection. Satu-persatu berlanjut pada elemen selanjutnya Berakhir ketika tidak ada lagi elemen pada collection yang

belum dibaca.

Ilustrasi: Iterator

Iterator

Collection

User(program yang mengakses data)