Algoritm (C++)

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 28 april 2015; kontroller kräver 16 redigeringar .

algorithm är en rubrikfil i standardbiblioteket för programmeringsspråket C++ , som inkluderar en uppsättning funktioner för att utföra algoritmiska operationer på behållare och andra sekvenser [1] .

Alla biblioteksfunktioner finns i namnutrymmet std [2] .

Kategorier av algoritmer

STL-standardbiblioteksalgoritmerna faller inom följande kategorier.

Beskrivning av algoritmer

I tabellerna nedan, i funktionsargumentkolumnen, hittar du följande symboler:

  1. första, sista — slut- och startiteratorer (first1, last1, first2, last2 — slut- och startiteratorer av intervall 1 respektive 2)
  2. mitten - en iterator som pekar på en specifik position i behållaren
  3. funktion, predikat, op och komp är funktionsobjekt
  4. värde, nytt, gammalt och init är värdena för de objekt som lagras i behållarna
  5. a, b är några objekt av samma typ
  6. iter - iterator

Sekventiella operationer som inte ändras

Funktionsnamn Funktionsargument Funktionsbeskrivning
adjacent_find first, last Returnerar en iterator som pekar på det första paret av identiska objekt
count first, last, value Returnerar antalet element vars värde ärvalue
equal first1, last1, first2 Returnerar trueom alla matchande par av objekt från två intervall är lika
find first, last, value Returnerar en iterator som pekar på det första elementet lika med värdevalue
for_each first, last, function Gäller functionalla objekt
mismatch first1, last1, first2 Returnerar det första icke-matchande paret av matchande objekt som finns i olika intervall av behållarpositioner
search first1, last1, first2, last2 Testar om det andra intervallet finns inom det första, returnerar början av matchen eller sist1 om det inte finns någon matchning

Ändra sekventiella operationer

Funktionsnamn Funktionsargument Funktionsbeskrivning
fill first, last, value Tilldelar ett värde till valuealla objekt i ett intervall
generate first, last, gen Fyller ett intervall med värden som erhålls genom successiva funktionsanropgen
iter_swap iter1, iter2 Byter ut de objekt som två iteratorer pekar på
remove first, last, value Tar bort från intervallet alla värden är lika medvalue
reverse first, last Vänder om en sekvens av objekt från ett område
replace first, last, old, new Ersätter alla objekt lika oldmed med objekt lika mednew
rotate first, last, middle Speglar sekvensen av element
swap a, b Ersätter ett objekt med ett annat
swap_ranges first1, last1, first2 Byter ut matchande objekt i två intervall
transform first1, last1, first2, operator Förvandlar objekt i intervall 1 till nya objekt i intervall 2 genom att tillämpaoperator
unique first, last Tar bort alla motsvarande objekt i en sekvens utom det första

Sorteringsoperationer

Funktionsnamn Funktionsargument Funktionsbeskrivning
nth_element first, nth,last Placerar det n:e objektet i den position som det skulle ha haft efter att ha sorterat hela intervallet
sort first, last Sorterar objekt i ett intervall
stable_sort first, last Sorterar objekten i ett intervall. Om två objekt är lika, kommer deras ordning inte att ändras.

Binära sökoperationer

Funktionsnamn Funktionsargument Funktionsbeskrivning
binary_search first, last, value Returnerar trueom värdet valueligger inom intervallet
equal_range first, last, value Returnerar ett par objekt som representerar de nedre och övre gränserna mellan vilka ett värde kan infogas valueutan att ändra sorteringsordningen
lower_bound first, last, value Returnerar en iterator som pekar på den första positionen där ett värde kan infogas valueutan att ändra ordningen på objekten
upper_bound first, last, value Returnerar en iterator som pekar till den sista positionen där ett värde kan infogas valueutan att ändra ordningen på objekten

Sammanfoga operationer

Funktionsnamn Funktionsargument Funktionsbeskrivning
includes first1, last1, first2, last2 Returnerar trueom alla objekt i intervall först2 sist2 också är i intervall först1 sist1 (endast för uppsättnings- och multisetarbete)
merge first1, last1, first2, last2, first3 slår samman sorterade intervall 1 och 2 till intervall 3
set_difference first1, last1, first2, last2, first3 Skapar en ordnad skillnad av set givna intervall 1 och 2 (endast för set och multiset)
set_intersection first1, last1, first2, last2, first3 Skapar en ordnad skärningspunkt mellan elementen i intervall 1 och 2 (endast för att arbeta med set och multiset)
set_union first1, last1, first2, last2, first3 Skapar en ordnad förening av elementen i intervall 1 och 2 (fungerar endast med set och multiset)

Heaps

Funktionsnamn Funktionsargument Funktionsbeskrivning
make_heap first, last Skapar en hög från intervallvärden först sist
pop_heap first, last Ändrar värdena i första och sista-1. Trycker intervallet först sist-1 till högen
push_heap first, last Lägger värdet från sista-1 i det resulterande heap-området (hög, dynamiskt minnesområde) från första till sista
sort_heap first, last Ordnar elementen i högen först sist

Relationsoperationer

Funktionsnamn Funktionsargument Funktionsbeskrivning
lexicographical_compare first1, last1, first2, last2 Returnerar trueom sekvensen i intervall 2 alfabetiskt följer sekvensen i intervall 1
max a, b Returnerar den största av a, b
max_element first, last Returnerar en iterator som pekar på det största objektet i ett intervall
min a, b Returnerar den minsta av a, b
min_element first,last Returnerar en iterator som pekar på det minsta objektet i ett intervall
next_permutation first, last Utför en permutation i sekvensen av det givna området
prev_permutation first, last Utför en omvänd permutation i sekvensen av det givna området

Anteckningar

  1. ISO / IEC (2003). ISO/IEC 14882:2003(E): Programmeringsspråk - C++ § 25 Algoritmbibliotek [lib.algorithms] para. ett
  2. Stroustrup, Bjarne. Programmering : principer och praxis med C++  . - Upper Saddle River, NJ: Addison-Wesley , 2009. - P. 729. - ISBN 9780321543721 . . - "Standardbiblioteksalgoritmerna finns i <algorithm>.".

Litteratur

Länkar