Bab 12. C++ Untuk Programer

Bab. 12 STL

Tujuan Instruksional

·         Kontainer: vector, list, dan deque.       ·         Kontainer asosiatif: multiset, set, multimap, dan map.       ·         Adapter kontainer: stack, queue, dan priority_queue.       ·         Algoritma: fill, fill_in, generate, generate_n, equal, mismatch,       lexicographical_compare, remove, remove_if,                    remove_copy, remove_copy_if, replace, replace_if, replace_copy,         replace_copy_if.

Algoritma pencarian dan pengurutan. swap, iter_swap, swap_ranges, copy_backward, merge, unique, reverse, inplace_merge, unique_copy, dan reverse_copy.

12.1 Introduksi

Standard Template Library (STL) mendefinisikan komponen-komponen berguna, berbasis-template, dan terdaur-ulang-kan yang mengimplementasikan beberapa struktur data dan algoritma untuk memproses data.

STL dikembangkan oleh Alexander Stepanov dan Meng Lee di Hawlett-Packard dan berbasis riset pemrograman generik mereka, dengan kontribusi signifikan dari David Musser. STL didesain untuk meningkatkan kinerja dan fleksibilitas. Bab ini akan mengintroduksi STL dan mendiskusikan tiga komponen kuncinya, yaitu kontainer (struktur data tertemplatisasi populer), iterator, dan algoritma. Kontainer STL merupakan struktur data yang mampu menyimpan objek-objek bertipe apapun (meski terdapat beberapa batasan). Ada tiga jenis kontainer, yaitu kontainer kelas-pertama, adapter, dan kontainer dekat.

Setiap kontainer STL memiliki beberapa fungsi anggota. Subhimpunan dari fungsi-fungsi anggota ini didefinisikan di dalam semua kontainer STL. Beberapa fungsionalitas umum dari kontainer STL akan diilustrasikan pada contoh yang berkaitan dengan vector, list, dan deque.

Iterator STL, yang memiliki kesamaan watak dengan pointer, digunakan oleh program untuk memanipulasi elemen-elemen kontainer STL. Array standard dapat juga dimanipulasi oleh algoritma STL, menggunakan pointer standard sebagai iterator. Akan Anda lihat bahwa pemanipulasian kontainer dengan iterator sangat membantu dan sangat berguna bila dikombinasikan dengan algoritma STL, dimana pada banyak kasus dapat mereduksi puluhan atau bahkan ratusan baris kode menjadi satu statemen tunggal. Terdapat lima kategori iterator yang akan didiskusikan nanti.

Algoritma STL terdiri-dari fungsi-fungsi yang melakukan pemanipulasian data seperti pencarian, pengurutan, dan pembandingan elemen-elemen atau keseluruhan elemen. STL menyediakan beberapa algoritma. Kebanyakan algoritma tersebut menggunakan iterator untuk mengakses elemen kontainer. Setiap algoritma mempunyai persyaratan minimum untuk tipe iterator yang akan digunakan. Anda akan melihat bahwa kontainer kelas-pertama mendukung beberapa tipe iterator spesifik. Tipe iterator yang didukung oleh suatu kontainer menentukan apakah kontainer tersebut dapat digunakan dengan algoritma tertentu. Iterator mengenkapsulasi mekanisme yang digunakan untuk mengakses elemen-elemen kontainer. Enkapsulasi ini membuat algoritma-algoritma STL dapat diterapkan di berbagai kontainer. Sepanjang iterator memenuhi persyaratan minimum dari algoritma, maka algoritma tersebut dapat memproses elemen-elemen kontainer. Hal ini tentu saja memampukan Anda untuk menciptakan algoritma baru.

12.2 Pengantar Kontainer

Tipe-tipe kontainer STL ditampilkan pada Gambar 12.1. Kontainer dibagi ke dalam tiga kategori utama, yaitu kontainer runtun, kontainer asosiatif, dan kontained adapter.

Gambar 12.1 Kelas Kontainer STL

Kelas Kontainer STL

Penjelasan

kontainer runtun vector deque list kontainer asosiatif set multiset map multimap kontainer adapter stack queue priority_queue

penyisipan dan penghapusan cepat dari belakang. Akses langsung ke semua elemen. penyisipan dan penghapusan cepat dari belakang atau dari depan. Akses langsung ke semua elemen. list berantai ganda, penyisipan dan penghapusan cepat di semua tempat. pencarian cepat, duplikasi tidak diperkenankan. pencarian cepat, duplikasi diperkenankan. pemetaan satu-ke-satu, duplikasi tidak diperkenankan, pencarian cepat berbasis-kunci. pemetaan satu-ke-satu, duplikasi diperkenankan, pencarian cepat berbasis-kunci. last-in, first-out (LIFO) first-in, first-out (FIFO) elemen berprioritas tertinggi adalah elemen yang pertama keluar

Fungsionalitas Kontainer STL

Kebanyakan kontainer STL memiliki fungsionalitas yang mirip. Banyak operasi generik, seperti fungsi anggota size, dapat diterapkan terhadap semua kontainer, dan banyak operasi lainnya dapat diterapkan terhadap subhimpunan kontainter yang mirip. Gambar 12.2 mendeskripsikan beberapa fungsi umum yang berlaku untuk semua kontainer STL. Perhatikan bahwa operator-operator teroverload <, <=, >, >=, ==, dan != tidak disediakan untuk priority_queue.

Header Kontainer STL

Header untuk tiap kontainer STL ditampilkan pada Gambar 12.3. Isi semua header ini berada di dalam namespace std.

Kontainer Kelas-Pertama typedef

Gambar 12.4 menampilkan beberapa jenis typedef (untuk menciptakan sinonim atau nama alias bagi nama tipe yang panjang) yang ada di dalam kontainer kelas-pertama. Semua typedef ini digunakan di dalam deklarasi generik dari variabel, parameter untuk fungsi dan nilai balik dari fungsi. Sebagai contoh, value_type di dalam setiap kontainer selalu merupakan sebuah typedef yang merepresentasikan tipe elemen yang disimpan di dalam kontainer.

Gambar 12.2 Beberapa Fungi Anggota Kontainer STL

Fungsi Anggota

Penjelasan

konstruktor default konstruktor penyalin atau pengganda destruktor empy insert size operator= operator< operator<= operator> operator>= operator== operator!= swap fungsi-fungsi yang ditemukan di dalam kontainer kelas-pertama max_size begin end rbegin rend

sebuah konstruktor yang menginisialisasi suatu kontainer kosong. Normalnya, setiap kontainer memiliki beberapa konstruktor yang menyediakan beberapa metode inisialisasi yang berbeda bagi kontainer. sebuah konstruktor yang menginisialisasi kontainer dengan salinan dari suatu kontainer yang sudah ada dan bertipe sama. destruktor berfungsi untuk membersihkan setelah sebuah kontainer tidak lagi dibutuhkan. memberikan nilai balik true jika tidak terdapat elemen di dalam kontainer; sebaliknya, menghasilkan false. menyisipkan sebuah item ke dalam kontainer. memberikan nilai balik berupa jumlah elemen yang saat ini berada di dalam kontainer. menugaskan satu kontainer kepada kontainer lainnya. menghasilkan nilai balik true jika isi dari konten pertama kurang dari isi dari konten kedua; sebaliknya, menghasilkan false. menghasilkan nilai balik true jika isi dari konten pertama kurang dari  atau sama dengan isi dari konten kedua; sebaliknya, menghasilkan false. menghasilkan nilai balik true jika isi dari konten pertama lebih dari isi dari konten kedua; sebaliknya, menghasilkan false. menghasilkan nilai balik true jika isi dari konten pertama lebih dari  atau sama dengan isi dari konten kedua; sebaliknya, menghasilkan false. menghasilkan nilai balik true jika isi dari konten pertama sama dengan isi dari konten kedua; sebaliknya, menghasilkan false. menghasilkan nilai balik true jika isi dari konten pertama tidak sama dengan isi dari konten kedua; sebaliknya, menghasilkan false. menukar elemen-elemen dari dua kontainer. memberikan nilai balik berupa jumlah elemen maksimum pada sebuah kontainer. dua versi dari fungsi ini menghasilkan nilai balik berupa sebuah iterator atau const_iteratir yang menunjuk ke elemen pertama di dalam kontainer. dua versi dari fungsi ini menghasilkan nilai balik berupa sebuah iterator atau const_iteratir yang menunjuk ke posisi berikutnya setelah akhir dari kontainer. dua versi dari fungsi ini menghasilkan nilai balik berupa sebuah reverse_iterator atau const_reverse_iteratir yang menunjuk ke elemen terakhir dari kontainer. dua versi dari fungsi ini menghasilkan nilai balik berupa sebuah reverse_iterator atau const_reverse_iteratir yang menunjuk ke posisi berikutnya setelah elemen terakhir pada kontainer.

Gambar 12.3 Header Kontainer STL

<vector> <list> <deque> <queue> <stack> <map> <set> <valarray> <bitset>

memuat queue dan priority_queue memuat map dan multimap memuat set dan multiset

Gambar 12.4 typedef di dalam Kontainer Kelas-Pertama

typedef

Penjelasan

allocator_type value_type reference const_reference pointer const_pointer iterator const_iterator reverse_iterator const_reverse_iterator difference_type size_type

tipe objek yang digunakan untuk mengalokasikan memori kontainer. tipe elemen yang disimpan di dalam kontainer. referensi untuk tipe elemen kontainer. referensi konstanta untuk tipe elemen kontainer. Referensi semacam ini dapat digunakan hanya untuk membaca elemen di dalam kontainer dan untuk melakukan operasi const. pointer untuk tipe elemen kontainer. pointer untuk sebuah konstanta dari tipe elemen kontainer. iterator yang menunjuk ke sebuah elemen dari tipe elemen kontainer. iterator konstanta yang menunjuk ke sebuah elemen dari tipe elem kontainer dan dapat digunakan hanya untuk membaca elemen. iterator terbalik yang menunjuk ke sebuah elemen dari tipe elemen kontainer. Tipe iterator ini untuk beriterasi menjelajahi kontainer dengan arah terbalik. iterator terbalik konstanta yang menunjuk ke sebuah elemen dari tipe elemen kontainer dan hanya dapat digunakan untuk membaca elemen. Tipe iterator ini untuk beriterasi menjelajahi kontainer dengan arah terbalik. tipe yang dihasilkan dari pengurangan atas dua iterator yang menunjuk ke kontainer yang sama (operator – tidak didefinisikan untuk iterator dari list dan kontainer asosiatif). tipe yang digunakan untuk menghitung item di dalam sebuah kontainer dan indeks untuk kontainer runtun.

Ketika mempersiapkan penggunaan suatu kontainer STL, adalah hal penting untuk memastikan bahwa tipe elemen yang sedang disimpan di dalam kontainer mendukung fungsionalitas yang diinginkan. Ketika sebuah elemen disisipkan ke dalam suatu kontainer, salinan dari elemen tersebut yang disisipkan. Karena alasan ini, tipe elemen harus menyediakan konstruktor penyalin dan operator penugasan sendiri. Juga, kontainer asosiatif dan banyak algoritma memerlukan pembandingan elemen. Untuk itu, tipe elemen harus menyediakan operator ekualitas (==) dan operator kurang-dari (<).

12.3 Pengantar Iterator

Iterator memiliki banyak kesamaan dengan pointer dan digunakan untuk menunjuk ke elemen-elemen kontainer kelas-pertama. Iterator menyimpan informasi yang sensitif dengan kontainer tertentu; oleh karena itu, iterator diimplementasikan berdasarkan tipe kontainer tertentu. Beberapa operasi iterator seragam di semua kontainer. Misalnya, operator dereferensi (*) mendereferensi sebuah iterator sehingga Anda dapat menggunakan elemen yang ditunjuk oleh iterator tersebut. Operasi ++ diterapkan pada iterator untuk menggesernya ke elemen berikutnya di dalam kontainer (sama seperti menginkremen pointer di dalam array untuk menunjuk elemen array berikutnya).

Kontainer STL kelas-pertama menyediakan fungsi begin dan end. Fungsi begin menghasilkan nilai balik berupa sebuah iterator yang menunjuk ke elemen pertama di dalam kontainer. Fungsi end menghasilkan nilai balik berupa sebuah iterator yang menunjuk ke elemen pertama setelah elemen terakhir di dalam kontainer (elemen yang belum ada). Jika iterator i menunjuk sebuah elemen tertentu, maka ++i akan menunjuk ke elemen berikutnya dan *i akan menunjuk ke elemen yang ditunjuk oleh i. Iterator yang dihasilkan dari end secara umum digunakan di dalam suatu perbandingan ekualitas atau inekualitas untuk menentukan apakah “iterator penggerak atau penggeser” (dalam hal ini adalah i) telah mencapai akhir kontainer atau tidak.

Sebuah objek bertipe iterator menunjuk ke suatu elemen kontainer yang dapat dimodifikasi. Sebuah objek bertipe const_interator menunjuk ke suatu elemen kontainer yang tidak dapat dimodifikasi.

Menggunakan istream_iterator untuk Masukan dan ostream_iterator untuk Keluaran

Akan digunakan iterator dengan runtun. Runtun ini bisa berada di dalam kontainer, atau dapat pula berupa runtun masukan atau runtun keluaran. Program pada Gambar 12.5 mendemonstrasikan masukan dari masukan standard (runtun data untuk masukan ke dalam program) menggunakan istream_iterator, dan keluaran ke keluaran standard (runtun data untuk keluaran dari program) menggunakan ostream_iterator. Program memasukkan dua integer dari papanketik dan menampilkan hasil penjumlahan atas kedua integer tersebut. Seperti yang akan Anda lihat nanti pada bab ini, istream_iterator dan ostream_iterator dapat digunakan dengan algoritma-algoritma STL untuk menciptakan statemen berguna. Sebagai contoh, Anda dapat menggunakan ostream_iterator dengan algoritma copy untuk menyalin isi sebuah kontainer ke aliran (stream) keluaran standard dengan satu statemen tunggal.

Gambar 12.5 Mendemonstrasikan masukan dan keluaran dengan iterator

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

// Gambar 12.5: gambar12_05.cpp // Mendemonstrasikan masukan dan keluaran dengan iterator. #include <iostream> #include <iterator> // ostream_iterator and istream_iterator using namespace std; int main() {   cout << "Masukkan dua integer: ";   // menciptakan istream_iterator untuk membaca nilai-nilai int dari cin   istream_iterator< int > inputInt( cin );   int angka1 = *inputInt; // membaca int dari masukan standard   ++inputInt; // menggeser iterator ke nilai masukan berikutnya   int angka2 = *inputInt; // membaca int dari masukan standard   // menciptakan ostream_iterator untuk menuliskan nilai-nilai int ke cout   ostream_iterator< int > outputInt( cout );   cout << "Penjumlahan atas kedua integer adalah: ";   *outputInt = angka1 + angka2; // mengirim hasil ke cout   cout << endl; } // akhir dari main

Masukkan dua integer: 12 25

Penjumlahan atas kedua integer adalah 37

Baris 12 menciptakan sebuah istream_iterator yang mampu mengekstrak nilai-nilai int dari objek masukan standard, cin. Baris 14 mendereferensi iterator inputInt untuk membaca integer pertama dari cin dan menugaskan integer itu kepada angka1. Operator dereferensi * diterapkan terhadap iterator inputInt untuk mendapatkan nilai dari aliran yang terkait dengan inputInt; hal ini mirip dengan mendereferensi sebuah pointer. Baris 15 memposisikan iterator inputInt ke nilai berikutnya di dalam aliran masukan. Baris 16 memasukkan integer berikutnya dari inputInt dan menugaskannya kepada angka2.

Baris 19 menciptakan sebuah ostream_iterator yang mampu menyisipkan nilai-nilai int ke dalam objek keluaran standard, cout. Baris 22 menyisipkan sebuah integer ke dalam cout dengan menugaskan penjumlahan atas angka1 dan angka2 kepada *outputInt. Perhatikan bahwa operator dereferensi * pada *outputInt dipakai sebagai lvalue di dalam statemen penugasan. Jika Anda ingin menyisipkan nilai lain menggunakan outputInt, maka iterator itu harus diinkremen dengan ++ (prefiks dan postfiks inkremen dapat digunakan).

Hirarki Kategori Iterator

Gambar 12.6 menampilkan beberapa kategori iterator STL. Setiap kategori menyediakan sekelompok fungsionalitas. Gambar 12.7 mengilustrasikan hirarki dari kategori iterator. Seperti Anda perhatikan dari atas ke bawah hirarki, setiap kategori iterator mendukung semua fungsionalitas kategori di atasnya. Jadi, tipe iterator “terlemah” adalah tipe iterator yang berada di atas dan yang paling “kuat” adalah yang berada di bawah. Ingat bahwa hirarki ini bukanlah hirarki pewarisan.

Kategori iterator yang didukung oleh tiap kontainer menentukan apakah kontainer itu dapat digunakan dengan algoritma tertentu di dalam STL. Kontainer yang mendukung iterator random access (akses-acak) dapat digunakan dengan semua algoritma di dalam STL. Seperti yang akan Anda lihat, pointer ke array dapat dipakai menggantikan iterator di dalam hampir semua algoritma STL, termasuk menggantikan iterator random access. Gambar 12.8 menampilkan kategori iterator untuk tiap kontainer STL. Kontainer kelas-pertama (vector, deque, list, set, multiset, map, dan multimap), string dan array semuanya dapat dijelajahi oleh iterator.

Gambar 12.6 Kategori Iterator

Kategori

Penjelasan

input output forward bidirectional random access

digunakan untuk membaca sebuah elemen dari suatu kontainer. Iterator input hanya dapat menggerakkan hanya dengan arah maju (dari awal sampai akhir kontainer) satu elemen per waktu. Iterator input hanya mendukung algoritma one-pass, iterator input yang sama tidak dapat dipakai untuk melewati suatu runtun dua kali. digunakan untuk menulis sebuah elemen ke dalam suatu kontainer. Iterator output bisa menggerakkan hanya dengan arah maju satu elemen per waktu. Iterator output hanya mendukung algoritma one-pass, iterator input yang sama tidak dapat dipakai untuk melewati suatu runtun dua kali. menggabungkan kapabilitas iterator input dan iterator output dan memperoleh posisisnya di dalam kontainer (sebagai informasi keadaan). menggabungkan kapabilitas suatu iterator forward dengan kemampuan untuk bergerak ke arah mundur (dari akhir ke awal kontainer). Iterator bidirectional mendukung algoritma multipass. menggabungkan kapabilitas suatu iterator forward dengan kemampuan untuk mengakses secara langsung sembarang elemen di dalam kontainer, untuk melompat maju atau mundur sejauh sembarang jumlah elemen.

Gambar 12.7 Hirarki kategori iterator

Gambar 12.8 Tipe Iterator yang Didukung oleh Setiap Kontainer

Kontainer	Tipe iterator yang didukung
kontainer runtun (kelas-pertama) vector deque list kontainer asosiatif (kelas pertama) set multiset map multimap adapter kontainer stack queue priority_queue	random access random access bidirectional bidirectional bidirectional bidirectional bidirectional - - -

Iterator typedef Terdefinisi

Gambar 12.9 menampilkan beberapa iterator typedef terdefinisi yang berada di dalam definisi-definisi kelas pada kontainer STL. Tidak setiap tydef didefinisikan untuk tiap kontainer. Digunakan versi const dari iterator untuk menjelajahi kontainer read-only. Digunakan iterator terbalik untuk menjelajahi iterator dengan arah terbalik.

Gambar 12.9 Iterator typedef

typedef terdefinisi untuk tipe-tipe iterator	Arah dari ++	Kapabilitas
iterator const_iterator reverse_iterator const_reverse_iterator	forward forward backward backward	read/write read read/write read

Operasi Iterator

Gambar 12.10 menampilkan beberapa operasi yang dapat dilakukan pada tiap tipe iterator. Untuk iterator input dan ouput, adalah hal yang tidak mungkin untuk menyimpan iterator kemudian menggunakannya nilai yang tersimpan di kemudian waktu.

Gambar 12.10 Operasi-Operasi Iterator untuk Tiap Tipe Iterator

Operasi iterator

Penjelasan

