Algoritma

Algoritma adalah bagian mendasar dari Pustaka Standar C++. Algoritma tidak berfungsi dengan kontainer itu sendiri melainkan dengan iterator. Oleh karena itu, algoritma yang sama dapat digunakan oleh sebagian besar jika tidak semua kontainer Pustaka Standar C++. Bagian ini membahas konvensi dan terminologi algoritma Pustaka Standar C++.

Keterangan

Deskripsi templat fungsi algoritma menggunakan beberapa frasa singkat:

• Frasa "dalam rentang [A, B)" berarti urutan nol atau lebih nilai diskrit yang dimulai dengan A hingga tetapi tidak termasuk B. Rentang hanya valid jika B dapat dijangkau dari A, Anda dapat menyimpan A di objek N (N = A), Anda dapat menaikkan objek nol atau lebih kali (++N), dan memiliki objek dibandingkan dengan B setelah jumlah kenaikan terbatas (N == B).

• Frasa "setiap N dalam rentang [A, B)" berarti bahwa N dimulai dengan nilai A dan ditahapkan nol atau lebih kali sampai sama dengan nilai B. Kasus N == B tidak dalam rentang.

• Frasa "nilai terendah N dalam rentang [A, B) sehingga X" berarti bahwa kondisi X ditentukan untuk setiap N dalam rentang [A, B) hingga kondisi X terpenuhi.

• Frasa "nilai tertinggi N dalam rentang [A, B) sehingga X" berarti bahwa X ditentukan untuk setiap N dalam rentang [A, B). Fungsi ini menyimpan dalam K salinan N setiap kali kondisi X terpenuhi. Jika ada penyimpanan seperti itu terjadi, fungsi menggantikan nilai akhir N, yang sama dengan B, dengan nilai K. Namun, untuk iterator akses dua arah atau acak, itu juga dapat berarti bahwa N dimulai dengan nilai tertinggi dalam rentang dan dikurangi di atas rentang hingga kondisi X terpenuhi.

• Ekspresi seperti X - Y, di mana X dan Y dapat menjadi iterator selain iterator akses acak, dimaksudkan dalam arti matematika. Fungsi ini tidak selalu mengevaluasi operator - jika harus menentukan nilai seperti itu. Hal yang sama juga berlaku untuk ekspresi seperti X + N dan X - N, di mana N adalah jenis bilangan bulat.

Beberapa algoritma menggunakan predikat yang melakukan perbandingan berpasangan, seperti dengan operator==, untuk menghasilkan bool hasil. Fungsi operator==predikat , atau penggantian apa pun untuk itu, tidak boleh mengubah salah satu operannya. Ini harus menghasilkan hasil yang sama bool setiap kali dievaluasi, dan harus menghasilkan hasil yang sama jika salinan salah satu operan diganti untuk operand.

Beberapa algoritma menggunakan predikat yang harus memberlakukan urutan lemah yang ketat pada pasangan elemen dari urutan. Untuk predikat pred(X, Y):

• Ketat berarti pred(X, X) salah.

• Lemah berarti bahwa X dan Y memiliki urutan yang setara jika!pred(X, Y) && & !pred(Y, X) (X == Y tidak perlu ditentukan).

• Pemesanan berarti pred(X, Y) && pred(Y, Z) menyiratkan pred(X, Z).

Beberapa algoritma ini secara implisit menggunakan predikat X<Y. Predikat lain yang biasanya memenuhi persyaratan pemesanan yang lemah yang ketat adalah X>Y, less(X, Y), dan greater(X, Y). Namun, perhatikan bahwa predikat seperti X<= Y dan X>= Y tidak memenuhi persyaratan ini.

Urutan elemen yang ditunjuk oleh iterator dalam rentang [First, ) adalah urutan yang diurutkan oleh operator < jika, untuk setiap N dalam rentang [0, LastFirst - ) dan untuk setiap M dalam rentang (N, LastFirst - ) predikat !( Last *(First + M) < *(First + N)) benar. (Perhatikan bahwa elemen diurutkan dalam urutan naik.) Fungsi operator<predikat , atau penggantian apa pun untuk itu, tidak boleh mengubah salah satu operannya. Ini harus menghasilkan hasil yang sama bool setiap kali dievaluasi, dan harus menghasilkan hasil yang sama jika salinan salah satu operan diganti untuk operand. Selain itu, itu harus memaksakan urutan lemah yang ketat pada operan yang dibandingkan.

Urutan elemen yang ditunjuk oleh iterator dalam rentang [First, ) adalah tumpukan yang diurutkan oleh operator< jika, untuk setiap N dalam rentang [1, Last - First) predikat !( Last *Pertama< *(First + N)) benar. (Elemen pertama adalah yang terbesar.) Struktur internalnya hanya diketahui oleh fungsi make_heaptemplat , , pop_heapdan push_heap. Seperti urutan yang diurutkan, fungsi operator<predikat , atau penggantian apa pun untuk itu, tidak boleh mengubah salah satu operannya, dan harus memaksakan urutan lemah yang ketat pada operan yang dibandingkan. Ini harus menghasilkan hasil yang sama bool setiap kali dievaluasi, dan harus menghasilkan hasil yang sama jika salinan salah satu operan diganti untuk operand.

Algoritma Pustaka Standar C++ terletak di <algorithm> file header dan <numeric> .

Lihat juga

Referensi pustaka standar C++
Keamanan utas di Pustaka Standar C++