semua iterator ++p p++ iterator input *p p = p1 p == p1 p != p1 iterator output *p p = p1 iterator forward iterator bidirectional --p p— iterator random access p += i p -= i p + i atau i + p p – i p – p1 p[i] p < p1 p <= p1 p > p1 p >= p1

melakukan preinkremen terhadap sebuah iterator. melakukan postinkremen terhadap sebuah iterator. mendereferensi sebuah iterator. menugaskan satu iterator kepada iterator lainnya. membandingkan iterator untuk ekualitas. membandingkan iterator untuk inekualitas. mendereferensi sebuah iterator. menugaskan satu iterator kepada iterator lainnya. iterator forward menyediakan semua fungsionalitas kedua iterator input dan iterator output. melakukan predekremen terhadap sebuah iterator. melakukan postdekremen terhadap sebuah iterator. menginkreman iterator p sejauh i posisi. mendekremen iterator p sejauh i posisi. nilai ekspresi adalah sebuah iterator diposisikan pada p yang diinkremen sejauh i posisi. nilai ekspresi adalah sebuah iterator diposisikan pada p yang didekremen sejauh i posisi. nilai ekspresi merupakan sebuah integer yang merepresentasikan jarak antara dua elemen di dalam kontainer yang sama. memberikan nilai balik berupa sebuah referensi ke elemen beroffset dari p sejauh i posisi. memberikan nilai balik true jika iterator p kurang dari iterator p1 (iterator p berada sebelum iterator p1 di dalam kontainer); sebaliknya, menghasilkan false. memberikan nilai balik true jika iterator p kurang dari  atau sama dengan iterator p1 (iterator p berada sebelum atau berada di lokasi yang sama dengan iterator  p1 di dalam kontainer); sebaliknya, menghasilkan false. memberikan nilai balik true jika iterator p lebih dari iterator p1 (iterator p berada setelah iterator p1 di dalam kontainer); sebaliknya, menghasilkan false. memberikan nilai balik true jika iterator p lebih dari  atau sama dengan iterator p1 (iterator p berada setelah atau berada di lokasi yang sama dengan iterator  p1 di dalam kontainer); sebaliknya, menghasilkan false.

12.4 Pengantar Algoritma

Algoritma STL dapat dipakai secara generik pada berbagai kontainer. STL menyediakan banyak algoritma yang seringkali akan Anda pakai untuk memanipulasi kontainer. Penyisipan, penghapusan, pencarian, pengurutan, dan lainnya merupakan sebagain dari pemanipulasian kontainer.

STL menyertakan beberapa algoritma standard. Akan ditunjukkan beberapa di antaranya pada bab ini. Algoritma STL beroperasi pada elemen-elemen kontainer hanya bisa mengakses secara tak-langsung melalui iterator. Banyak algoritma beroperasi pada runtun elemen yang didefinisikan oleh sepasang iterator, satu iterator menunjuk ke elemen pertama runtun dan satu iterator lainnya menunjuk ke satu elemen setelah elemen terakhir. Juga, adalah hal yang memungkinkan untuk menciptakan algoritma Anda sendiri yang beroperasi dengan gaya sama sehingga dapat digunakan dengan kontainer STL dan iterator.

Gambar 12.11 Beberapa Algoritma STL Pemodifikasi Runtun

Beberapa algoritma STL
copy copy_backward fill fill_n generate generate_n iter_swap	partition random_shuffle remove remove_copy remove_copy_if remove_if replace	replace_copy replace_copy_if replace_if reverse reverse_copy rotate rotate_copy	stable_partition swap swap_ranges transform unique unique_copy

Algoritma seringkali menjadikan iterator sebagai nilai balik yang mengindikasikan hasil algoritma tersebut. Algoritma find, misalnya, mencari lokasi sebuah elemen dan memberikan nilai balik berupa sebuah iterator yang menunjuk ke elemen tersebut. Jika elemen yang dicari tidak ditemukan, maka find akan menghasilkan nilai balik berupa iterator yang menunjuk ke satu elemen setelah elemen terakhir, yang dilewatkan untuk mendefinisikan akhir rentang yang dicari. Algoritma find dapat digunakan dengan sembarang kontainer kelas-pertama. Algoritma STL menciptakan peluang untuk mendaur-ulang kode, sehingga Anda dapat menghemat waktu pengembangan program.

Sebuah algoritma dapat digunakan dengan kontainer yang mendukung sedikitnya persyaratan iterator minimum. Beberapa iterator menuntut iterator yang kuat; misalnya, algoritma sort menuntut iterator random-access.

Gambar 12.11 menampilkan beberapa algoritma STL, yaitu algoritma yang menghasilkan pemodifikasian kontainer.

Gambar 12.12 Beberapa Algoritma STL Non-Pemodifikasi Runtun

Beberapa algoritma STL Non-Pemodifikasi Runtun
adjacent_find count count_if	equal find find_each	find_end find_first_of find_if	mismatch search searc_n

Gambar 12.12 menampilkan beberapa algoritma STL pemodifikasi runtun, yaitu algoritma yang tidak menghasilkan pemodifikasian kontainer. Gambar 12.13 menampilkan beberapa algoritma numerik dari header <numeric>.

Gambar 12.13 Beberapa Algoritma STL Numerik dalam header <numeric>

Beberapa algoritma STL Numerik
accumulate inner_product	partial_sum adjacent_difference

12.5 Kontainer Runtun

STL menyediakan tiga kontainer runtun, yaitu vector, list, dan deque. Template kelas vector dan template kelas deque keduanya didasarkan pada array. Template kelas list mengimplementasikan sebuah struktur data list-berantai.

Salah satu kontainer yang paling populer di dalam STL adalah vector. Sebuah vector dapat mengubah ukurannya secara dinamis. Tidak seperti array biasa di dalam C atau C++, vector dapat ditugaskan satu sama lain. Hal ini tidak mungkin dilakukan pada array C yang berbasis pointer, karena nama array merupakan pointer konstanta sehingga tidak bisa dilakukan penugasan. Sama seperti array C, subskript dari vector tidak melakukan pengecekan rentang secara otomatis, tetapi template kelas vector menyediakan kapabilitas ini melalui fungsi anggota at.

Gambar 12.2 telah menyajikan beberapa operasi yang dapat diterapkan pada semua kontainer. Di luar operasi tersebut, secara umum setiap kontainer menyediakan berbagai kapabilitas lain. Banyak kapabilitas ini berlaku untuk beberapa kontainer, tetapi tidak semuanya sama efisiennya untuk tiap kontainer. Anda harus memilih kontainer yang paling sesuai dengan aplikasi Anda.

Selain operasi yang dideskripsikan pada Gambar 12.2, kontainer runtun mempunya beberapa operasi lainnya, seperti front untuk menghasilkan nilai balik berupa sebuah referensi ke elemen pertama di dalam suatu kontainer tak-kosong, push_back untuk menyisipkan suatu elemen baru ke ujung akhir sebuah kontainer, back untuk menghasilkan nilai balik berupa sebuah referensi ke elemen terakhir di dalam suatu kontainer tak-kosong, dan pop_back untuk menghapus elemen terakhir di dalam sebuah kontainer.

12.5.1 Kontainer Runtun vector

Template kelas vector menyediakan suatu struktur data dengan lokasi-lokasi memori yang bertetangga. Hal ini membuat akses langsung menjadi efisien ke sembarang elemen melalui sebuah vektor menggunakan operator subskript [ ], sama seperti array pada C atau C++. Template kelas vector paling banyak digunakan ketika data di dalam kontainer dapat dengan mudah diakses melalui sebuah subskript. Ketika memori vector telah penuh, vector mengalokasikan area memori bertetangga yang lebih besar, menyalin semua elemen awal ke memori baru dan membebaskan memori lama.

Bagian penting dari setiap kontainer adalah tipe iterator yang didukung. Ini menentukan algoritma mana yang dapat diterapkan terhadap kontainer. Sebuah vector mendukung iterator random-access, jadi semua operasi iterator pada Gambar 12.10 dapat diterapkan terhadap iterator vector. Semua algoritma STL dapat beropasi pada sebuah vector. Iterator untuk sebuah vector kadangkala diimplementasikan sebagai pointer yang menunjuk ke elemen-elemen vector. Setiap algoritma STL yang mengambil iterator sebagai argumen mensyaratkan bahwa iterator tersebut harus menyediakan suatu level fungsionalitas minimum. Jika suatu algoritma mensyaratkan sebuah iterator forward, misalnya, maka algoritma itu dapat beroperasi pada sembarang kontainer yang menyediakan iterator forward, iterator bidirectional, atau iterator random-access. Sepanjang kontainer mendukung fungsionalitas iterator minimum pada algoritma, maka algoritma tersebut dapat beroperasi pada kontainer tersebut.

Menggunakan Vektor dan Iterator

Gambar 21.14 mengilustrasikan beberapa fungsi dari template kelas vector. Banyak dari fungsi-fungsi ini tersedia di dalam setiap kontainer kelas-pertama. Anda harus menyertakan header <vector> untuk menggunakan template kelas vector.

Baris 14 mendefinisikan sebuah instans bernama integers dari template kelas vector yang menyimpan nilai-nilai int. Ketika objek ini diinstansiasi, maka sebuah vector kosong diciptakan dengan ukuran 0 (jumlah elemen yang disimpan di dalam vector) dan kapasitas 0 (jumlah elemen yang dapat disimpan tanpa mengalokasikan memori tambahan kepada vector).

Baris 16 dan 17 mendemonstrasikan fungsi size dan capacity; setiap fungsi awalnya memberikan nilai balik 0 untuk vector v pada contoh ini. Fungsi size, tersedia bagi setiap kontainer, memberikan nilai balik berupa jumlah elemen yang saat ini disimpan di dalam kontainer. Fungsi capacity memberikan nilai balik berupa jumlah elemen yang dapat disimpan di dalam vector sebelum vector secara dinamis perlu mengekspansi dirinya untuk mengakomodasi elemen tambahan.

Gambar 12.14 Mendemonstrasikan Template Kelas vector STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

// Gambar 12.14: gambar12_14.cpp // Mendemonstrasikan template kelas vector STL. #include <iostream> #include <vector> // definisi tempalte-kelas vector using namespace std; // prototipe untuk template fungsi tampilVektor template < typename T > void tampilVektor( const vector< T > &integers2 ); int main() {   const int UKURAN = 6; // mendefinisikan ukuran array   int array[ UKURAN ] = { 1, 2, 3, 4, 5, 6 }; // menginisialisasi array   vector< int > integers; // menciptakan vektor yang memuat nilai-nilai int   cout << "Ukuran awal vektor adalah: " << integers.size()     << "\nKapasitas awal vektor adalah: " << integers.capacity();   // fungsi push_back berada di dalam setiap kontainer runtun   integers.push_back( 2 );   integers.push_back( 3 );   integers.push_back( 4 );   cout << "\nUkuran vektor adalah: " << integers.size()     << "\nKapasitas vektor adalah: " << integers.capacity();   cout << "\n\nMenampilkan array menggunakan notasi pointer: ";   // menampilkan array menggunakan notasi pointer   for ( int *ptr = array; ptr != array + UKURAN; ++ptr )     cout << *ptr << ' ';   cout << "\nMenampilkan vektor menggunakan notasi iterator: ";   tampilVektor( integers );   cout << "\nIsi vektor terbalik adalah: ";   // dua iterator const reverse   vector< int >::const_reverse_iterator reverseIterator;   vector< int >::const_reverse_iterator tempIterator = integers.rend();   // menampilkan vektor dengan urutan terbalik menggunakan reverse_iterator   for ( reverseIterator = integers.rbegin();     reverseIterator!= tempIterator; ++reverseIterator )     cout << *reverseIterator << ' ';   cout << endl; } // akhir dari main // template fungsi untuk menampilkan elemen-elemen vektor template < typename T > void tampilVektor( const vector< T > &integers2 ) {                  typename vector< T >::const_iterator constIterator; // const_iterator   // menampilkan elemen-elemen vektor menggunakan const_iterator   for ( constIterator = integers2.begin();     constIterator != integers2.end(); ++constIterator )     cout << *constIterator << ' '; } // akhir dari fungsi tampilVektor

Ukuran awal vektor adalah: 0

Kapasitas awal vektor adalah: 0

Ukuran vektor adalah: 3

Kapasitas vektor adalah: 4

Menampilkan array menggunakan notasi pointer: 1 2 3 4 5 6

Menampilkan vektor menggunakan notasi iterator: 2 3 4

Isi vektor terbalik adalah: 4 3 2

Baris 20-22 menggunakan fungsi push_back, tersedia di dalam semua kontainer runtun, untuk menambahkan sebuah elemen ke ujung akhir vector. Jika sebuah elemen ditambahkan ke dalam sebuah vector yang telah penuh, maka vector tersebut akan menambah ukurannya, beberapa implementasi STL menggandakan dua kali lipat kapasitas vector.

Baris 24 dan 25 menggunakan size dan capacity untuk mengilustrasikan ukuran dan kapasitas baru vector setelah tiga operasi push_bach diterapkan. Fungsi size menghasilkan nilai balik 3, jumlah elemen yang ditambahkan ke dalam vector. Fungsi capacity menghasilkan nilai balik 4, mengindikasikan bahwa Anda dapat menambahkan satu elemen tambahan lagi sebelum vector mengekspansi memorinya. Ketika elemen pertama ditambahkan, vector mengalokasikan memori untuk satu elemen, dan ukuran menjadi 1 untuk mengindikasikan bahwa vector hanya memuat satu elemen. Ketika elemen kedua ditambahkan, kapasitasnya digandakan menjadi 2 dan ukuran menjadi 2. Ketika elemen ketiga ditambahkan, kapasitas dilipat-duakan lagi menjadi 4. Jadi sebenarnya Anda dapat menambahkan satu elemen lagi sebelum vector melipat-gandakan kapasitasnya. Ketika akhirnya vector memenuhi kapasitas yang teralokasi dan program mencoba untuk menambahkan satu elemen baru ke dalam vector, maka vector akan melipat-duakan kapasitasnya menjadi 8.

Baris 29-30 mendemonstrasikan bagaimana menampilkan isi sebuah array menggunakan pointer dan aritmatika pointer. Baris 33 memanggil fungsi tampilVektor (deidefinisikan pada baris 49-57) untuk menampilkan isi sebuah vector menggunakan iterator. Template fungsi tampilVektor menerima sebuah referensi const yang menunjuk kepada sebuah vector (integers2) sebagai argumennya. Baris 51 mendefinisikan sebuah const_iterator memanggil constIterator yang beriterasi menjelajahi vector dan menampilkan isinya. Perhatikan bahwa deklarasi pada baris 51 diprefiks dengan katakunci typename.

Karena tampilVektor merupakan sebuah template fungsi dan vector<T> akan dispesialisasi secara berbeda untuk tiap spesialisasi template fungsi, kompiler tidak dapat memberitahu pada saat waktu kompilasi apakah vector<T>::const_iterator sebuah tipe atau tidak. Pada suatu spesialisasi tertentu, const_iterator bisa jadi berupa sebuah variabel static. Kompiler memerlukan informasi ini untuk mengkompilasi program secara tepat. Oleh karena itu, Anda harus memberitahu kompiler bahwa nama yang dikualifikasi, ketika pengkualifikasi merupakan sebuah tipe independen, adalah sebuah tipe di dalam setiap spesialisasi.

Sebuah const_iterator memampukan program untuk membaca elemen-elemen dari vector, tetapi ia tidak mengijinkan program untuk memodifikasi elemen-elemen tersebut. Statemen for pada baris 54-56 menginisialisasi constIterator menggunakan fungsi anggota begin, yang menghasilkan nilai balik berupa sebuah const_iterator untuk elemen pertama di dalam vector. Sebuah const_iterator dijadikan nilai balik karena pengenal integers2 telah dideklarasikan const di dalam daftar parameter pada fungsi tampilVektor. Loop terus beriterasi sepanjang constIterator tidak meraih ujung akhir vector. Hal ini dilakukan dengan membandingkan constIterator dengan hasil dari integers.end(), yang menghasilkan sebuah iterator yang mengindikasikan lokasi satu elemen setelah elemen terakhir di dalam vector. Jika constIterator sama dengan nilai ini, maka ujung akhir vector telah diraih. Fungsi begin dan end tersedia untuk semua kontainer kelas-pertama. Tubuh loop melakukan dereferensi terhadap iterator constIterator untuk mendapatkan nilai di dalam elemen sekarang pada vector. Ingat bahwa iterator berperilaku seperti pointer yang menunjuk ke elemen dan bahwa operator * dioverload untuk menghasilkan sebuah referensi yang menunjuk ke elemen. Ekspresi ++constIterator (baris 55) memposisikan iterator ke elemen berikutnya di dalam vector.

Baris 37 mendeklarasikan sebuah const_reverse_iterator yang dapat digunakan untuk beriterasi dengan arah mundur di dalam vector. Baris 38 mendeklarasikan sebuah variabel const_reverse_iterator, tempIterator, dan menginisialisasinya dengan iterator yang dijadikan nilai balik oleh fungsi rend. Semua kontainer kelas-pertama mendukung tipe iterator ini. Baris 42-43 menggunakan statemen for, seperti yang ada di dalam fungsi tampilVektor untuk beriterasi menjelajahi vector. Fungsi begin dan end, rbegin dan rend dapat menghasilkan nilai balik berupa sebuah const_reverse_iterator atau berupa sebuah reverse_iterator, tergantung apakah kontainer konstanta atau tidak.

Fungsi Pemanipulas-ELemen Vektor

Gambar 12.15 mengilustrasikan beberapa fungsi yang memampukan penarikan dan pemanipulasian elemen-elemen sebuah vector. Baris 15 menggunakan konstruktor vector teroverload yang mengambil dua iterator sebagai argumen untuk menginisialisasi integers. Baris 15 menginisialisasi integers dengan isi array dari lokasi array sampai lokasi array + UKURAN.

Gambar 12.15 Menguji Fungsi Pemanipulasi Elemen

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

// Gambar 12.15: gambar12_15.cpp // Menguji template kelas fungsi-fungsi pemanipulasi-elemen // di dalam kelas vector STL. #include <iostream> #include <vector> // definisi template-kelas vector #include <algorithm> // algoritma copy #include <iterator> // iterator ostream_iterator #include <stdexcept> // eksepsi out_of_range using namespace std; int main() {   const int UKURAN = 6;   int array[ UKURAN ] = { 1, 2, 3, 4, 5, 6 };   vector< int > integers( array, array + UKURAN );   ostream_iterator< int > output( cout, " " );   cout << "Vektor integers memuat: ";   copy( integers.begin(), integers.end(), output );   cout << "\nElemen pertama vektor integers: " << integers.front()    << "\nElemen terakhir vektor integers: " << integers.back();   integers[ 0 ] = 7; // menetapkan elemen pertama menjadi 7   integers.at( 2 ) = 10; // menetapkan elemen pada posisi 2 menjadi 10   // menyisipkan 22 pada elemen kedua   integers.insert( integers.begin() + 1, 22 );   cout << "\n\nIsi vektor integers setelah perubahan: ";   copy( integers.begin(), integers.end(), output );   // mengakses elemen di luar rentang   try   {     integers.at( 100 ) = 777;   } // akhir dari try   catch( out_of_range &outOfRange )// eksepsi out_of_range   {     cout << "\n\nEksepsi: " << outOfRange.what();   } // akhir dari catch   // menghapus elemen pertama   integers.erase( integers.begin() );   cout << "\n\nVektor integers setelah penghapusan elemen pertama: ";   copy( integers.begin(), integers.end(), output );   // menghapus elemen-elemen yang lain   integers.erase( integers.begin(), integers.end() );   cout << "\nSetelah menghapus semua elemen, vektor integers "     <<( integers.empty() ?"menjadi" : "menjadi tidak" ) << " kosong";   // menyisipkan elemen-elemen dari array   integers.insert( integers.begin(), array, array + UKURAN );   cout << "\n\nIsi vektor integers sebelum penghapusan: ";   copy( integers.begin(), integers.end(), output );   // vektor integers kosong; clear menghapus semuanya   integers.clear();   cout << "\nSetelah penghapusan, vektor integers "    <<( integers.empty() ?"menjadi" : "menjadi tidak" ) << " kosong" << endl; } // akhir dari main

Vektor integers memuat: 1 2 3 4 5 6

Elemen pertama vektor integers: 1

Elemen terakhir vektor integers: 6

Isi vektor integers setelah perubahan: 7 22 2 10 4 5 6

Eksepsi: invalid vector<T> subscript

Vektor integers setelah penghapusan elemen pertama: 22 2 10 4 5 6

Setelah menghapus semua elemen, vektor integers menjadi kosong

Isi vektor integers sebelum penghapusan: 1 2 3 4 5 6

Setelah penghapusan vektor integers menjadi kosong

Baris 16 mendefinisikan sebuah ostream_iterator, dinamakan output, yang dapat digunakan untuk menampilkan integer-integer dipisahkan oleh spasi melalui cout. Sebuah ostream_iterator merupakan mekanisme yang hanya menampilkan nilai-nilai tipe int atau tipe kompatibelnya. Argumen pertama dari konstruktor menspesifikasi aliran keluaran, dan argumen kedua adalah sebuah string yang menspesifikasi separator atau pemisah keluaran (nilai-nilai integer), dalam kasus ini, string memuat karakter spasi. Digunakan ostream_iterator (yang didefinisikan di dalam header <iterator>) untuk menampilkan isi vector pada contoh ini.

Baris 19 menggunakan algoritma copy dari STL untuk menampilkan keseluruhan isi vector integers. Algoritma copy menyalin setiap elemen di dalam kontainer mulai dari lokasi yang dispesifikasi oleh iterator di dalam argumen pertamanya dan berlanjut sampai lokasi yang dispesifikasi di dalam argumen keduanya. Elemen-elemen disalin ke lokasi yang dispesifikasi oleh iterator output pada argumen terakhir. Untuk menggunakan algoritma-algoritma STL, Anda harus menyertakan header <algorithm>.

Baris 21-22 menggunakan fungsi front dan back (tersedia untuk semua kontainer runtun) untuk menentukan elemen pertama dan terakhir dari vector. Perhatikan bahwa perbedaan antara fungsi front dan begin. Fungsi front menghasilkan sebuah referensi ke elemen pertama di dalam vector, sedangkan fungsi begin menghasilkan sebuah iterator random access yang menunjuk ke elemen pertama di dalam vector. Perhatikan pula perbedaan antara fungsi back dan end. Fungsi back menghasilkan sebuah referensi ke elemen terakhir di dalam vector, sedangkan fungsi end menghasilkan sebuah iterator random access yang menunjuk ke ujung akhir vector (lokasi satu elemen setelah elemen terakhir).

Baris 24-25 mengilustrasikan dua cara untuk mensubskript sebuah vector (yang juga dapat dilakukan terhadap deque). Baris 24 menggunakan operator yang telah dioverload untuk menghasilkan sebuah referensi ke nilai pada lokasi tertentu atau menghasilkan sebuah referensi konstanta yang menunjuk ke nilai tersebut, tergantung dari apakah kontainer konstanta atau tidak. Fungsi at (baris 25) melakukan operasi yang sama, tetapi dengan pemeriksaan rentang. Fungsi at pertama-tama memeriksa nilai yang disuplai sebagai argumen dan menentukan apakah ia berada di dalam rentang vector atau tidak. Jika tidak, fungsi at akan melempar sebuah eksepsi out_of_range yang didefinisikan di dalam header <stdexcept> (seperti didemonstrasikan pada baris 34-41). Gambar 12.16 menunjukkan beberapa tipe eksepsi STL.

Gambar 12.16 Beberapa Tipe Eksepsi STL

Tipe Eksepsi STL

Penjelasan

out_of_range invalid_argument length_error bad_alloc

mengindikasikan bahwa subskript di luar rentang, misalnya, ketika sebuah subskript tak-valid dispesifikasi untuk vector pada fungsi anggota at. mengindikasikan sebuah argumen tak-valid yang dilewatkan ke suatu fungsi. mengindikasikan sebuah percobaan untuk menciptakan kontainer, string, atau lainnya yang terlalu panjang. mengindikasikan bahwa sebuah percobaan untuk mengalokasikan memori menggunakan new (atau dengan sebuah alokator) telah gagal karena tidak tersedia memori yang cukup.

Baris 28 menggunakan salah satu dari tiga fungsi insert teroverload yang disediakan oleh setiap kontainer runtun. Baris 28 menyisipkan nilai 22 di depan elemen pada lokasi yang dispesifikasikan oleh iterator pada argumen pertamanya. Pada contoh ini, iterator menunjuk ke elemen kedua vector, jadi 22 disisipkan sebagai elemen kedua dan elemen kedua yang asli menjadi elemen ketiga di dalam vector. Versi lain dari insert memampukan penyisipan salinan jamak dari nilai yang sama dimulai pada posisi tertentu di dalam kontainer, atau menyisipkan rentang nilai dari kontainer (atau array) lain, dimulai dari posisi tertentu.

Baris 44 dan 49 menggunakan dua fungsi erase yang tersedia bagi semua kontainer kelas-pertama. Baris 44 mengindikasikan bahwa elemen pada lokasi yang dispesifikasi oleh argumen iterator harus dibuang dari kontainer (pada contoh ini, elemen pada awal vector). Baris 49 menspesifikasi bahwa semua elemen di dalam rentang, mulai dari lokasi argumen pertama sampai lokasi argumen kedua (tetapi tidak termasuk elemen pada lokasi yang dispesifikasi oleh argumen kedua) harus dihapus dari kontainer. Baris 51 menggunakan fungsi empty (tersedia bagi semua kontainer dan adapter) untuk memastikan apakah vector kosong atau tidak.

Baris 54 mendemonstrasikan versi fungsi insert yang menggunakan argumen kedua dan ketiga untuk menspesifikasi lokasi awal dan lokasi akhir di dalam sebuah runtun nilai (bisa saja dari kontainer lain; pada kasus ini, dari array yang memuat integer, array)  yang harus disisipkan ke dalam vector. Ingat bahwa lokasi akhir menspesifikasi posisi, di dalam runtun, setelah elemen terakhir disisipkan. Terakhir, baris 59 menggunakan fungsi clear (yang berada di dalam semua kontainer kelas-pertama) untuk mengosongkan vector. Fungsi ini memanggil versi erase yang digunakan pada baris 51 untuk mengosongkan vector.

12.5.2 Kontainer Runtun list

Kontainer runtun list menyediakan implementasi efisien untuk operasi penyisipan dan penghapusan pada sembarang lokasi di dalam kontainer. Jika kebanyakan penyisipan dan penghapusan terjadi di ujung akhir kontainer, maka struktur data deque lah yang dipakai karena menyediakan implementasi yang lebih efisien. Template kelas list diimplementasikan sebagai list-berantai ganda, dimana setiap simpul di dalam list memuat sebuah pointer ke simpul sebelumnya di dalam list dan ke simpul berikutnya di dalam list. Hal ini memampukan template kelas list untuk mendukung iterator bidrectional (dua-arah) sehingga kontainer dapat dijelalahi dengan arah maju dan arah mundur. Setiap algoritma yang memerlukan iterator input, iterator output, atau iterator bidirectional dapat beroperasi pada sebuah list. Tersedia banyak fungsi anggota list yang dapat memanipulasi elemen-elemen kontainer sebagai himpunan elemen terurut.

Template kelas list juga menyediakan sembilan fungsi anggota, yaitu splice, push_front, pop_front, remove, remove_if, unique, merge, reverse, dan sort. Beberapa dari fungsi anggota ini diimplementasikan dengan teroptimasi-list. Gambar 12.17 mendemonstrasikan beberap fitur kelas list. Ingat bahwa beberapa fungsi yang disajikan pada Gambar 12.14 - 12.15 dapat dipakai dengan kelas list. Header <list> harus dicantumkan untuk mengunakan kelas list.

Gambar 12.17 Menguji Template Kelas list STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102

// Gambar 12.17: gambar12_17.cpp // Menguji template kelas list STL. #include <iostream> #include <list> // definisi template kelas list #include <algorithm> // algoritma copy #include <iterator> // ostream_iterator using namespace std; // prototipe untuk fungsi tampilList template < typename T > void tampilList( const list< T > &listRef ); int main() {   const int UKURAN = 4;   int array[ UKURAN ] = { 2, 6, 4, 8 };   list< int > nilai2; // menciptakan list yang memuat nilai-nilai int   list< int > nilai2Lain; // menciptakan list yang memuat nilai-nilai int   // menyisipkan beberapa item ke dalam nilai2   nilai2.push_front( 1 );   nilai2.push_front( 2 );   nilai2.push_back( 4 );   nilai2.push_back( 3 );   cout << "nilai2 memuat: ";   tampilList( nilai2 );   nilai2.sort(); // mengurutkan nilai2   cout << "\nnilai2 setelah pengurutan memuat: ";   tampilList( nilai2 );   // menyisipkan elemen-elemen array ke dalam nilai2Lain   nilai2Lain.insert( nilai2Lain.begin(), array, array + UKURAN );   cout << "\nSetelah penyisipan, nilai2Lain memuat: ";   tampilList( nilai2Lain );   // menghapus elemen-elemen nilai2Lain dan menyisipkannya di ujung nilai2   nilai2.splice( nilai2.end(), nilai2Lain );   cout << "\nSetelah splice, nilai2 memuat: ";   tampilList( nilai2 );   nilai2.sort(); // mengurutkan nilai2   cout << "\nSetelah pengurutan, nilai2 memuat: ";   tampilList( nilai2 );   // menyisipkan elemen-elemen array ke dalam nilai2Lian   nilai2Lain.insert( nilai2Lain.begin(), array, array + UKURAN );   nilai2Lain.sort();   cout << "\nSetelah penyisipan dan pengurutan, nilai2Lain memuat: ";   tampilList( nilai2Lain );   // menghapus elemen-elemen nilai2Lain dan menyisipkan ke nilai2 dengan terurut   nilai2.merge( nilai2Lain );   cout << "\nSetelah merge:\n nilai2 memuat: ";   tampilList( nilai2 );   cout << "\n nilai2Lain memuat: ";   tampilList( nilai2Lain );   nilai2.pop_front(); // menghapus elemen dari depan   nilai2.pop_back(); // menghapus elemen dari belakang   cout << "\nSetelah pop_front dan pop_back:\n nilai2 memuat: ";   tampilList( nilai2 );   nilai2.unique(); // menghapus elemen duplikat   cout << "\nSetelah unique, nilai2 memuat: ";   tampilList( nilai2 );   // menukar elemen-elemen nilai2 dan nilai2Lain   nilai2.swap( nilai2Lain );   cout << "\nSetelah swap:\n nilai2 memuat: ";   tampilList( nilai2 );   cout << "\n nilai2Lain memuat: ";   tampilList( nilai2Lain );   // menggantikan isi nilai2 dengan elemen-elemen nilai2Lain   nilai2.assign( nilai2Lain.begin(), nilai2Lain.end() );   cout << "\nSetelah assign, nilai2 memuat: ";   tampilList( nilai2 );   // menghapus elemen-elemen nilai2Lain dan menyisipkannya ke nilai2 dengan terurut   nilai2.merge( nilai2Lain );   cout << "\nSetelah merge, nilai2 memuat: ";   tampilList( nilai2 );   nilai2.remove( 4 ); // menhapus keempat isi nilai2   cout << "\nSetelah remove( 4 ), nilai2 memuat: ";   tampilList( nilai2 );   cout << endl; } // akhir dari main // definisi template fungsi tampilList; menggunakan // ostream_iterator dan algoritma copy untuk menampilkan elemen-elemen list template < typename T > void tampilList( const list< T > &listRef ) {   if ( listRef.empty() ) // list kosong     cout << "List kosong";   else   {     ostream_iterator< T > output( cout, " " );     copy( listRef.begin(), listRef.end(), output );   } // akhir dari else } // akhir dari fungsi tampilList

nilai2 memuat: 2 1 4 3

nila2 setelah pengurutan memuat: 1 2 3 4

Setelah penyisipan, nilai2Lain memuat: 2 6 4 8

Setelah splice, nilai2 memuat: 1 2 3 4 2 6 4 8

Setelah penyisipan dan pengurutan, nilai2Lain memuat: 2 4 6 8

Seteleh merge:

   nilai2 memuat: 1 2 2 2 3 4 4 4 6 6 8 8

   nilai2Lain memuat: List kosong

Setelah pop_front dan pop_back:

nilai2 memuat: 2 2 2 3 4 4 4 6 6 8

Setelah unique, nilai2 memuat: 2 3 4 6 8

Setelah swap:

  nilai2 memuat: List kosong

  nilai2Lain memuat: 2 3 4 6 8

Setelah assign, nilai2 memuat: 2 3 4 6 8

Setelah merge, nilai2 memuat: 2 2 3 3 4 4 6 6 8 8

Setelah remove(4), nilai2 memuat: 2 2 3 3 6 6 8 8

Baris 16-17 menginstansiasi dua objek list yang mampu menyimpan integer-integer. Baris 20-21 menggunakan fungsi push_front untuk menyisipkan integer pada awal nilai2. Fungsi push_front spesifik untuk kelas list dan deque (bukan untuk vector). Baris 22-23 menggunakan fungsi push_back untuk menyisipkan integer-integer di akhir nilai2. Ingat bahwa fungsi push_back tersedia untuk semua kontainer runtun.

Baris 28 menggunakan fungsi anggota list, sort, untuk menata elemen-elemen di dalam list dalam urutan menaik. Versi kedua dari fungsi sort mengijinkan Anda untuk menyuplai sebuah fungsi predikat biner yang mengambil dua argumen (nilai-nilai di dalam list), melakukan perbandingan dan menghasilkan nilai balik bool untuk mengindikasikan hasil. Fungsi ini menentukan urutan dari elemen-elemen di dalam list.

Baris 38 menggunakan fungsi anggota list, splice, untuk menghapus elemen-elemen di dalam nilai2Lain dan menyisipkannya sebelum posisi iterator yang dispesifikasi sebagai argumen pertama. Ada dua versi dari fungsi ini. Fungsi splice dengan tiga argumen membolehkan satu elemen dihapus dari kontainer yang dispesifikasi sebagai argumen kedua dari lokasi yang dispesifikasi oleh iterator pada argumen ketiga. Fungsi splice dengan empat argumen menggunakan dua argumen terakhir untuk menentukan suatu rentang lokasi yang harus dihapus dari kontainer dalam argumen kedua dan menempatkannya di argumen pertama.

Setelah penyisipan elemen-elemen lain di dalam nilai2Lain dan pengurutan nilai2 dan nilai2Lain, baris 53 menggunakan fungsi anggota list, merge, untuk menghapus semua elemen nilai2Lain dan menyisipkannya dalam tatanan terurut ke dalam nilai2. Kedua list harus diurutkan sebelum operasi ini dilakukan. Versi kedua dari merge memampukan Anda untuk menyuplai sebuah fungsi predikat yang mengambil dua argumen (nilai-nilai di dalam list) dan menghasilkan nilai balik bool. Fungsi predikat tersebut menentukan tatanan pengurutan yang dipakai oleh merge.

Baris 59 menggunakan fungsi anggota list, pop_front, untuk menghapus elemen pertama di dalam list. Baris 60 menggunakan fungsi pop_back (tersedia bagi semua kontainer runtun) untuk menghapus elemen terakhir di dalam list.

Baris 64 menggunakan fungsi anggota list, unique, untuk menghapus elemen-elemen duplikat di dalam list. list harus dalam tatanan terurut (sehingga semua duplikat berada berdampingan) sebelum operasi ini dilakukan, untuk menjamin semua duplikat tereliminasi. Versi kedua dari unique memampukan Anda untuk menyuplai sebuah fungsi predikat yang mengambil dua argumen (nilai-nilai di dalam list) dan menghasilkan nilai balik bool, yang menspesifikasi apakah kedua elemen sama atau tidak.

Baris 69 menggunakan fungsi swap (tersedia bagi semua kontainer kelas-pertama) untuk menukar elemen-elemen nilai2 dengan elemen-elemen nilai2Lain.

Baris 76 menggunakan fungsi anggota list, assign, (yang tersedia bagi semua kontainer runtun) untuk menggantikan isi nilai2 dengan isi nilai2Lain dalam rentang yang dispesifikasi oleh dua argumen iterator. Versi kedua dari assign mengganti isi asli dengan salinan dari nilai yang dispesifikasi dalam argumen kedua. Argumen pertama dari fungsi itu menspesifikasi jumlah salinan. Baris 58 menggunakan fungsi anggota list, remove, untuk menghapus semua salinan nilai 4 dari list.

12.5.3 Kontainer Runtun deque

Kelas deque menyediakan keuntungan dari vector dan list dalam satu kontainer. Istilah deque berasal dari singkatan “double-ended queue” atau “antrian ujung-ganda”. Kelas deque diimplementasikan untuk menyediakan akses berindeks secara efisien (menggunakan subskript) dalam membaca dan memodifikasi elemen-elemennya. Kelas deque juga diimplementasikan untuk operasi penyisipan dan penghapusan secara efisien di ujung depan dan di ujung belakang.  Kelas deque menyediakan dukungan untuk iterator random access, sehingga deque dapat dipakai dengan semua algoritma STL.

Memori tambahan untuk deque dapat dialokasikan di salah satu ujung deque. Karena tata letak memori yang tidak bertetangga dari sebuah deque, iterator deque harus lebih cerdas dari pointer yang digunakan untuk mengiterasi menjelajahi vector.

Kelas deque menyediakan operasi-operasi dasar yang sama dengan kelas vector, tetapi sama seperti list yang memiliki fungsi anggota push_front dan push_back untuk membolehkan penyisipan dan penghapusan di awal deque.

Gambar 12.18 mendemonstrasikan beberapa fitur kelas deque. Ingat bahwa banyak fungsi yang disajikan pada Gambar 12.14, Gambar 12.15, dan Gambar 12.17 juga dapat dipakai menggunakan kelas deque.

Baris 11 menginstansiasi sebuah deque yang dapat menyimpan nilai-nilai double. Baris 15-17 menggunakan fungsi push_front dan push_back untuk menyisipkan elemen-elemen di ujung awal dan ujung akhir deque.

Gambar 12.18 Program Menguji Kelas deque STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

// Gambar 12.18: gambar12_18.cpp // Program menguji kelas deque STL. #include <iostream> #include <deque> // definisi template-kelas deque #include <algorithm> // algoritma copy #include <iterator> // ostream_iterator using namespace std; int main() {   deque< double > nilai2; // menciptakan deque yang memuat double   ostream_iterator< double > output( cout, " " );   // menyisipkan elemen-elemen di nilai2   nilai2.push_front( 2.2 );   nilai2.push_front( 3.5 );   nilai2.push_back( 1.1 );   cout << "nilai2 memuat: ";   // menggunakan operator subskript untuk mendapatkan elemen-elemen nilai2   for ( unsigned int i = 0; i < nilai2.size() ;++i )     cout << nilai2[ i ] << ' ';   nilai2.pop_front(); // menghapus elemen pertama   cout << "\nSetelah pop_front, nilai2 memuat: ";   copy( nilai2.begin(), nilai2.end(), output );   // menggunakan operator subskript untuk memodifikasi elemen pada lokasi 1   nilai2[ 1 ] = 5.4;   cout << "\nSetelah nilai2[ 1 ] = 5.4, nilai2 memuat: ";   copy( nilai2.begin(), nilai2.end(), output );   cout << endl; } // akhir dari main

nilai2 memuat: 3.5 2.2 1.1

Setelah pop_front, nilai2 memuat: 2.2 1.1

Setelah nilai2[1], nilai2 memuat: 2.2 5.4

Ingat bahwa push_back tersedia bagi semua kontainer runtun, tetapi push_front hanya tersedia bagi kelas list dan deque.

Statemen for pada baris 22-23 menggunakan operator subskript untuk mengambil nilai setiap elemen deque untuk ditampilkan. Kondisi menggunakan fungsi size untuk memastikan bahwa Anda tidak mencoba untuk mengakses elemen di luar rentang deque.

Baris 25 menggunakan fungsi pop_front untuk mendemonstrasikan penghapusan elemen pertama deque. Ingat bahwa pop_front hanya tersedia bagi kelas list dan deque (tidak bagi kelas vector).

Baris 30 menggunakan operator subskript untuk menciptakan sebuah lvalue. Ini memampukan nilai-nilai ditugaskan secara langsung ke sembarang elemen deque.

12.6 Kontainer Asosiatif

Kontainer asosiatif STL menyediakan akses langsung dalam menyimpan mengambil elemen melalui kunci (seringkali disebut juga dengan kunci pencarian).  Ada empat kontainer asosiatif, yaitu multiset, set, multimap, dan map. Setiap kontainer asosiatif mempunyai kunci dalam tatanan terurut. Kelas multiset dan set menyediakan beberapa operasi untuk memanipulasi sehimpunan nilai dimana nilai-nilai tersebut merupakan kuncinya. Perbedaan utama antara multiset dan set adalah bahwa multiset membolehkan adanya kunci duplikat sedangkan set tidak mengijinkan adanya kunci duplikat.

Kelas multimap dan map menyediakan beberapa operasi untuk memanipulasi nilai yang berkaitan dengan kunci. Perbedaan utama antara multimap dan map adalah bahwa multimap mengijinkan adanya kunci duplikat dengan nilai berkaitan yang akan disimpan dan map tidak mengijinkannya. Selain fungsi anggota untuk semua kontainer yang disajikan pada Gambar 12.2, semua kontainer asosiatif juga mendukung beberapa fungsi anggota lain, termasuk find, lower_bound, upper_bound, dan count.

12.6.1 Kontainer Asosiatif multiset

Kontainer asosiatif multiset menyediakan mekanisme penyimpanan dan penarikan kunci secara cepat dan membolehkan adanya kunci duplikat. Pengurutan elemen ditentukan oleh sebuah objek fungsi komparator. Sebagai contoh, di dalam sebuah multiset integer, elemen-elemen dapat diurutkan secara menaik dengan mengurutkan kunci menggunakan objek fungsi komparator less<int>. Tipe data kunci semua kontainer asosiatif harus mendukung perbandingan berbasis objek fungsi komparator yang dispesifikasi, yaitu less<T> harus mendukung perbandirngan dengan operator<. Jika kunci yang digunakan di dalam kontainer asosiatif adalah tipe data yang didefinisikan oleh pengguna, maka tipe tersebut harus menyuplai operator perbandingan yang sesuai. Sebuah multiset mendukung iterator bidirectional (tetapi tidak mendukung iterator random access).

Gambar 12.19 mendemonstrasikan kontainer asosiatif multiset untuk sebuah multiset yang memuat integer-integer terurut secara menaik. Header <set> harus dicantumkan untuk menggunakan kelas multiset. Kontainer multiset dan set menyediakan fungsionalitas dasar yang sama.

Baris 10 menggunakan typedef untuk menciptakan nama alias bagi sebuah multiset yang memuat integer-integer terurut secara menaik, menggunakan objek fungsi less<int>. Urutan menaik adalah kondisi default untuk multiset, jadi less<int> dapat diabaikan pada baris 10. Tipe baru ini (Ims) kemudian digunakan untuk menginstansiasi objek multiset integer, intMultiset, pada baris 16.

Gambar 12.19 Menguji Template Kelas multiset STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

// Gambar 12.19: gambar12_19.cpp // Menguji template kelas multiset STL #include <iostream> #include <set> // definisi template-kelas multiset #include <algorithm> // algoritma copy #include <iterator> // ostream_iterator using namespace std; // mendefinisikan nama alias untuk tipe multiset typedef multiset< int, less< int > > Ims; int main() {   const int UKURAN = 10;   int a[ UKURAN ] = { 7, 22, 9, 1, 18, 30, 100, 22, 85, 13 };   Ims intMultiset; // Ims adalah typedef untuk "multiset integer"   ostream_iterator< int > output( cout, " " );   cout << "Sekarang terdapat " <<  intMultiset.count( 15 )     << " buah nilai 15 di dalam multiset\n";   intMultiset.insert( 15 ); // menyisipkan 15 di dalam intMultiset   intMultiset.insert( 15 ); // menyisipkan 15 di dalam intMultiset   cout << "Setelah insert, terdapat " << intMultiset.count( 15 )     << " buah nilai 15 di dalam multiset\n\n";   // iterator yang tidak bisa dipakai untuk mengubah nilai elemen   Ims::const_iterator hasil;   // mencari 15 di dalam intMultiset; find menghasilkan iterator   hasil = intMultiset.find( 15 );   if ( hasil != intMultiset.end() ) // jika iterator tidak di ujung     cout << "Ditemukan nilai 15\n"; // nilai 15 ditemukan   // mencari 20 di dalam intMultiset; find menghasilkan iterator   hasil = intMultiset.find( 20 );   if ( hasil == intMultiset.end() )     cout << "Nilai 20 tidak ditemukan\n"; // nilai 20 tidak ditemukan   // menyisipkan elemen array ke intMultiset   intMultiset.insert( a, a + UKURAN );   cout << "\nSetelah insert, intMultiset memuat:\n";   copy( intMultiset.begin(), intMultiset.end(), output );   // menentukan batas bawah dan batas atas 22 di dalam intMultiset   cout << "\n\nBatas bawah dari 22: "     << *( intMultiset.lower_bound( 22 ) );   cout << "\nBatas atas dari 22: " << *( intMultiset.upper_bound( 22 ) );   // p merepresentasikan sepasang const_iterator   pair< Ims::const_iterator, Ims::const_iterator > p;   // menggunakan equal_range untuk menentukan batas atas dan batas bawah   // dari 22 di dalam intMultiset   p = intMultiset.equal_range( 22 );   cout << "\n\nequal_range dari 22:" << "\n Batas bawah: "     << *( p.first ) << "\n Batas atas: " << *( p.second );   cout << endl; } // akhir dari main

Sekarang terdapat 0 buah nilai 15 di dalam multiset

Setelah insert, terdapat 2 buah nilai 15 di dalam multiset

Ditemukan nilai 15

Nilai 20 tidak ditemukan

Setelah insert, intMultiset memuat:

1 7 9 13 15 15 18 22 22 30 85 100

Batas bawah dari 22: 22

Batas atas dari 22: 30

equal_range dari 22:

   Batas bawah: 22

   Batas atas: 30

Statemen keluaran pada baris 19 menggunakan fungsi count (tersedia bagi semua kontainer asosiatif) untuk menghitung jumlah kemunculan nilai 15 yang saat ini berada di dalam multiset. Baris 22-23 menggunakan salah satu dari tiga versi fungsi insert untuk menambahkan nilai 15 ke dalam multiset dua kali. Versi kedua dari insert mengambil sebuah iterator dan sebuah nilai sebagai argumen dan memulai pencarian titik penyisipan dari posisi iterator yang dispesifikasi. Versi ketiga dari insert mengambil dua iterator sebagai argumen yang menspesfikasi rentang nilai yang ditambahkan ke dalam multiset dari kontainer lain.

Baris 31 menggunakan fungsi find (tersedia bagi semua kontainer asosiatif) untuk mencari lokasi nilai 15 di dalam multiset. Fungsi find menghasilkan sebuah iterator atau sebuah const_iterator yang menunjuk ke lokasi nilai yang dicari. Jika nilai yang dicari tidak ditemukan, find menghasilkan iterator atau const_iterator yang sama dengan nilai yang dijadikan nilai balik oleh pemanggilan fungsi end. Baris 40 mendemonstasikan hal itu.

Baris 43 menggunakan fungsi insert untuk menyisipkan elemen array ke dalam multiset. Pada baris 45, algoritma copy menyalin elemen-elemen multiset ke keluaran standard dalam urutan menaik.

Baris 49 dan 50 menggunakan fungsi lower_bound dan upper_bound (tersedia bagi semua kontainer asosiatif) untuk mencari lokasi kemunculan pertama dari nilai 22 di dalam multiset dan lokasi elemen setelah kemunculan terakhir dari nilai 22 di dalam multiset. Kedua fungsi ini menghasilkan nilai balik berupa iterator atau const_iterator yang menunjuk ke lokasi tertentu atau berupa iterator yang dijadikan nilai balik oleh fungsi end jika nilai yang dicari tidak ditemukan di dalam multiset.

Baris 53 menciptakan sebuah objek pair, yang dinamakan p. Objek semacam itu memuat pasangan-pasangan nilai. Pada contoh ini, isi sebuah pair adalah dua const_iterator untuk multiset integer. Tujuan adanya p adalah untuk menyimpan nilai balik dari fungsi equal_range yang menghasilkan sebuah pair yang memuat hasil dari operasi lower_bound dan upper_bound.

Baris 57 menggunakan fungsi equal_range untuk menentukan lower_bound dan upper_bound dari nilai 22 di dalam multiset. Baris 60 menggunakan p.first dan p.second untuk mengakses lower_bound dan upper_bound. Kedua iterator tersebut kemudian didereferensi untuk menampilkan nilai-nilai pada lokasi-lokasi yang dihasilkan dari equal_range.

12.6.2 Kontainer Asosiatif set

Kontainer asosiatif set digunakan untuk penyimpanan dan penarikan kunci-kunci unik. Implementasi atas sebuah set identik dengan implementasi atas sebuah multiset, kecuali bahwa sebuah set harus memiliki kunci-kunci unik. Oleh karena itu, jika suatu percobaan untuk menyisipkan kunci duplikat ke dalam sebuah set dilakukan, maka kunci duplikat tersebut diabaikan. Sebuah set mendukung iterator bidirectional (tetapi tidak mendukung iterator random access). Gambar 12.20 mendemonstrasikan sebuah set yang memuat nilai-nilai double. Header <set> harus disertakan untuk menggunakan kelas set.

Gambar 12.20 Menguji Template Kelas set STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

// Gambar 12.20: gambar12_20.cpp // Program menguji set STL. #include <iostream> #include <set> #include <algorithm> #include <iterator> // ostream_iterator using namespace std; // mendefinisikan nama alias untuk set typedef set< double, less< double > > DoubleSet; int main() {   const int UKURAN = 5;   double a[ UKURAN ] = { 2.1, 4.2, 9.5, 2.1, 3.7 };   DoubleSet doubleSet( a, a + UKURAN );   ostream_iterator< double > output( cout, " " );   cout << "doubleSet memuat: ";   copy( doubleSet.begin(), doubleSet.end(), output );     // p merepresentasikan pair memuat const_iterator dan bool   pair< DoubleSet::const_iterator, bool > p;   // menyisipkan 13.8 ke dalam doubleSet; penyisipan menghasilkan pair   // dimana p.first merepresentasikan lokasi dari 13.8 di dalam doubleSet dan   // p.second merepresentasikan apakah 13.8 telah disisipkan atau belum   p = doubleSet.insert( 13.8 );   cout << "\n\n" << *( p.first )     << ( p.second ? " telah" : " tidak" ) << " disisipkan";   cout << "\ndoubleSet memuat: ";   copy( doubleSet.begin(), doubleSet.end(), output );     // menyisipkan 9.5 ke dalam doubleSet   p = doubleSet.insert( 9.5 ); // nilai telah berada di dalam set   cout << "\n\n" << *( p.first )     << ( p.second ? " telah" : " tidak" ) << " disisipkan";   cout << "\ndoubleSet memuat: ";   copy( doubleSet.begin(), doubleSet.end(), output );   cout << endl; } // akhir dari main

doubleSet memuat: 2.1 3.7 4.2 9.5

13.8 telah disisipkan

doubleSet memuat: 2.1 3.7 4.2 9.5 13.8

19.5 tidak disisipkan

doubleSet memuat: 2.1 3.7 4.2 9.5 13.8

Baris 10 menggunakan typedef untuk menciptakan nama alias (DoubleSet) untuk sehimpunan nilai double yang tersusun secara menaik, menggunakan objek fungsi less<double>.

Baris 16 menggunakan DoubleSet untuk menginstansiasi objek doubleSet. Pemanggilan konstruktor mengambil elemen-elemen di dalam array a di antara a dan a + SIZE (keseluruhan array) dan menyisipkannya ke dalam set. Baris 20 menggunakan algoritma copy untuk menampilkan isi set. Perhatikan bahwa nilai 2.1, yang muncul dua kali di dalam array a, hanya muncul sekali saja di dalam doubleSet. Hal ini karena kontainer set yang tidak mengijinkan duplikasi.

Baris 23 mendefinisikan sebuah pair yang memuat const_iterator untuk DoubleSet dan sebuah nilai double. Objek ini menyimpan hasil dari pemanggilan fungsi insert. Baris 28 menggunakan fungsi insert untuk menempatkan nilai 13.8 di dalam set. Nilai balik pair dari fungsi insert, p, memuat sebuah iterator p.first yang menunjuk ke nilai 13.8 di dalam set dan sebuah iterator p.second yang menunjuk ke nilai bool yang bernilai true jika nilai telah disisipkan dan false jika nilai tidak disisipkan (karena sudah ada di dalam set). Keluaran dari baris 36-37 menunjukkan bahwa 9.5 tidak disisipkan, karena sudah ada sebelumnya di dalam set.

12.6.3 Kontainer Asosiatif multimap

Kontainer asosiatif multimap digunakan untuk penyimpanan dan penarikan kunci dan nilai terkait (sering disebut dengan pasangan kunci/nilai). Banyak fungsi yang digunakan dengan multiset dan set dapat pula dipakai dengan multimap dan map. Elemen-elemen multimap dan map adalah pasangan-pasangan kunci dan nilai, bukan nilai saja. Ketika menyisipkan ke dalam multimap atau map, sebuah objek pair yang memuat kunci dan nilai digunakan. Pengurutan kunci ditentukan oleh sebuah objek fungsi komparator. Sebagai contoh, di dalam multimap yang menggunakan integer sebagai tipe kunci, kunci-kunci dapat disimpan dalam urutan menaik dengan mengurutkannya menggunakan objek fungsi komparator less<int>. Kunci duplikat diijinkan di dalam multimap, jadi banyak nilai bisa diasosiasikan dengan sebuah kunci. Hal ini dikenal dengan relasi satu-ke-banyak. Sebagai contoh, di dalam sistem pemrosesan traksaksi kartu kredit, satu akun kartu kredit dapat memiliki banyak transaksi; di universitas, seorang mahasiswa dapat mengambil banyak matakuliah, dan seorang guru besar dapat mengajar banyak mahasiswa. Sebuah multimap mendukung iterator bidirectional, tetapi tidak mendukung iterator random access. Gambar 12.21 mendemonstrasikan kontainer asosiatif. Header <map> harus dicantumkan untuk menggunakan kelas multimap.

Baris 8 menggunakan typedef untuk mendefinisikan alias Mmid untuk suatu tipe multimap dimana di dalamnya tipe kunci adalah integer, tipe nilai yang terasosiasi dengan kunci adalah double dan elemen-elemen diurutkan dengan tatanan menaik. Baris 12 menggunakan Mmid untuk menginstansiasi sebuah multimap, yang dinamakan sepasang. Baris 14 menggunakan fungsi count untuk menentukan jumlah pasangan kunci/nilai dengan sebuah kunci 15.

Gambar 12.21 Menguji Template Kelas multimap STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

// Gambar 12.21: gambar21_21.cpp // Program untuk menguji kelas multimap STL. #include <iostream> #include <map> // definisi template kelas multimap using namespace std; // mendefinisikan nama alias untuk tipe multimap typedef multimap< int, double, less< int > > Mmid; int main() {   Mmid sepasang; // mendeklarasikan pasangan multimap   cout << "Sekarang terdapat " << sepasang.count( 15 )     << " buah pasangan dengan kunci 15 di dalam multimap\n";   // menyisipkan dua objek value_type objects di dalam sepasang   sepasang.insert( Mmid::value_type( 15, 2.7 ) );   sepasang.insert( Mmid::value_type( 15, 99.3 ) );   cout << "Setelah insert, terdapat " << sepasang.count( 15 )     << " buah pasangan dengan kunci 15\n\n";   // menyisipkan lima objek value_type di dalam sepasang   sepasang.insert( Mmid::value_type( 30, 111.11 ) );   sepasang.insert( Mmid::value_type( 10, 22.22 ) );   sepasang.insert( Mmid::value_type( 25, 33.333 ) );   sepasang.insert( Mmid::value_type( 20, 9.345 ) );   sepasang.insert( Mmid::value_type( 5, 77.54 ) );   cout << "Multimap sepasang memuat:\nKunsi\tNilai\n";   // menggunakan const_iterator untuk menjelajahi elemen-elemen sepasang   for ( Mmid::const_iterator iter = sepasang.begin();     iter != sepasang.end(); ++iter )   cout << iter->first << '\t' << iter->second << '\n';   cout << endl; } // akhir dari main

Sekarang terdapat 0 buah pasangan dengan kunci 15 di dalam multimap

Setelah insert, terdapat 2 buah pasangan dengan kunci 15

Multimap sepasang memuat:

5       77.54

10      22.22

15      2.7

15      99.3

20      9.345

25      33.333

30      111.11

Baris 18 menggunakan fungsi insert untuk menambahkan sepasang kunci/nilai baru ke dalam multimap. Ekspresi Mmid::value_type (15, 2.7) menciptakan sebuah objek sepasang dimana di dalamnya first adalah kunci (15) bertipe int dan second adalah nilai (2.7) bertipe double. Tipe Mmid::value_type didefinisikan sebagai bagian dari typedef untuk multimap. Baris 19 menyisipkan objek sepasang lainnya dengan kunci 15 dan nilai 99.3. Statemen for pada baris 34-36 menampilkan isi multimap, termasuk kunci dan nilai. Baris 36 menggunakan const_iterator, dinamakan iter, untuk mengakses anggota-anggota dari sepasang di setiap elemen multimap. Perhatikan bahwa keluaran menunjukkan kunci-kunci dalam tatanan terurut menaik.

12.6.4 Kontainer Asosiatif map

Kontainer asosiatif map melakukan operasi penyimpanan dan penarikan kunci unik dan nilai terkait. Kunci duplikat tidak diijinkan, jadi sebuah nilai hanya bisa diasosiasikan dengan sebuah kunci. Ini dikenal dengan relasi satu-ke-satu. Sebagai contoh, sebuah perusahaan menggunakan nomor pegawai, seperti 101, 203, dan 309, yang memiliki sebuah map yang mengasosiasikannya dengan ekstensi telepon sebagai kunci, seperti 3421, 5435, dan 8273. Dengan map, Anda menspesifikasi dapat kunci dan memperoleh data (nilai) dengan cepat. Sebuah map juga dikenal dengan array asosiatif. Penyediaan kunci di dalam operator subskript [ ] pada sebuah map dapat mencari lokasi nilai yang diasosiasikan dengan nilai di dalam map. Penyisipan dan penghapusan dapat dilakukan di sembarang tempat di dalam map.

Gambar 12.22 mendemonstrasikan sebuah map dan menggunakan beberapa fitur yang sama pada Gambar 12.21 untuk mendemonstrasikan operator subskript. Header <map> harus dicantumkan untuk menggunakan kelas map. Baris 31-32 menggunakan operator subskript dari kelas map. Ketika subskript merupakan sebuah kunci yang sebelumnya telah ada di dalam map (baris 31), operator menghasilkan sebuah referensi ke nilai terasosiasi. Ketika subskript merupakan sebuah kunci yang belum ada di dalam map (baris 32), operator menyisipkan kunci tersebut di dalam map dan menghasilkan nilai balik berupa sebuah referensi yang dapat dipakai untuk mengasosiasikan sebuah nilai dengan kunci tersebut. Baris 31 mengganti nilai untuk kunci 35 (sebelumnya 33.333 seperti yang dispesifikasikan pada baris 19) dengan sebuah nilai baru, 9999.99. Baris 32 menyisipkan sepasang kunci/nilai baru di dalam map (yang disebut dengan penciptaan sebuah asosiasi).

Gambar 12.22 Menguji Template Kelas map STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

// Gambar 12.22: gambar12_22.cpp // Program menguji map STL. #include <iostream> #include <map> // definisi template kelas map using namespace std; // mendefinisikan nama alias untuk tipe map typedef map< int, double, less< int > > Mid; int main() {   Mid sepasang;   // menyisipkan delapan objek value_type di dalam sepasang   sepasang.insert( Mid::value_type( 15, 2.7 ) );   sepasang.insert( Mid::value_type( 30, 111.11 ) );   sepasang.insert( Mid::value_type( 5, 1010.1 ) );   sepasang.insert( Mid::value_type( 10, 22.22 ) );   sepasang.insert( Mid::value_type( 25, 33.333 ) );   sepasang.insert( Mid::value_type( 5, 77.54 ) ); // diabaikan   sepasang.insert( Mid::value_type( 20, 9.345 ) );   sepasang.insert( Mid::value_type( 15, 99.3 ) ); // diabaikan   cout << "sepasang memuat:\nKunci\tNilai\n";   // menggunakan const_iterator untuk menjelajahi elemen-elemen sepasang   for ( Mid::const_iterator iter = sepasang.begin();     iter != sepasang.end(); ++iter )   cout << iter->first << '\t' << iter->second << '\n';   sepasang[ 25 ] = 9999.99; // menggunakan subskript untuk mengubah nilai kunci 25   sepasang[ 40 ] = 8765.43; // menggunakan subskript untuk mengubah nilai kunci 40   cout << "\nSetelah operasi subskript, sepasang memuat:\nKunci\tNilai\n";   // menggunakan const_iterator untuk menjelajahi elemen-elemen sepasang   for ( Mid::const_iterator iter2 = sepasang.begin();     iter2 != sepasang.end(); ++iter2 )   cout << iter2->first << '\t' << iter2->second << '\n';  cout << endl;  } // end main

sepasang memuat:

5       1010.1

10      22.22

15      2.7

20      9.345

25      33.333

30      111.11

Setelah operasi subskript, sepasang memuat:

5       1010.1

10      22.22

15      2.7

20      9.345

25      9999.99

12.7 Adapter Kontainer

STL menyediakan tiga adapter kontainer, yaitu stack, queue, dan prioriy_queue. Adapter bukan kontainer kelas-pertama, karena ia tidak menyediakan implementasi struktur data aktual dimana di dalamnya elemen-elemen dapat disimpan dan karena adapter tidak mendukung iterator. Keuntungan dari kelas adapter adalah bahwa Anda dapat memilih struktur data yang cocok untuk aplikasi Anda. Ketiga kelas adapter menyediakan fungsi anggota push dan pop yang menyisipkan sebuah elemen ke dalam setiap struktur data adapter dan menghapus sebuah elemen dari setiap struktur data adapter.

12.7.1 Adapter stack

Kelas stack memampukan penyisipan ke dalam dan penghapusan dari  ujung struktur data (yang sering dikenal dengan struktur data last-in, first-out). Sebuah stack dapat diimplementasikan dengan sembarang kontainer runtun: vector, list, dan deque. Contoh ini menciptakan tiga tumpukan integer, menggunakan ketiga kontainer runtun STL sebagai struktur data untuk merepresentasikan stack. Secara default, stack diimplementasikan dengan deque. Beberapa operasi stack adalah push untuk menyisipkan sebuah elemen teratas stack (diimplementasikan dengan pemanggilan fungsi push_back), pop untuk menghapus elemen teratas stack, top untuk mendapatkan sebuah referensi ke elemen teratas stack (diimplementasikan dengan pemanggilan fungsi back), empty untuk menentukan apakah stack kosong atau tidak (diimplementasikan dengan pemanggilan fungsi empty), dan size untuk mendapatkan jumlah elemen di dalam stack (diimplementasikan dengan pemanggilan fungsi size).

Gambar 12.23 mendemonstrasikan kelas adapter stack. Header <stack> harus dicantumkan untuk memakai kelas stack. Baris 18, 21, dan 24 menginstansiasi tiga tumpukan integer. Baris 18 menspesifikasi sebuah stack integer yang menggunakan kontainer deque default sebagai struktur data. Baris 21 menspesifikasi sebuah stack integer yang menggunakan vector integer sebagai struktur data. Baris 24 menspesifikasi sebuah stack integer yang menggunakan list integer sebagai struktur data.

Fungsi pushElemen (baris 46-53) mendorong elemen ke atas setiap stack. Baris 50 menggunakan fungsi push (tersedia bagi setiap kelas adapter) untuk menempatkan sebuah integer di atas stack. Baris 51 menggunakan fungsi top untuk menarik elemen teratas stack untuk ditampilkan. Fungsi top tidak membuang elemen teratas stack.

Fungsi popElemen (baris 56-63) membuang elemen dari setiap stack. Baris 60 menggunakan fungsi top untuk menarik elemen teratas stack untuk ditampilkan. Baris 61 menggunakan fungsi pop (tersedia bagi setiap kelas adapter) untuk menghapus elemen teratas stack. Fungsi pop tidak menghasilkan nilai balik apapun.

Gambar 12.23 Menguji Adapter stack STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

// Gambar 12.23: gambar12_23.cpp // Program menguji adapter stack STL. #include <iostream> #include <stack> // definisi adapter stack #include <vector> // definisi template kelas vector #include <list> // definisi template kelas list using namespace std; // prototipe template-fungsi pushElemen template< typename T > void pushElemen( T &stackRef ); // prototipe template-fungsi popElements template< typename T > void popElemen( T &stackRef ); int main() {   // stack dengan deque default   stack< int > intDequeStack;   // stack dengan struktur-data vector   stack< int, vector< int > > intVectorStack;   // stack dengan struktur data list   stack< int, list< int > > intListStack;   // mendorong nilai 0-9 ke atas tiap stack   cout << "Mendorong ke atas intDequeStack: ";   pushElemen( intDequeStack );   cout << "\nMendorong ke atas  intVectorStack: ";   pushElemen( intVectorStack );   cout << "\nMendorong ke atas  intListStack: ";   pushElemen( intListStack );   cout << endl << endl;   // menampilkan dan menghapus elemen dari setiap stack   cout << "Menghapus dari intDequeStack: ";   popElemen( intDequeStack );   cout << "\nMenghapus dari intVectorStack: ";   popElemen( intVectorStack );   cout << "\nMenghapus dari intListStack: ";   popElemen( intListStack );   cout << endl; } // akhir dari main // mendorong elem ke atas objek stack yang ditunjuk oleh stackRef template< typename T > void pushElemen( T &stackRef ) {   for ( int i = 0; i < 10; ++i )   {     stackRef.push( i ); // mendorang elemen ke atas stack     cout << stackRef.top() << ' '; // menampilkan elemen teratas   } // akhir dari for } // akhir dari fungsi pushElemen // menghapus elemen dari objek stack yang ditunjuk oleh stackRef template< typename T > void popElemen( T &stackRef ) {   while( !stackRef.empty() )   {     cout << stackRef.top() << ' '; // menampilkan elemen teratas     stackRef.pop(); // menghapus elemen teratas   } // akhir dari while } // akhir dari fungsi popElemen

Mendorong ke atas intVectorStack: 0 1 2 3 4 5 6 7 8 9

Mendorong ke atas intListStack: 0 1 2 3 4 5 6 7 8 9

Menghapus dari intDequeStack: 9 8 7 6 5 4 3 2 1 0

Menghapus dari intVectorStack: 9 8 7 6 5 4 3 2 1 0

Menghapus dari intListStack: 9 8 7 6 5 4 3 2 1 0

12.7.2 Adapter queue

Kelas queue memampukan penyisipan di belakang struktur data dan penghapusan dari depan struktur data (yang sering dikenal dengan struktur data first-in, first-out). Sebuah queue dapat diimplementasikan dengan list atau deque. Secara default, sebuah queue diimplementasikan dengan deque. Beberapa operasi umum queue adalah push untuk menyisipkan sebuah elemen di belakang queue (diimplementasikan dengan pemanggilan fungsi push_back), pop untuk menghapus elemen di depan queue (diimplementasikan dengan pemanggilan fungsi pop_front), front untuk mendapatkan sebuah referensi ke elemen pertama di dalam queue (diimplementasikan dengan pemanggilan fungsi front), back untuk memperoleh sebuah referensi ke elemen terakhir di dalam queue (diimplementasikan dengan pemanggilan fungsi back), empty untuk menentukan apakah queue kosong atau tidak (diimplementasikan dengan pemanggilan fungsi empty), dan size untuk mendapatkan jumlah elemen di dalam queue (diimplementasikan dengan pemanggilan fungsi size).

Gambar 12.24 mendemonstrasikan kelas adapter queue. Header <queue> harus dicantumkan untuk menggunakan sebuah queue. Baris 9 menginstansiasi sebuah queue yang menyimpan nilai-nilai double. Baris 12-14 menggunakan fungsi push untuk menambahkan elemen ke dalam queue. Statemen while pada baris 19-23 menggunakan fungsi empty (tersedia untuk semua kontainer) untuk menentukan apakah queue kosong atau tidak (baris 19). Jika masih ada elemen di dalam queue, baris 21 menggunakan fungsi front untuk membaca (tetapi tidak menghapus) elemen pertama di dalam queue untuk ditampilkan. Baris 22 menghapus elemen pertama di dalam queue menggunakan fungsi pop (tersedia di dalam semua kelas adapter).

Gambar 12.24 Menguji Adapter queue STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// Gambar 12.24: gambar12_24.cpp // Program menguji adapter queue STL. #include <iostream> #include <queue> // definisi adapter queue using namespace std; int main() {   queue< double > nilai2; // queue berisi nilai-nilai double   // mendorong elemen ke atas queue   nilai2.push( 3.2 );   nilai2.push( 9.8 );   nilai2.push( 5.4 );   cout << "Menghapus dari nilai2: ";   // menghapus elemen dari queue   while(!nilai2.empty())   {     cout << nilai2.front() << ' '; // menampilkan elemen depan     nilai2.pop(); // menghapus elemen   } // akhir dari while   cout << endl; } // akhir main

Menghapus dari nilai2: 3.2 9.8 5.4

12.7.3 Adapter priority_queue

Kelas priority_queue menyediakan fungsionalitas yang memampukan penyisipan dalam tatanan terurut ke dalam struktur data dan penghapusan dari depan struktur data. Sebuah priority_queue dapat diimplementasikan dengan kontainer runtun STL vector atau deque. Secara default, priority_queue diimplementasikan dengan vector. Ketika elemen-elemen ditambahkan ke priority_queue, elemen-elemen tersebut disisipkan dalam urutan prioritas, sehingga elemen dengan prioritas tertinggi akan dihapus pertama kali dari priority-queue. Hal ini dilakukan dengan menata elemen-elemen dalam suatu struktur pohon biner yang disebut dengan heap, dimana nilai terbesar (elemen dengan prioritas tertinggi) berada di depan struktur data. Perbandingan elemen dilakukan dengan objek fungsi komparator less<T> secara deault, tetapi Anda bisa menyuplai komparator yang berbeda.

Terdapat beberapa operasi yang umum pada priority_queue. Operasi push menyisipkan sebuah elemen ke suatu lokasi tertentu berdasarkan urutan prioritas dari priority_queue (diimplementasikan oleh pemanggilan fungsi push_back, kemudian mengurutkan-ulang elemen-elemen menggunakan heap). Operasi pop menghapus elemen dengan prioritas tertinggi (diimplementasikan dengan pemanggilan fungsi pop_back setelah menghapus elemen teratas heap). Operasi top memperoleh sebuah referensi ke elemen teratas priority_queue (diimplementasikan dengan pemanggilan fungsi front). Operasi empty menentukan apakah priority_queue kosong atau tidak (diimplementasikan dengan pemanggilan fungsi empty). Operasi size mendapatkan jumlah elemen di dalam priority_queue (diimplementasikan dengan pemanggilan fungsi size).

Gambar 12.25 mendemonstrasikan kelas adapter priorty_queue. Header <queue> harus dicantumkan untuk menggunakan priority_queue. Baris 9 menginstansiasi sebuah priority_queue yang menyimpan nilai-nilai double dan menggunakan sebuah vector sebagai struktur data. Baris 12-14 menggunakan fungsi push untuk menambahkan elemen ke dalam priority_queue. Statemen while pada baris 19-23 menggunakan fungsi empty (tersedia bagi semua kontainer) untuk menentukan apakah priority_queue kosong atau tidak (baris 19). Ketika masih ada elemen, baris 21 menggunakan fungsi top untuk menarik elemen dengan prioritas tertinggi di dalam priority_queue agar ditampilkan. Baris 22 menghapus elemen dengan prioritas tertinggi di dalam priority_queue dengan fungsi pop (tersedia bagi semua kelas adapter).

Gambar 12.25 Menguji Adapter priority_queue STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

// Gambar 12.25: gambar12_25.cpp // Standard Library adapter priority_queue test program. #include <iostream> #include <queue> // definisi adapter priority_queue using namespace std; int main() {   priority_queue< double > prioritas; // menciptakan priority_queue   // mendorong elemen ke atas prioritas   prioritas.push( 3.2 );   prioritas.push( 9.8 );   prioritas.push( 5.4 );   cout << "Menghapus dari prioritas: ";   // menghapus elemen dari priority_queue   while(!prioritas.empty())   {     cout << prioritas.top() << ' '; // menampilkan elemen teratas     prioritas.pop(); // menghapus elemen teratas   } // akhir dari while   cout << endl; } // akhir main

Menghapus dari prioritas: 9.8 5.4 3.2

12.8 Algoritma

Sebelum adanya STL, pustaka kelas kontainer dan algoritma saling tidak kompatibel di antara vendor. Pustaka kontainer, pada awal pembentukannya, menggunakan pewarisan dan polimorfisme untuk membangun algoritma ke dalam kelas kontainer. STL memisahkan algoritma dari kontainer. Hal ini membuat penambahan algoritma baru menjadi lebih mudah. Dengan STL, elemen kontainer dapat diakses melalui iterator.

12.8.1 fill, fill_n, generate, dan generate_n

Gambar 12.26 mendemonstrasikan algoritma fill, fill_n, generate, dan generate_n. Fungi fill dan fill_n menetapkan sebuah nilai spesifik terhadap elemen-elemen di dalam suatu rentang elemen kontainer. Fungei generate dan generate_n menggunakan suatu fungsi pembangkit dalam menciptakan nilai-nilai untuk setiap elemen di dalam suatu rentang elemen kontainer. Fungsi pembangkit tidak memerlukan argumen apapun dan menghasilkan nilai balik berupa suatu nilai yang dapat ditempatkan di dalam sebuah elemen kontainer.

Gambar 12.26 Algoritma fill, fill_n, generate, dan generate_n

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

// Gambar 21.26: gambar21_26.cpp // Algoritma fill, fill_n, generate dan generate_n dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // ostream_iterator using namespace std; char nextHuruf(); // prototipe fungsi pembangkit int main() {   vector< char > karakter( 10 );   ostream_iterator< char > output( cout, " " );   fill( karakter.begin(), karakter.end(), '5' ); // mengisi karakter dengan 5    cout << "Vektor karakter setelah diisi dengan 5:\n";    copy( karakter.begin(), karakter.end(), output );    // mengisi lima elemen pertama karakter dengan A    fill_n( karakter.begin(), 5, 'A' );    cout << "\n\nVektor karakter setelah diisi lima elemen pertama dengan A:\n";    copy( karakter.begin(), karakter.end(), output );   // membangkitkan nilai-nilai untuk semua elemen karakter dengan nextHuruf   generate( karakter.begin(), karakter.end(), nextHuruf );   cout << "\n\nVektor karakter setelah pembangkitan huruf A-J:\n";   copy( karakter.begin(), karakter.end(), output );   // membangkitkan nilai-nilai untuk lima elemen pertama karakter dengan nextHuruf   generate_n( karakter.begin(), 5, nextHuruf );   cout << "\n\nVektor karakter setelah pembangkitan K-O untuk"     << " lima elemen pertama:\n";    copy( karakter.begin(), karakter.end(), output );    cout << endl; } // akhir dari main // fungsi pembangkit menghasilkan huruf berikutnya (mulai dari A) char nextHuruf() {   static char huruf = 'A';   return ++huruf; } // akhir dari fungsi nextHuruf

Vektor karakter setelah diisi dengan 5:

5 5 5 5 5 5 5 5 5 5

Vektor karakter setelah diisi lima elemen pertama dengan A:

A A A A A 5 5 5 5 5

Vektor karakter setelah pembangkitan huruf A-J:

A B C D E F G H I J

Vektor karakter setelah pembangkitan K-O untuk lima elemen pertama:

K L M N O F G H I J

Baris 13 mendefinisikan 10 elemen vector yang menyimpan nilai-nilai char. Baris 15 menggunakan fungsi fill untuk menempatkan karakter ‘5’ di semua elemen vector, karakter, mulai dari karakter.begin() sampai ke karakter.end(). Iterator yang disuplai sebagai argumen pertama dan argumen kedua harus setidaknya berupa iterator forward (yang dapat digunakan untuk masukan dari kontainer dan mengeluarkan ke sebuah kontainer dalam arah maju).

Baris 21 menggunakan fungsi fill_n untuk menempatkan karakter ‘A’ di dalam lima elemen pertama vector,  karakter. Iterator yang disuplai sebagai argumen pertama harus setidaknya berupa iterator output (yang dapat digunakan untuk mengeluarkan ke sebuah kontainer dalam arah maju). Argumen kedua menspesifikasi jumlah elemen yang akan diisi. Argumen ketiga menspesifikasi nilai yang akan ditempatkan di setiap elemen.

Baris 27 menggunakan fungsi generate untuk menempatkan hasil dari pemanggilan fungsi pembangkit nextHuruf di setiap elemen vector karakter mulai dari karakter.begin() sampai ke karakter.end().Iterator yang disuplai sebagai argumen pertama dan argumen kedua harus setidaknya berupa iterator forward. Fungsi nextHuruf (baris 42-46) membangkitkan karakter mulai dari ‘A’ yang disimpan di dalam sebuah variabel lokal static. Statemen pada baris 45 melakukan postinkremen terhadap nilai huruf dan memberikan nilai balik berupa nilai lama dari huruf setiap kali nextHuruf dipanggil.

Baris 33 menggunakan fungsi generate_n untuk menempatkan hasil dari pemanggilan fungsi pembangkit nextHuruf di dalam lima elemen vector karakter, mulai dari karakter.begin(). Iterator yang disuplai sebagai argumen pertama harus setidaknya berupa iterator output.

12.8.2 equal, mismatch, dan lexicographical_compare

Gambar 12.27 mendemonstrasikan perbandingan ekualitas atas runtun-runtun nilai menggunakan  algoritma equals, mismatch, dan lexicographical_compare.

Gambar 12.27 Algoritma equal, mismatch, dan lexicographical_compare

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53

// Gambar 12.27: gambar12_27.cpp // Algoritma equal, mismatch dan lexicographical_compare di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // ostream_iterator using namespace std; int main() {   const int UKURAN = 10;   int a1[ UKURAN ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };   int a2[ UKURAN ] = { 1, 2, 3, 4, 1000, 6, 7, 8, 9, 10 };   vector< int > v1( a1, a1 + UKURAN ); // salinan dari a1   vector< int > v2( a1, a1 + UKURAN ); // salinan dari a1   vector< int > v3( a2, a2 + UKURAN ); // salinan dari a2   ostream_iterator< int > output( cout, " " );   cout << "Vektor v1 memuat: ";   copy( v1.begin(), v1.end(), output );   cout << "\nVektor v2 memuat: ";   copy( v2.begin(), v2.end(), output );   cout << "\nVektor v3 memuat: ";   copy( v3.begin(), v3.end(), output );   // membandingkan vektor v1 dan v2 untuk ekualitas   bool hasil = equal( v1.begin(), v1.end(), v2.begin() );   cout << "\n\nVektor v1 " << ( hasil ? "sama" : "tidak sama" )     << " dengan vektor v2.\n";   // membandingkan vektor v1 dan v3 untuk ekualitas   hasil = equal( v1.begin(), v1.end(), v3.begin() );   cout << "Vektor v1 " << ( hasil ? "sama" : "tidak sama" )    << " dengan vektor v3.\n";   // lokasi merepresentasikan sepasang iterator vector   pair< vector< int >::iterator, vector< int >::iterator > lokasi;   // memeriksa ketidakcocokan antara v1 dan v3   lokasi = mismatch( v1.begin(), v1.end(), v3.begin() );   cout << "\nTerdapat ketidakcocokan antara v1 dan v3 pada lokasi "     <<( lokasi.first - v1.begin() )<< "\ndimana v1 memuat "     << *lokasi.first << " dan v3 memuat " << *lokasi.second     << "\n\n";   char c1[ UKURAN ] = "SELAMAT";   char c2[ UKURAN ] = "JALAN";   // melakukan perbandingan leksikografikal atas c1 dan c2   hasil = lexicographical_compare( c1, c1 + UKURAN, c2, c2 + UKURAN );   cout << c1 << ( hasil ? " kurang dari " :     " lebih dari atau sama dengan " ) << c2 << endl;  } // akhir dari main

Vektor v1 memuat: 1 2 3 4 5 6 7 8 9 10

Vektor v2 memuat: 1 2 3 4 5 6 7 8 9 10

Vektor v3 memuat: 1 2 3 4 1000 6 7 8 9 10

Vektor v1 sama dengan vektor v2.

Vektor v1 tidak sama dengan vektor v3.

Terdapat ketidakcocokan antara v1 dan v3 pada lokasi 4

dimana v1 memuat 5 dan v3 memuat 1000

SELAMAT lebih dari atau sama dengan JALAN

Baris 27 menggunakan fungsi equal untuk membandingkan dua runtun nilai untuk ekualitas. Setiap runtun tidak perlu memuat jumlah elemen yang sama. Fungsi ini menghasilkan false jika runtun tidak sama panjang. Operator == melakukan perbandingan elemen. Pada contoh ini, elemen-elemen di dalam vector v1 mulai dari v1.begin() sampai v1.end() dibandingkan dengan elemen-elemen di dalam vector v2 mulai dari v2.begin() sampai v2.end(). Pada contoh ini, v1 dan v2 sama. Tiga argumen iterator harus sedikitnya berupa iterator input (yang dapat digunakan untuk masukan dari sebuah runtun dengan arah maju). Baris 32 menggunakan fungsi equal untuk membandingkan vector v1 dan vector v3, yang tidak sama.

Ada versi lain dari fungsi equal yang mengambil sebuah fungsi predikat biner sebagai prameter keempat. Fungsi predikat biner menerima dua elemen yang sedang dibandingkan dan menghasilkan nilai balik bool yang mengindikasikan apakah kedua elemen sama atau tidak. Hal ini berguna di dalam runtun untuk menyimpan objek-objek atau pointer-pointer yang menunjuk ke nilai, karena Anda dapat mendefinisikan satu atau lebih perbandingan. Sebagai contoh, Anda dapat membandingkan objek-objek Pegawai untuk perbandingan usia, nomor KTP, atau alamat. Anda dapat membandingkan apa yang ditunjuk oleh pointer, bukan membandingkan nilai-nilai pointer (alamat yang disimpan di dalam pointer).

Baris 37-40 dimulai dengan menginstansiasi sebuah objek pair yang dinamakan lokasi untuk vector yang memuat integer-integer. Objek ini menyimpan hasil dari pemanggilan mismatch (baris 40). Fungsi mismatch membandingkan dua runtun nilai dan menghasilkan nilai balik berupa objek pair yang mengindikasikan lokasi di dalam setiap runtun yang memuat elemen-elemen tak-cocok. Jika semua elemen cocok, dua iterator di dalam pair sama dengan iterator terakhir untuk tiap runtun. Tiga argumen iterator sedikitnya harus berupa iterator input. Baris 42 menentukan lokasi aktual dari ketidakcocokan di dalam vector dengan ekspresi lokasi.first - v1.begin(). Hasil dari kalkulasi ini adalah jumlah elemen di antara dua iterator.

Baris 50 menggunakan fungsi lexicographical_compare untuk membandingkan isi dari dua array karakter. Empat argumen iterator pada fungsi ini harus sedikitnya berupa iterator input. Seperti yang Anda ketahui, pointer ke array adalah iterator random access. Dua argumen iterator pertama menspesifikasi rentang lokasi di dalam runtun pertama. Dua argumen iterator terakhir menentukan rentang lokasi di dalam runtun kedua. Ketika beriterasi menjelajahi runtun, lexicographical_compare memeriksa apakah elemen di dalam runtun pertama kurang dari elemen terkait di dalam runtun kedua. Jika ya, fungsi ini menghasilkan true. Jika elemen di dalam runtun pertama lebih dari atau sama dengan elemen terkait di dalam runtun kedua, maka fungsi ini menghasilkan false. Fungsi ini dapat digunakan untuk menata runtun secara leksikografikal.

12.8.3 remove, remove_if, remove_copy dan remove_copy_if

Gambar 12.28 mendemonstrasikan penghapusan nilai dari sebuah runtun menggunakan algoritma remove, remove_if, remove_copy, dan remove_copy_if.

Gambar 12.28 Algoritma remove, remove_if, remove_copy, dan remove_copy_if

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

// Gambar 12.28: gambar12_28.cpp // Fungsi remove, remove_if, // remove_copy dan remove_copy_if di dalam STL #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // ostream_iterator using namespace std; bool lebihDari9( int ); // prototipe int main() {   const int UKURAN = 10;   int a[ UKURAN ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 };   ostream_iterator< int > output( cout, " " );   vector< int > v( a, a + UKURAN ); // salinan dari a   vector< int >::iterator newElemenTerakhir;   cout << "Vektor v sebelum dihapus semua 10:\n ";   copy( v.begin(), v.end(), output );   // menghapus semua 10 daro v   newElemenTerakhir = remove( v.begin(), v.end(), 10 );   cout << "\nVektor v setelah dihapus semua 10:\n ";   copy( v.begin(), newElemenTerakhir, output );   vector< int > v2( a, a + UKURAN ); // salinan dari a   vector< int > c( UKURAN, 0 ); // menginstansiasi vektor c   cout << "\n\nVektor v2 sebelum dihapus dan disalin semua 10s:\n ";   copy( v2.begin(), v2.end(), output );   // menyalin dari v2 ke c, menghapus semua 10   remove_copy( v2.begin(), v2.end(), c.begin(), 10 );   cout << "\nVektor c setelah dihapus semua 10 dari v2:\n ";   copy( c.begin(), c.end(), output );   vector< int > v3( a, a + UKURAN ); // copy of a   cout << "\n\nVektor v3 sebalum dihapus semua elemen"     << "\nyang lebih dari 9:\n ";   copy( v3.begin(), v3.end(), output );   // menghapus elemen yang lebih dari 9 dari v3   newElemenTerakhir = remove_if( v3.begin(), v3.end(), lebihDari9 );   cout << "\nVektor v3 setelah dihapus semua elemen"     << "\nyang lebih dari 9:\n ";   copy( v3.begin(), newElemenTerakhir, output );      vector< int > v4( a, a + UKURAN ); // salinan dari a   vector< int > c2( UKURAN, 0 ); // menginstansiasi vektor c2   cout << "\n\nVektor v4 sebelum disalin dan dihapus semua elemen"    << "\nyang lebih dari 9:\n ";   copy( v4.begin(), v4.end(), output );   // menyalin elemen dari v4 ke c2, menghapus semua elemen yang lebih dari   // 9 di dalam prosesnya   remove_copy_if( v4.begin(), v4.end(), c2.begin(), lebihDari9 );   cout << "\nVektor c2 setelah dihapus semua elemen"     << "\nyang lebih dari 9 dari v4:\n ";   copy( c2.begin(), c2.end(), output );   cout << endl; } // akhir dari main // menentukan apakah argumen lebih dari 9 atau tidak bool lebihDari9( int x ) {   return x > 9; } // akhir dari fungsi lebihDari9

Vektor v sebelum dihapus semua 10:

  10 2 10 4 16 6 14 8 12 10

Vektor v setelah dihapus semua 10:

  2 4 16 6 14 8 12

Vektor v2 sebelum dihapus dan disalin semua 10:

  10 2 10 4 16 6 14 8 12 10

Vektor c setelah semua 10 dihapus dari v2:

   2 4 16 6 14 8 12 0 0 0

Vektor v3 sebelum dihapus semua elemen

yang lebih dari 9:

   10 2 10 4 16 6 14 8 12 10

Vektor v3 setelah dihapus semua elemen

yang lebih dari 9:

   2 4 6 8

Vektor v4 sebelum disalin dan dihapus semua elemen

yang lebih dari 9:

   10 2 10 4 16 6 14 8 12 10

Vektor c2 setelah dihapus semua elemen

yang lebih dari 9 dari v4:

   2 4 6 8 0 0 0 0 0 0

Baris 24 menggunakan fungsi remove untuk mengeliminasi semua elemen dengan nilai 10 di dalam rentang dari v.begin() sampai v.end(). Dua argumen iterator pertama harus berupa iterator forward sehingga algoritma ini dapat memodifikasi elemen di dalam runtun. Fungsi ini tidak memodifikasi jumlah elemen di dalam vector atau menghancurkan semua elemen tereliminasi, tetapi hanya memindahkan semua elemen yang tidak dieliminasi ke awal vector. Fungsi ini menghasilkan nilai balik berupa suatu iterator yang diposisikan satu elemen setelah elemen vector yang tidak tereliminasi. Elemen-elemen mulai dari posisi iterator sampai ke akhir vector memiliki nilai tak-terdefinisi (pada contoh ini, setiap posisi “tak-terdefinisi” memiliki nilai 0).

Baris 34 menggunakan fungsi remove_copy untuk menyalin semua elemen yang tidak memiliki nilai 10 di dalam rentang mulai dari v2.begin() sampai v2.end(). Elemen-elemen tersebut kemudian ditempatkan di dalam c, mulai dari posisi c.begin(). Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator input. Iterator yang disuplai sebagai argumen ketiga harus berupa sebuah iterator output sehingga semua elemen yang sedang disalin dapat disisipkan ke dalam lokasi penyalinan. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan satu elemen setelah elemen terakhir yang disalin ke dalam vector c. Perhatikan pada baris 29 penggunaan konstruktor vector dan nilai-nilai awal untuk elemen-elemen tersebut.

Baris 44 menggunakan fungsi remove_if untuk menghapus semua elemen di dalam rentang mulai dari v3.begin() sampai v3.end() bila fungsi predikat (yang didefinisikan oleh pengguna) bernilai true. Fungsi lebihDari9 (didefinisikan pada baris 65-68) menghasilkan true jika nilai yang dilewatkan kepadanya bernilai lebih dari 9; sebaliknya, menghasilkan false. Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator forward sehingga algoritma ini dapat memodifikasi elemen-elemen di dalam runtun. Fungsi ini tidak memodifikasi jumlah elemen di dalam vector, tetapi ia hanya memindahkan semua elemen yang tidak tereliminasi ke awal vector. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan satu elemen setelah elemen terakhir di dalam vector yang tidak dihapus. Semua elemen mulai dari posisi iterator sampai ke akhir vector memiliki nilai tak-terdefinisi.

Baris 57 menggunakan fungsi remove_copy_if untuk menyalin semua elemen di dalam rentang mulai dari v4.begin() sampai v4.end() bila fungsi predikat (lebihDari9) bernilai true. Elemen-elemen yang ditempatkan di dalam c2 mulai dari posisi c2.begin(). Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator input. Iterator yang disuplai sebagai argumen ketiga harus berupa iterator output sehingga elemen yang sedang disalin dapat disisipkan ke lokasi penyalinan. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan satu elemen setelah elemen terakhir yang disalin ke dalam c2.

12.8.4 replace, replace_if, replace_copy dan replace_copy_if

Gambar 12.29 mendemonstrasikan penggantian nilai-nilai dari sebuah runtun menggunakan algoritma replace, replace_if, replace_copy, dan replace_copy_if.

Gambar 12.29 Algoritma replace, replace _if, replace _copy, dan replace _copy_if

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

// Gambar 12.29: gambar12_29.cpp // Fungsi replace, replace_if, // replace_copy dan replace_copy_if di dalam STL. #include <iostream> #include <algorithm> #include <vector> #include <iterator> // ostream_iterator using namespace std; bool lebihDari9( int ); // prototipe fungsi predikat int main() {   const int SIZE = 10;   int a[ SIZE ] = { 10, 2, 10, 4, 16, 6, 14, 8, 12, 10 };   ostream_iterator< int > output( cout, " " );   vector< int > v1( a, a + SIZE ); // salinan dari a   cout << "Vektor v1 sebelum diganti semua 10:\n ";   copy( v1.begin(), v1.end(), output );   // mengganti semua 10 di dalam v1 dengan 100   replace( v1.begin(), v1.end(), 10, 100 );   cout << "\nVektor v1 setelah diganti semua 10 dengan 100:\n ";   copy( v1.begin(), v1.end(), output );   vector< int > v2( a, a + SIZE ); // copy of a   vector< int > c1( SIZE ); // instantiate vector c1   cout << "\n\nVektor v2 sebelum diganti dan disalin semua 10:\n ";   copy( v2.begin(), v2.end(), output );   // menyalin dari v2 ke v1, mengganti 10 dengan 100   replace_copy( v2.begin(), v2.end(), c1.begin(), 10, 100 );   cout << "\nVektor c1 setelah diganti semua 10 di dalam v2:\n ";   copy( c1.begin(), c1.end(), output );   vector< int > v3( a, a + SIZE ); // copy of a   cout << "\n\nVektor v3 sebelum diganti nilai yang lebih dari 9:\n ";   copy( v3.begin(), v3.end(), output );   // mengganti semua nilai yang lebih dari 9 di dalam v3 dengan 100   replace_if( v3.begin(), v3.end(), lebihDari9, 100 );   cout << "\nVektor v3 setelah diganti semua elemen"     << "\nyang lebih dari 9 dengan 100:\n ";   copy( v3.begin(), v3.end(), output );   vector< int > v4( a, a + SIZE ); // salinan dari a   vector< int > c2( SIZE ); // menginstansiasi vektor c2   cout << "\n\nVektor v4 sebelum diganti dan disalin semua elemen "     << "yang lebih dari 9:\n ";   copy( v4.begin(), v4.end(), output );   // menyalin v4 ke c2, mengganti elemen-elemen yang lebih dari 9 dengan 100   replace_copy_if( v4.begin(), v4.end(), c2.begin(), lebihDari9, 100 );   cout << "\nVektor c2 setelah diganti semua elemen "     << "yang lebih dari 9 di dalam v4:\n ";   copy( c2.begin(), c2.end(), output );   cout << endl; } // akhir dari main // menentukan apakah argumen lebih dari 9 atau tidak bool lebihDari9( int x ) {   return x > 9; } // akhir dari fungsi lebihDari9

Vektor v1 sebelum diganti semua 10:

   10 2 10 4 16 6 14 8 12 10

Vektor v1 setelah diganti semua 10 dengan 100:

   100 2 100 4 16 6 14 8 12 100

Vektor v2 sebelum diganti dan disalin semua 10:

   10 2 10 4 16 6 14 8 12 10

Vektor c1 setelah diganti semua 10 di dalam v2:

   100 2 100 4 16 6 14 8 12 100

Vektor v3 sebelum diganti nilai yang lebih dari 9:

   10 2 10 4 16 6 14 8 12 10

Vektor v3 setelah diganti semua elemen

yang lebih dari 9 dengan 100:

   100 2 100 4 16 6 14 8 12 100

Vektor v4 sebelum diganti dan disalin semua elemen yang lebih dari 9:

   10 2 10 4 16 6 14 8 12 10

Vektor c2 setelah diganti semua elemen yang lebih dari 9 di dalam v4:

   100 2 100 4 16 6 14 8 12 100

Baris 23 menggunakan fungsi replace untuk mengganti semua elemen dengan nilai 10 di dalam rentang dari v1.begin() sampai v1.end(). Dua argumen iterator pertama harus berupa iterator forward sehingga algoritma ini dapat memodifikasi elemen di dalam runtun.

Baris 33 menggunakan fungsi replace_copy untuk menyalin semua elemen yang tidak memiliki nilai 10 di dalam rentang mulai dari v2.begin() sampai v2.end(), mengganti semua elemen bernilai 10 dengan nilai baru 100. Elemen-elemen tersebut kemudian ditempatkan di dalam c1, mulai dari posisi c1.begin(). Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator input. Iterator yang disuplai sebagai argumen ketiga harus berupa sebuah iterator output sehingga semua elemen yang sedang disalin dapat disisipkan ke dalam lokasi penyalinan. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan satu elemen setelah elemen terakhir yang disalin ke dalam vector c1.

Baris 42 menggunakan fungsi replace_if untuk menghapus semua elemen di dalam rentang mulai dari v3.begin() sampai v3.end() bila fungsi predikat (yang didefinisikan oleh pengguna) bernilai true. Fungsi lebihDari9 (didefinisikan pada baris 62-65) menghasilkan true jika nilai yang dilewatkan kepadanya bernilai lebih dari 9; sebaliknya, menghasilkan false. Nilai 100 menggantikan setiap nilai yang lebih dari 9. Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator forward sehingga algoritma ini dapat memodifikasi elemen-elemen di dalam runtun.

Baris 54 menggunakan fungsi replace_copy_if untuk menyalin semua elemen di dalam rentang mulai dari v4.begin() sampai v4.end() bila fungsi predikat (lebihDari9) bernilai true. Jika fungsi predikat bernilai true (elemen bernilai lebih dari 9), maka setiap nilai yang lebih dari 9 akan digantikan dengan nilai baru 100. Elemen-elemen yang ditempatkan di dalam c2 mulai dari posisi c2.begin(). Iterator yang disuplai sebagai dua argumen pertama harus berupa iterator input. Iterator yang disuplai sebagai argumen ketiga harus berupa iterator output sehingga elemen yang sedang disalin dapat disisipkan ke lokasi penyalinan. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan satu elemen setelah elemen terakhir yang disalin ke dalam c2.

12.8.5 Algoritma Matematik

Gambar 12.30 mendemonstrasikan beberapa algoritma matematik di dalam STL, termasuk random_shuffle, count, count_if, min_element, max_element, accumulate, for_each, dan transform.

Gambar 12.30 Beberapa Algoritma Matematik di dalam STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82

// Gambar 12.30: gambar12_30.cpp // Beberapa algoritma matematik di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <numeric> // accumulate didefinisikan di sini #include <vector> #include <iterator> using namespace std; bool lebihDari9( int ); // prototipe fungsi predikat void tampilKuadrat( int ); // menampilkan kuadrat atas suatu nilai int hitungKubik( int ); // menghitung kubik atas suatu nilai int main() {   const int UKURAN = 10;   int a1[ UKURAN ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };   vector< int > v( a1, a1 + UKURAN ); // salinan dari a1   ostream_iterator< int > output( cout, " " );   cout << "Vektor v sebelum random_shuffle: ";   copy( v.begin(), v.end(), output );   random_shuffle( v.begin(), v.end() ); // mengacak elemen-elemen di dalam v   cout << "\nVektor v setelah random_shuffle: ";   copy( v.begin(), v.end(), output );   int a2[ UKURAN ] = { 100, 2, 8, 1, 50, 3, 8, 8, 9, 10 };   vector< int > v2( a2, a2 + UKURAN ); // copy of a2   cout << "\n\nVektor v2 memuat: ";   copy( v2.begin(), v2.end(), output );   // menghitung jumlah elemen di dalam v2 yang bernilai 8   int hasil = count( v2.begin(), v2.end(), 8 );   cout << "\nJumlah elemen yang cocok dengan 8: " << hasil;   // menghitung jumlah elemen di dalam v2 yang bernilai lebih dari 9   hasil = count_if( v2.begin(), v2.end(), lebihDari9 );   cout << "\nJumlah elemen yang bernilai lebih dari 9: " << hasil;   // mencari lokasi elemen minimum di dalam v2   cout << "\n\nElemen minimum di dalam vektor v2 adalah: "     << *( min_element( v2.begin(), v2.end() ) );   // mencari lokasi elemen maksimum di dalam v2   cout << "\nElemen maksimum di dalam vektor v2 adalah: "     << *( max_element( v2.begin(), v2.end() ) );   // menghitung jumlah dari elemen-elemen di dalam v   cout << "\n\nTotal elemen di dalam vektor v adalah: "     << accumulate( v.begin(), v.end(), 0 );   // menampilkan kuadrat atas setiap elemen di dalam v   cout << "\n\nKuadrat atas setiap integer di dalam vektor v adalah:\n";   for_each( v.begin(), v.end(), tampilKuadrat );   vector< int > kubik( UKURAN ); // menginstansiasi vektor kubik   // menghitung kubik atas setiap elemen di dalam v; menempatkan hasilnya di dalam kubik   transform( v.begin(), v.end(), kubik.begin(), hitungKubik );   cout << "\n\nKubik atas setiap integer di dalam vektor v adalah:\n";   copy( kubik.begin(), kubik.end(), output );   cout << endl; } // akhir dari main // menentukan apakah argumen lebih dari 9 atau tidak bool lebihDari9( int nilai ) {   return nilai > 9; } // akhir dari fungsi lebihDari9 // menampilkan kuadrat atas argumen void tampilKuadrat( int nilai ) {   cout << nilai * nilai << ' '; } // akhir dari fungsi tampilKuadrat // menghasilkan kubik atas argumen int hitungKubik( int nilai ) {   return nilai * nilai * nilai; } // akhir dari fungsi hitungKubik

Vektor v sebelum random_shuffle: 1 2 3 4 5 6 7 8 9 10

Vektor v setelah random_shuffle: 5 4 1 3 7 8 9 10 6 2

Vektor v2 memuat: 100 2 8 1 50 3 8 8 9 10

Jumlah elemen yang cocok dengan 8: 3

Jumlah elemen yang bernilai lebih dari 9: 3

Elemen minimum di dalam vektor v2 adalah: 1

Elemen maksimum di dalam vektor v2 adalah: 100

Total elemen di dalam vektor v adalah: 55

Kuadrat atas setiap elemen di dalam vektor v adalah:

25 16 1 9 49 64 81 100 36 4

Kubik atas setiap elemen di dalam vektor v adalah:

125 64 1 27 343 512 729 1000 216 8

Baris 24 menggunakan fungsi random_shuffle untuk menata-ulang secara acak elemen-elemen di dalam rentang mulai dari v.begin() sampai v.end() di dalam v. Fungsi ini mengambil dua argumen iterator random access.

Baris 34 menggunakan fungsi count untuk menghitung elemen bernilai 8 di dalam rentang dari v2.begin() sampai v2.end() di dalam v2. Fungsi ini memerlukan dua agumen iterator yang sedikitnya berupa iterator input.

Baris 38 menggunakan fungsi count_if untuk menghitung elemen-elemen di dalam rentang dari v2.begin() sampai v2.end() di dalam v2 jika fungsi predikat lebihDari9 bernilai true. Fungsi ini memerlukan dua argumen iterator yang sedikitnya berupa iterator input.

Baris 43 menggunakan fungsi min_element untuk mencari lokasi elemen terkecil di dalam rentang dari v2.begin() sampai v2.end(). Fungsi ini menghasilkan nilai balik berupa sebuah iterator forward yang ditempatkan di elemen terkecil atau di v2.end() jika rentang kosong. Dua argumen iterator sedikitnya harus berupa iterator input. Versi kedua dari fungsi ini mengambil sebuah fungsi biner sebagai argumen ketiga yang membandingkan dua elemen di dalam runtun. Fungsi ini menghasilkan true jika argumen pertama kurang dari argumen kedua.

Baris 47 menggunakan fungsi max_element untuk mencari lokasi elemen terbesar di dalam rentang dari v2.begin() sampai v2.end(). Fungsi ini menghasilkan nilai balik berupa sebuah iterator input yang ditempatkan di elemen terbesar. Dua argumen iterator sedikitnya harus berupa iterator input. Versi kedua dari fungsi ini mengambil sebuah fungsi biner sebagai argumen ketiga yang membandingkan dua elemen di dalam runtun. Fungsi ini menghasilkan true jika argumen pertama kurang dari argumen kedua.

Baris 51 menggunakan fungsi accumulate (templatenya berada di dalam header <numeric>) untuk menjumlahkan nilai-nilai di dalam rentang mulai dari v.begin() sampai v.end() di dalam v. Dua argumen iterator sedikitnya harus berupa iterator input dan argumen ketiganya merepresentasikan nilai awal dari total. Versi kedua dari fungsi ini mengambil sebuah fungsi umum sebagai argumen keempat yang menentukan bagaimana elemen diakumulasikan. Fungsi umum itu mengambil dua argumen dan memberikan nilai balik hasil penjumlahan. Argumen pertama fungsi ini adalah nilai terkini dari akumulasi. Argumen keduanya adalah nilai elemen di dalam runtun yang akan diakumulasikan.

Baris 55 menggunakan fungsi for_each untuk menerapkan suatu fungsi umu terhadap setiap elemen di dalam rentang mulai dari v.begin() sampai v.end(). Fungsi umum itu mengambil elemen sekarang sebagai argumen dan memodifikasinya. Fungsi for_each memerlukan dua argumen iterator yang sedikitnya berupa iterator input.

Baris 60 menggunakan fungsi transform untuk menerapkan suatu fungsi umum terhadap setiap elemen di dalam rentang mulai dari v.begin() sampai v.end(). Fungsi umum itu mengambil elemen sekarang sebagai argumen, tidak memodifikasinya, dan mengembalikan nilai yang telah ditransformasi. Fungsi transform memerlukan dua argumennya sedikitnya berupa iterator input. Argumen ketiga fungsi ini menspesifikasi dimana nilai yang telah ditransformasi harus ditempatkan.

12.8.6 Algoritma Pencarian dan Pengurutan

Gambar 12.31 mendemonstrasikan beberapa kapabilitas pencarian dan pengurutan di dalam STL, termasuk find, find_if, sort dan binary_search.

Gambar 12.31 Beberapa Algoritma Pencarian dan Pengurutan di dalam STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

// Gambar 12.31: gambar12_31.cpp // Algoritma pencarian dan pengurutan STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> using namespace std; bool lebihDari10( int ); // prototipe fungsi predikat int main() {   const int UKURAN = 10;   int a[ UKURAN ] = { 10, 2, 17, 5, 16, 8, 13, 11, 20, 7 };   vector< int > v( a, a + UKURAN ); // salinan dari a   ostream_iterator< int > output( cout, " " );   cout << "Vektor v memuat: ";   copy( v.begin(), v.end(), output ); // menampilkan vector   // mencari lokasi kemunculan pertama dari 16 di dalam v   vector< int >::iterator lokasi;   lokasi = find( v.begin(), v.end(), 16 );   if ( lokasi != v.end() ) // ditemukan 16     cout << "\n\nDitemukan 16 pada lokasi " << ( lokasi - v.begin() );   else // 16 tidak ditemukan     cout << "\n\n16 tidak ditemukan";   // mencari lokasi kemunculan pertama dari 100 di dalam v   lokasi = find( v.begin(), v.end(), 100 );   if ( lokasi != v.end() ) // found 100     cout << "\nDitemukan 100 pada lokasi " << ( lokasi - v.begin() );   else // 100 tidak ditemukan     cout << "\n100 tidak ditemukan";   // mencari lokasi kemunculan pertama nilai yang lebih dari 10 di dalam v   lokasi = find_if( v.begin(), v.end(), lebihDari10 );   if ( lokasi != v.end() ) // ditemukan nilai lebih dari 10     cout << "\n\nNilai pertama yang lebih dari 10 adalah " << *lokasi       << "\nditemukan pada lokasi " << ( lokasi - v.begin() );   else // nilai yang lebih dari 10 tidak ditemukan     cout << "\n\n Tidak adal nilai yang lebih dari 10 ditemukan";   // mengurutkan elemen-elemen di dalam v   sort( v.begin(), v.end() );   cout << "\n\nVektor v setelah sort: ";   copy( v.begin(), v.end(), output );   // menggunakan binary_search untuk mencari lokasi 13 di dalam v   if(binary_search( v.begin(), v.end(), 13 ))     cout << "\n\n13 ditemukan di dalam v";   else     cout << "\n\n13 tidak ditemukan di dalam v";   // menggunakan binary_search untuk mencari lokasi 100 di dalam v   if(binary_search( v.begin(), v.end(), 100 ))     cout << "\n100 ditemukan di dalam v";   else     cout << "\n100 tidak ditemukan di dalam v";   cout << endl; } // end main // menentukan apakah argumen bernilai lebih dari 10 bool lebihDari10( int nilai ) {   return nilai > 10; } // akhir dari fungsi lebihDari10

Vektor v memuat: 10 2 17 5 16 8 13 11 20 7

Ditemukan 16 pada lokasi 4

100 tidak ditemukan

Nilai pertama yang lebih dari 10 adalah 17

ditemukan pada lokasi 2

Vektor v setelah sort: 2 5 7 8 10 11 13 16 17 20

13 ditemukan di dalam v

100 tidak ditemukan di dalam v

Baris 23 menggunakan fungsi find untuk mencari lokasi nilai 16 di dalam rentang mulai dari v.begin() sampai v.end(). Fungsi ini memerlukan dua argumen iterator yang sedikitnya harus berupa iterator input dan memberikan nilai balik berupa sebuah iterator input yang diposisikan pada  elemen pertama yang memuat nilai yang dicari atau elemen yang mengindikasikan akhir suatu runtun (seperti kasus pada baris 31).

Baris 39 menggunakan fungsi find_if untuk mencari lokasi nilai pertama di dalam rentang mulai dari v.begin() sampai v.end() dimana fungsi predikat lebihDari10 bernilai true. Fungsi lebihDari10 (didefinisikan pada baris 68-71) mengambil sebuah integer sebagai argumen dan menghasilkan sebuah nilai bool yang mengindikasikan apakah argumen integer tersebut bernilai lebih dari 10. Fungsi find_if mensyaratkan bahwa dua argumen iteratornya sedikitnya harus berupa iterator input. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan di elemen pertama yang memuat nilai dimana fungsi predikat bernilai true atau di elemen yang mengindikasikan akhir runtun.

Baris 48 menggunakan fungsi sort untuk menata elemen-elemen di dalam rentang mulai dari v.begin() sampai v.end() dengan urutan menaik. Fungsi ini mensyaratkan bahwa kedua argumen iteratornya harus berupa sedikitnya iterator random access. Versi kedua dari fungsi ini mengambil sebuah argumen ketiga, yang merupakan sebuah fungsi predikat biner yang memerlukan dua argumen (nilai di dalam runtun), dan menghasilkan nilai bool yang mengindikasikan hasil pengurutan. Jika nilai baliknya true, maka dua elemen yang sedang dibandingkan tertata secara terurut.

Baris 53 menggunakan fungsi binary_search untuk menentukan apakah nilai 13 berada di dalam rentang mulai dari v.begin() sampai v.end(). Runtun nilai harus sudah diurutkan secara menaik terlebih dahulu. Fungsi ini mensyaratkan bahwa kedua argumen iteratornya sedikitnya harus berupa iterator forward. Nilai baliknya adalah sebuah bool yang mengindikasikan apakah nilai yang dicari ditemukan di dalam runtun atau tidak. Baris 59 mendemonstrasikan pemanggilan terhadap fungsi binary_search dimana di dalamnya nilai yang dicari tidak ditemukan. Versi kedua dari fungsi ini mengambil argumen keempat, yang merupakan sebuah  fungsi predikat biner yang memerlukan dua argumen (nilai di dalam runtun), dan menghasilkan nilai bool yang mengindikasikan hasil pengurutan. Jika nilai baliknya true, maka dua elemen yang sedang dibandingkan tertata secara terurut. Untuk mendapatkan lokasi kunci pencarian di dalam kontainer, digunakan algoritma lower_bound atau find.

12.8.7 Algoritma swap, iter_swap, dan swap_ranges

Gambar 12.32 mendemonstrasikan algoritma swap, swap_iter, dan swap_ranges untuk menukar elemen. Baris 18 menggunakan fungsi swap untuk menukar dua elemen. Pada contoh ini, elemen pertama dan elemen kedua dari sebuah array a dipertukarkan. Fungsi ini mengambil referensi ke dua nilai yang sedang dipertukarkan sebagai argumen.

Gambar 12.32 Algoritma swap, iter_swap, dan swap_ranges

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

// Gambar 12.32: gambar12_32.cpp // Algoritma iter_swap, swap dan swap_ranges di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <iterator> using namespace std; int main() {   const int UKURAN = 10;   int a[ UKURAN ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };   ostream_iterator< int > output( cout, " " );   cout << "Array a memuat:\n ";   copy( a, a + UKURAN, output ); // menampilkan array a   // menukar elemen pada lokasi 0 dengan elemen pada lokasi 1 di dalam array a   swap( a[ 0 ], a[ 1 ] );   cout << "\nArray a setelah menukar a[0] dan a[1] menggunakan swap:\n ";   copy( a, a + UKURAN, output ); // menampilkan array a   // menggunakan iterator untuk menukar elemen lokasi 0 dengan elemen lokasi 1 array a   iter_swap( &a[ 0 ], &a[ 1 ] ); // menukar dengan iterator   cout << "\nArray a setelah menukar a[0] dan a[1] menggunakan iter_swap:\n ";   copy( a, a + UKURAN, output );   // menukar lima elemen pertama dari a dengan   // lima elemen terakhir dari a   swap_ranges( a, a + 5, a + 5 );   cout << "\nArray a setelah menukar lima elemen pertama\n"     << "dengan lima elemen terakhir:\n ";   copy( a, a + UKURAN, output );   cout << endl; } // akhir dari main

Array a memuat:

   1 2 3 4 5 6 7 8 9 10

Array a setelah menukar a[0] dan a[1] menggunakan swap:

   2 1 3 4 5 6 7 8 9 10

Array a setelah menukar a[0] dan a[1] menggunakan iter_swap:

   1 2 3 4 5 6 7 8 9 10

Array a setelah menukar lima elemen pertama

dengan lima elemen terakhir:

   6 7 8 9 10 1 2 3 4 5

Baris 24 menggunakan fungsi iter_swap untuk mempertukarkan dua elemen. Fungsi ini mengambil dua argumen iterator forward (pada kasus ini, pointer yang menunjuk ke elemen suatu array) dan mempertukarkan nilai-nilai di dalam elemen yang ditunjuk oleh iterator.

12.8.8 Algoritma copy_backward, merge, unique, dan reverse

Gambar 12.33 mendemonstrasikan algoritma STL copy_backward, merge, unique, dan reverse. Baris 26 menggunakan fungsi copy_backward untuk menyalin elemen-elemen di dalam rentang mulai dari v1.begin() sampai dengan v1.end(), dengan menempatkan elemen-elemen di dalam hasil mulai dari elemen sebelum hasil.end() dan bergerak ke arah awal vector. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan di elemen terakir yang disalin ke hasil (awal hasil, karena penyalinan mundur). Fungsi ini mensyaratkan bahwa ketiga argumen iterator bidirectional dapat diinkremen dan didekremen dengan arah maju dan arah mundur di dalam suatu runtun. Satu perbedaan antara copy_backward dan copy adalah bahwa iterator yang dijadikan nilai balik oleh copy diposisikan setelah elemen terakhir yang disalin dan iterator yang dijadikan nilai balik oleh copy_backward diposisikan di elemen terakhir yang disalin (elemen pertama di dalam runtun). Juga, bahwa copy_backward dapat memanipulasi rentang elemen yang tumpang-tindih di dalam suatu kontainer sepanjang elemen pertama yang akan disalin bukan destinasi rentang elemennya.

Gambar 12.33 Algoritma copy_backward, merge, unique, dan reverse

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

// Gambar 12.33: gambar12_33.cpp // Algoritma copy_backward, merge, unique dan reverse di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // ostream_iterator using namespace std; int main() {   const int UKURAN = 5;   int a1[ UKURAN ] = { 1, 3, 5, 7, 9 };   int a2[ UKURAN ] = { 2, 4, 5, 7, 9 };   vector< int > v1( a1, a1 + UKURAN ); // salinan dari a1   vector< int > v2( a2, a2 + UKURAN ); // salinan dari a2   ostream_iterator< int > output( cout, " " );   cout << "Vektor v1 memuat: ";   copy( v1.begin(), v1.end(), output ); // menampilkan vektor   cout << "\nVektor v2 mamuat: ";   copy( v2.begin(), v2.end(), output ); // menampilkan vektor   vector< int > hasil( v1.size() );   // menempatkan elemen-elemen dari v1 ke hasil dengan arah terbalik   copy_backward( v1.begin(), v1.end(), hasil.end() );   cout << "\n\nSetelah copy_backward, hasil memuat: ";   copy( hasil.begin(), hasil.end(), output );   vector< int > hasil2( v1.size() + v2.size() );   // menggabung elemen-elemen dari v1 dan v2 ke hasil2 dalam tatanan terurut   merge( v1.begin(), v1.end(), v2.begin(), v2.end(), hasil2.begin() );   cout << "\n\nSetelah merge dari v1 dan v2 hasil2 memuat:\n";   copy( hasil2.begin(), hasil2.end(), output );   // mengeliminasi nilai-nilai duplikat dari hasil2   vector< int >::iterator endLokasi;   endLokasi = unique( hasil2.begin(), hasil2.end() );   cout << "\n\nSetelah unique hasil2 memuat:\n";   copy( hasil2.begin(), endLokasi, output );   cout << "\n\nVektor v1 setelah reverse: ";   reverse( v1.begin(), v1.end() ); // membalik elemen-elemen dari v1   copy( v1.begin(), v1.end(), output );   cout << endl; } // akhir dari main

Vektor v1 memuat: 1 3 5 7 9

Vektor v1 memuat: 2 4 5 7 9

Setelah copy_backward, hasil memuat: 1 3 5 7 9

Setelah merge dari v1 dan v2 hasil2 memuat:

1 2 3 4 5 5 7 7 9 9

Setelah unique hasil2 memuat:

1 2 3 4 5 7 9

Vektor v1 setelah reverse: 9 7 5 3 1

Baris 33 menggunakan fungsi merge untuk menggabungkan dua runtun nilai terurut menaik menjadi sebuah runtun ketiga  terurut menaik. Fungsi ini memerlukan lima argumen iterator. Keempat argumen pertama harus sedikitnya berupa iterator input dan argumen terakhir harus berupa sedikitnya berupa iterator output. Dua argumen pertama menspesifikasi rentang elemen di dalam runtun terurut pertama (v1), dua argumen kedua menspesifikasi rentang elemen di dalam runtun terurut kedua (v2) dan argumen terakhir menspesifikasi lokasi awal di dalam runtun ketiga (hasil2) dimana elemen-elemen akan digabungkan. Versi kedua dari fungsi ini mengambil sebuah fungsi predikat biner sebagai argumen keenamnya yang menspesifikasi tatanan pengurutan.

Baris 30 menciptakan vektor hasil2 dengan jumlah elemen v1.size() + v2.size(). Penggunaan fungsi merge di sini mensyaratkan bahwa runtun dimana hasil penggabungan disimpan harus mempunyai ukuran sedikitnya total ukuran penggabungan dua runtun. Jika Anda tidak ingin mengalokasikan jumlah elemen untuk runtun yang dihasilkan sebelum operasi merge, Anda dapat menggunakan statemen berikut ini:

vector< int > hasil2;

merge( v1.begin(), v1.end(), v2.begin(), v2.end(),

back_inserter(hasil2) );

Argumen back_inserter(hasil2) menggunakan template fungsi back_inserter (header <iterator>) untuk kontainer hasil2. Sebuah back_inserter memanggil fungsi push_back default untuk menyisipkan sebuah elemen di ujung akhir kontainer. Jika sebuah elemen disisipkan ke suatu kontainer yang tidak lagi memiliki ruang, maka kontainer itu akan mengekspansi ukurannya. Jadi, jumlah elemen di dalam kontainer tidak perlu diketahui sebelumnya.

Baris 40 menggunakan fungsi unique pada runtun elemen terurut di dalam rentang mulai dari hasil2.begin() sampai hasil2.end() di dalam hasil2. Jika fungsi ini diterapkan terhadap sebuah runtun terurut yang memuat nilai-nilai duplikat, maka hanya satu salinan atas tiap nilai yang akan tersisa di dalam runtun tersebut. Fungsi ini mengambil dua argumen yang sedikitnya harus berupa iterator forward. Fungsi ini menghasilkan nilai balik berupa sebuah iterator yang diposisikan setelah elemen terakhir di dalam runtun dengan nilai-nilai unik. Nilai semua elemen di dalam kontainer setelah nilai unik terakhir tidak terdefinisi.

Baris 46 menggunakan fungsi reverse untuk membalik urutan semua elemen di dalam rentang dimulai dari v1.begin() sampai v1.end() di dalam v1. Fungsi ini mengambil dua argumen yang sedikitnya harus berupa iterator bidirectional.

12.8.9 Algoritma inplace_merge, unique_copy, dan reverse_copy

Gambar 12.34 mendemonstrasikan algoritma inplace_merge, unique_copy, dan reverse_copy. Baris 22 menggunakan fungsi inplace_merge untuk menggabungkan dua runtun terurut di dalam kontainer yang sama. Pada contoh ini, elemen-elemen dari v1.begin() sampai v1.begin() + 5 - 1 digabungkan dengan elemen-elemen dari v1.begin() + 5 sampai v1.end(). Fungsi ini mensyaratkan bahwa ketiga argumen iteratornya harus berupa sedikitnya iterator bidirectional.

Gambar 12.34 Algoritma inplace_merge, unique_copy, dan reverse_copy

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

// Gambar 12.34: gambar12_34.cpp // Algoritma inplace_merge, // reverse_copy dan unique_copy di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // definisi back_inserter using namespace std; int main() {   const int UKURAN = 10;   int a1[ UKURAN ] = { 1, 3, 5, 7, 9, 1, 3, 5, 7, 9 };   vector< int > v1( a1, a1 + UKURAN ); // salinan dari a   ostream_iterator< int > output( cout, " " );   cout << "Vektor v1 memuat: ";   copy( v1.begin(), v1.end(), output );   // menggabungkan setengah bagian pertama dari v1 dengan setengah bagian   // kedua dari v1 sehingga v1 memuat sehimpunan elemen terurut setelah merge   inplace_merge( v1.begin(), v1.begin() + 5, v1.end() );   cout << "\nSetelah inplace_merge, v1 memuat: ";   copy( v1.begin(), v1.end(), output );   vector< int > hasil1;   // menyalin hanya elemen-elemen unik dari v1 ke hasil1   unique_copy( v1.begin(), v1.end(), back_inserter( hasil1 ) );   cout << "\nSetelah unique_copy hasil1 memuat: ";   copy( hasil1.begin(), hasil1.end(), output );   vector< int > hasil2;   // menyalin elemen-elemen dari v1 ke hasil2 dengan urutan terbalik   reverse_copy( v1.begin(), v1.end(), back_inserter( hasil2 ) );   cout << "\nSetelah reverse_copy, hasil2 memuat: ";   copy( hasil2.begin(), hasil2.end(), output );   cout << endl; } // akhir dari main

Vektor v1 memuat: 1 3 5 7 9 1 3 5 7 9

Setelah inplace_merge, v1 memuat: 1 1 3 3 5 5 7 7 9 9

Setelah unique_copy hasil memuat: 1 3 5 7 9

Setelah reverse_copy, hasil2 memuat: 9 9 7 7 5 5 3 3 1 1

Baris 30 menggunakan fungsi unique_copy untuk membuat salinan dari semua elemen unik di dalam runtun nilai terurut mulai dari v1.begin() sampai v1.end(). Elemen-elemen yang disalin ditempatkan ke vector hasil1. Dua argumen pertama sedikitnya harus berupa iterator input dan argumen terakhir harus sedikitnya berupa sebuah argumen output. Pada contoh ini, Anda tidak perlu sebelumnya mengalokasikan memori yang cukup untuk menampung elemen-elemen yang disalin dari v1, karena digunakan fungsi back_inserter (yang didefinisikan di dalam header <iterator>).

Baris 37 menggunakan fungsi reverse_copy untuk membuat salinan terbalik atas elemen-elemen di dalam rentang mulai dari v1.begin() sampai v1.end(). Elemen-elemen yang disalin disisipkan ke dalam hasil2 menggunakan objek back_inserter untuk memastikan bahwa vector dapat mengekspansi ukurannya untuk mengakomodasi jumlah elemen yang disalin. Fungsi reverse_copy mensyaratkan bahwa dua argumen iterator pertama sedikitnya harus berupa iterator bidirectional dan argumen ketiganya harus berupa sedikitnya sebuah iterator output.

12.8.10 Operasi-Operasi set

Gambar 12.35 mendemonstrasikan fungsi includes, set_difference, set_intersection, set_symmetric, dan set_union untuk memanipulasi sehimpunan nilai terurut. Untuk mendemonstrasikan bahwa fungsi-fungsi STL dapat diterapkan pada array dan kontainer, contoh ini hanya menggunakan array (ingat bahwa pointer ke array adalah iterator random access).

Baris 25 dan 31 memanggil fungsi includes. Fungsi ini membandingkan dua himpunan nilai terurut untuk menentukan apakah setiap elemen dari himpunan kedua berada di dalam himpunan pertama. Jika ya, includes menghasilkan true; sebaliknya menghasilkan false. Dua argumen iterator pertama sedikitnya harus berupa iterator input. Pada baris 25, himpunan pertama memuat elemen-elemen dari a1 sampai a1 + UKURAN. Dua argumen iterator terakhir sedikitnya harus berupa iterator input. Pada contoh ini, himpunan kedua memuat elemen-elemen dari a2 sampai a2 + UKURAN2.

Gambar 12.35 Algoritma includes, set_difference, set_intersection, set_symmetric_difference, dan set_union STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

// Gambar 12.35: gambar12_35.cpp // Algoritma includes, set_difference, // set_intersection, set_symmetric_difference dan set_union di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <iterator> // ostream_iterator using namespace std; int main() {   const int UKURAN1 = 10, UKURAN2 = 5, UKURAN3 = 20;   int a1[ UKURAN1 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };   int a2[ UKURAN2 ] = { 4, 5, 6, 7, 8 };   int a3[ UKURAN2 ] = { 4, 5, 6, 11, 15 };   ostream_iterator< int > output( cout, " " );   cout << "a1 memuat: ";   copy( a1, a1 + UKURAN1, output ); // menampilkan array a1   cout << "\na2 memuat: ";   copy( a2, a2 + UKURAN2, output ); // menampilkan array a2   cout << "\na3 memuat: ";   copy( a3, a3 + UKURAN2, output ); // menampilkan array a3   // menentukan apakah himpunan a2 secara utuh dimuat di dalam a1   includes( a1, a1 + UKURAN1, a2, a2 + UKURAN2 )     cout << "\n\na1 mencakup a2";   else     cout << "\n\na1 tidak mencakup a2";   // menentukan apakah himpunan a3 secara utuh dimuat di dalam a1   includes( a1, a1 + UKURAN1, a3, a3 + UKURAN2 )     cout << "\na1 mencakup a3";   else     cout << "\na1 tidak mencakup a3";   int difference[ UKURAN1 ];   // menentukan elemen-elemen a1 yang tidak di dalam a2   int *ptr = set_difference( a1, a1 + UKURAN1,     a2, a2 + UKURAN2, difference );   cout << "\n\nset_difference dari a1 dan a2 adalah: ";   copy( difference, ptr, output );   int intersection[ UKURAN1 ];   // menentukan elemen-elemen di dalam kedua a1 dan a2   ptr = set_intersection( a1, a1 + UKURAN1,     a2, a2 + UKURAN2, intersection );   cout << "\n\nset_intersection dari a1 dan a2 adalah: ";   copy( intersection, ptr, output );   int symmetric_difference[ UKURAN1 + UKURAN2 ];   // menentukan elemen-elemen dari a1 yang tidak di dalam a2 dan   // elemen-elemen dari a2 yang tidak di dalam a1   ptr = set_symmetric_difference( a1, a1 + UKURAN1,     a3, a3 + UKURAN2, symmetric_difference );   cout << "\n\nset_symmetric_difference dari a1 dan a3 adalah: ";   copy( symmetric_difference, ptr, output );   int unionSet[ UKURAN3 ];   // menentukan elemen-elemen yang  berada di salah satu atau kedua himpunan   ptr = set_union( a1, a1 + UKURAN1, a3, a3 + UKURAN2, unionSet );   cout << "\n\nset_union dari a1 dan a3 adalah: ";   copy( unionSet, ptr, output );   cout << endl; } // akhir dari main

a1 memuat: 1 2 3 4 5 6 7 8 9 10

a2 memuat: 4 5 6 7 8

a3 memuat: 4 5 6 11 15

a1 mencakup a2

a1 tidak mencakup a3

set_difference dari a1 dan a2 adalah: 1 2 3 9 10

set_intersection dari a1 dan a2 adalah: 4 5 6 7 8

set_symmetric_difference dari a1 dan a3 adalah: 1 2 3 7 8 9 10 11 15

set_union dari a1 dan a3 adalah: 1 2 3 4 5 6 7 8 9 10 11 15

Baris 39-40 menggunakan fungsi set_difference untuk menemukan elemen-elemen dari himpunan pertama yang memuat nilai-nilai terurut yang tidak berada di dalam himpunan kedua nilai-nilai terurut (kedua himpunan nilai harus dalam tatanan urutan menaik). Elemen-elemen tersebut disalin ke argumen kelima (pada kasus ini, array difference). Dua argumen iterator pertama sedikitnya harus berupa iterator input untuk himpunan pertama. Dua argumen iterator berikutnya sedikitnya harus berupa iterator input untuk himpunan kedua. Argumen kelima sedikitnya harus berupa iterator output yang mengindikasikan tempat dimana untuk menyimpan salinan nilai-nilai yang berbeda. Fungsi ini menghasilkan nilai balik berupa sebuah iterator output yang diposisikan satu elemen setelah nilai terakhir yang disalin ke lokasi yang ditunjukkan oleh argumen kelima.

Baris 47-48 menggunakan fungsi set_intersection untuk menentukan elemen-elemen dari himpunan pertama yang memuat nilai-nilai terurut yang berada di dalam himpunan kedua yang memuat nilai-nilai terurut (kedua himpunan nilai harus dalam tatanan urutan menaik). Elemen-elemen tersebut disalin ke argumen kelima (pada kasus ini, array intersection). Dua argumen iterator pertama sedikitnya harus berupa iterator input untuk himpunan pertama. Dua argumen iterator berikutnya sedikitnya harus berupa iterator input untuk himpunan kedua. Argumen kelima sedikitnya harus berupa iterator output yang mengindikasikan tempat dimana untuk menyimpan salinan nilai-nilai yang berbeda. Fungsi ini menghasilkan nilai balik berupa sebuah iterator output yang diposisikan satu elemen setelah nilai terakhir yang disalin ke lokasi yang ditunjukkan oleh argumen kelima.

Baris 56-57 menggunakan fungsi set_symmetric_difference untuk menentukan elemen-elemen dari himpunan pertama yang memuat nilai-nilai terurut yang tidak berada di dalam himpunan kedua yang memuat nilai-nilai terurut (kedua himpunan nilai harus dalam tatanan urutan menaik). Fungsi ini juga untuk memastikan bahwa elemen-elemen dari himpunan pertama tidak berada di dalam himpunan kedua. Elemen-elemen tersebut disalin ke argumen kelima (pada kasus ini, array symmetric_difference). Dua argumen iterator pertama sedikitnya harus berupa iterator input untuk himpunan pertama. Dua argumen iterator berikutnya sedikitnya harus berupa iterator input untuk himpunan kedua. Argumen kelima sedikitnya harus berupa iterator output yang mengindikasikan tempat dimana untuk menyimpan salinan nilai-nilai yang berbeda. Fungsi ini menghasilkan nilai balik berupa sebuah iterator output yang diposisikan satu elemen setelah nilai terakhir yang disalin ke lokasi yang ditunjukkan oleh argumen kelima.

Baris 64 menggunakan fungsi set_union untuk menciptakan sebuah himpunan yang memuat semua elemen yang berada di dalam salah satu atau kedua himpunan (kedua himpunan nilai harus dalam tatanan urutan menaik). Elemen-elemen tersebut disalin ke argumen kelima (pada kasus ini, array unionSet). Dua argumen iterator pertama sedikitnya harus berupa iterator input untuk himpunan pertama. Dua argumen iterator berikutnya sedikitnya harus berupa iterator input untuk himpunan kedua. Argumen kelima sedikitnya harus berupa iterator output yang mengindikasikan tempat dimana untuk menyimpan salinan nilai-nilai yang berbeda. Fungsi ini menghasilkan nilai balik berupa sebuah iterator output yang diposisikan satu elemen setelah nilai terakhir yang disalin ke lokasi yang ditunjukkan oleh argumen kelima.

12.8.11 Algoritma lower_bound, upper_bound, dan equal_range

Gambar 12.36 mendemonstrasikan fungsi lower_bound, upper_bound, dan equal_range. Baris 22 menggunakan fungsi lower_bound untuk menemukan lokasi pertama di dalam runtun nilai terurut dimana argumen ketiga dapat disisipkan di dalam runtun tersebut sehingga runtun itu masih tertata terurut secara menaik. Dua argumen iterator pertama sedikitnya harus berupa iterator forward. Argumen ketiga merupakan sebuah nilai untuk menentukan batas bawah. Nilai balik fungsi adalah sebuah iterator forward yang menunjuk ke posisi dimana penyisipan dapat dilakukan. Versi kedua dari fungsi lower_bound mengambil fungsi predikat biner sebagai argumen keempat, yang mengindikasikan tatanan pengurutan elemen.

Baris 28 menggunakan upper_bound untuk menemukan lokasi terakhir di dalam runtun nilai terurut dimana argumen ketiga dapat disisipkan di dalam runtun tersebut sehingga runtun itu masih tertata terurut secara menaik. Dua argumen iterator pertama sedikitnya harus berupa iterator forward. Argumen ketiga merupakan sebuah nilai untuk menentukan batas atas. Nilai balik fungsi adalah sebuah iterator forward yang menunjuk ke posisi dimana penyisipan dapat dilakukan. Versi kedua dari fungsi upper_bound mengambil fungsi predikat biner sebagai argumen keempat, yang mengindikasikan tatanan pengurutan elemen.

Gambar 12.36 Algoritma lower_bound, upper_bound, dan equal_range STL

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64

// Gambar 12.36: gambar12_36.cpp // Algoritma lower_bound, upper_bound dan // equal_range di dalam STL. #include <iostream> #include <algorithm> // definisi algoritma #include <vector> // definisi template kelas vector #include <iterator> // ostream_iterator using namespace std; int main() {   const int UKURAN = 10;   int a1[ UKURAN ] = { 2, 2, 4, 4, 4, 6, 6, 6, 6, 8 };   vector< int > v( a1, a1 + UKURAN ); // salinan dari a1   ostream_iterator< int > output( cout, " " );   cout << "Vektor v memuat:\n";   copy( v.begin(), v.end(), output );   // menentukan batas-bawah titik penyisipan untuk 6 di dalam v   vector< int >::iterator bawah;   bawah = lower_bound( v.begin(), v.end(), 6 );   cout << "\n\nBatas bawah untuk 6 adalah elemen "     << ( bawah - v.begin() ) << " di vektor v";   // menentukan batas-atas titik penyisipan untuk 6 di dalam v   vector< int >::iterator atas;   atas = upper_bound( v.begin(), v.end(), 6 );   cout << "\nBatas atas untuk 6 adalah elemen "    << ( atas - v.begin() ) << " di vektor v";   // menggunakan equal_range untuk menentukan batas atas dan   // batas bawah titik penyisipan untuk 6   pair< vector< int >::iterator, vector< int >::iterator > eq;   eq = equal_range( v.begin(), v.end(), 6 );   cout << "\nMenggunakan equal_range:\n Batas bawah dari 6 adalah elemen "     << ( eq.first - v.begin() ) << " di vektor v";   cout << "\n Batas atas dari 6 adalah elemen "     << ( eq.second - v.begin() ) << " di vektor v";   cout << "\n\nMenggunakan lower_bound untuk melokasi titik pertama\n"     << "dimana 6 bisa disisipkan";   // menentukan batas bawah titik penyisipan untuk 5 di dalam v   bawah = lower_bound( v.begin(), v.end(), 5 );   cout << "\n Batas bawah untuk 5 adalah elemen "     << ( bawah - v.begin() ) << " di vektor v";   cout << "\n\nMenggunakan upper_bound untuk melokasi titik akhir\n"     << "dimana 7 dapat disisipkan";   // menentukan batas atas titik penyisipan untuk 7 di dalam v   atas = upper_bound( v.begin(), v.end(), 7 );   cout << "\n Batas atas untuk 7 adalah elemen "     << ( atas - v.begin() ) << " di vektor v";   cout << "\n\nMenggunakan equal_range untuk melokasi titik pertama dan\n"    << "titik akhir dimana 5 dapat disisipkan";   // menggunakan equal_range untuk menentukan batas atas dan   // batas bawah titik penyisipan untuk 5   eq = equal_range( v.begin(), v.end(), 5 );   cout << "\n Batas bawah untuk 5 adalah elemen "     << ( eq.first - v.begin() ) << " di vektor v";   cout << "\n Batas atas untuk 5 adalah elemen "     << ( eq.second - v.begin() ) << " di vektor v" << endl; } // akhir dari main

Vektor v memuat: 2 2 4 4 4 6 6 6 6 8

Batas bawah untuk 6 adalah elemen 5 di vektor v

Batas atas untuk 6 adalah elemen 9 di vektor v

Menggunakan equal_range:

Batas bawah untuk 6 adalah elemen 5 di vektor v

Batas atas untuk 6 adalah elemen 9 di vektor v

Menggunakan lower_bound untuk melokasi titik pertama

dimana 5 bisa disisipkan

   Batas bawah untuk 5 adalah elemen 5 di vektor v

Menggunakan upper_bound untuk melokasi titik akhir

dimana 7 bisa disisipkan

   Batas atas untuk 7 adalah elemen 9 di vektor v

Menggunakan equal_range untuk melokasi titik pertama dan

titik akhir dimana 5 bisa disisipkan

   Batas bawah untuk 5 adalah elemen 5 di vektor v

   Batas atas untuk 5 adalah elemen 5 di vektor v

Kesimpulan

      Kontainer dibagi ke dalam tiga kategori utama, yaitu kontainer runtun, kontainer asosiatif, dan kontained adapter.

      Kontainer STL kelas-pertama menyediakan fungsi begin dan end. Fungsi begin menghasilkan nilai balik berupa sebuah iterator yang menunjuk ke elemen pertama di dalam kontainer. Fungsi end menghasilkan nilai balik berupa sebuah iterator yang menunjuk ke elemen pertama setelah elemen terakhir di dalam kontainer (elemen yang belum ada).

      STL menyediakan tiga kontainer runtun, yaitu vector, list, dan deque. Template kelas vector dan template kelas deque keduanya didasarkan pada array. Template kelas list mengimplementasikan sebuah struktur data list-berantai.

      Kontainer asosiatif STL menyediakan akses langsung dalam menyimpan mengambil elemen melalui kunci (seringkali disebut juga dengan kunci pencarian).  Ada empat kontainer asosiatif, yaitu multiset, set, multimap, dan map. Setiap kontainer asosiatif mempunyai kunci dalam tatanan terurut. Kelas multiset dan set menyediakan beberapa operasi untuk memanipulasi sehimpunan nilai dimana nilai-nilai tersebut merupakan kuncinya. Perbedaan utama antara multiset dan set adalah bahwa multiset membolehkan adanya kunci duplikat sedangkan set tidak mengijinkan adanya kunci duplikat.

      STL menyediakan tiga adapter kontainer, yaitu stack, queue, dan prioriy_queue. Adapter bukan kontainer kelas-pertama, karena ia tidak menyediakan implementasi struktur data aktual dimana di dalamnya elemen-elemen dapat disimpan dan karena adapter tidak mendukung iterator. Keuntungan dari kelas adapter adalah bahwa Anda dapat memilih struktur data yang cocok untuk aplikasi Anda. Ketiga kelas adapter menyediakan fungsi anggota push dan pop yang menyisipkan sebuah elemen ke dalam setiap struktur data adapter dan menghapus sebuah elemen dari setiap struktur data adapter.

       STL memisahkan algoritma dari kontainer. Hal ini membuat penambahan algoritma baru menjadi lebih mudah. Dengan STL, elemen kontainer dapat diakses melalui iterator.

Latihan

1.      Tulislah sebuah template fungsi palindrome yang mengambil sebuah parameter vector dan menghasilkan nilai balik true atau false tergantung dari apakah vector membaca atau tidak membaca sebuah palindrome. ( Misalnya, vector yang memuat 1 2 3 2 1 adalah sebuah palindrome, tetapi vector yang memuat 1 2 3 4 bukan sebuah palindrome).