Knihovna standardních šablon III


	31. Knihovna standardních šablon III

Nyní se podrobněji seznámíme se všemi obecnými algoritmy poskytnutými standardní knihovnou. Jména a krátký popis těchto algoritmů je uveden v následující tabulce. Tyto algoritmy můžeme rozdělit do několika kategorií, a to na základě jejich obvyklého použití.

Jméno	Popis
	Algoritmy používané k plnění sekvence
fill	Plnění sekvence počátečními hodnotami.
fill_n	Plnění n pozic počáteční hodnotou.
copy	Kopírování sekvence z jiné sekvence.
copy_backward	Kopírování sekvence z jiné sekvence.
generate	Inicializuje sekvenci pomocí generátoru.
generate_n	Inicializuje n pozic pomocí generátoru.
swap_ranges	Zaměňuje hodnoty ve dvou paralelních sekvencích.
	Vyhledávací algoritmy
find	Hledání prvku odpovídajícímu parametru.
find_if	Hledání prvku splňujícího podmínku.
adjacent_find	Hledání prvku shodujícího se s následujícím prvkem.
find_first_of	Hledání prvního výskytu jedné sekvence v jiné sekvenci.
find_end	Hledání posledního výskytu podsekvence v sekvenci.
search	Hledání podsekvence v sekvenci.
max_element	Hledání maximální hodnoty v sekvenci.
min_element	Hledání minimální hodnoty v sekvenci.
mismatch	Nalezení první neshody v paralelních sekvencích.
	Transformace na místě
reverse	Obrací prvky v sekvenci.
replace	Nahrazuje specifikované hodnoty novou hodnotou.
replace_if	Nahrazuje prvky vyhovující tvrzení.
rotate	Rotuje prvky v sekvenci okolo bodu.
partition	Rozděluje prvky do dvou skupin.
stable_partition	Rozdělování chránící původní pořadí.
next_permutation	Generuje permutaci v sekvenci.
prev_permutation	Generuje permutaci v reverzní sekvenci.
inplace_merge	Spojuje dvě sousední sekvence v jednu.
random_shuffle	Náhodně přeskupí prvky v sekvenci.
	Odstraňovací algoritmy
remove	Odstraňuje prvky splňující podmínku.
unique	Odstraňuje všechny neprvní duplicitní hodnoty v sekvenci.
	Algoritmy generující skalár
count	Počet prvků s odpovídající hodnotou.
count_if	Počet prvků vyhovujících tvrzení.
accumulate	Redukce sekvence na skalární hodnotu.
inner_product	Vnitřní produkt dvou paralelních sekvencí.
equal	Test dvou sekvencí na rovnost.
lexicographical_compare	Porovnávání dvou sekvencí.
	Algoritmy generující sekvence
transform	Transformuje každý prvek.
partial_sum	Generuje sekvenci částečných součtů.
adjacent_difference	Generuje sekvenci sousedních rozdílů.
	Různé operace
for_each	Aplikuje funkci na každý prvek kolekce.

Pro použití většiny obecných algoritmů musíme vložit příslušný hlavičkový soubor. Hlavní funkce jsou definovány v hlavičkovém souboru algorithm. Funkce accumulate, inner_product, partial_sum a adjacent_difference jsou definovány v hlavičkovém souboru numeric.
# include <algorithm>
# include <numeric>

První skupinou algoritmů, kterými se budeme zabývat jsou algoritmy používané k inicializaci nově vytvořených sekvencí jistými hodnotami. Standardní knihovna poskytuje několik inicializačních algoritmů.

fill

fill_n

void fill (ForwardIterator first, ForwardIterator last, const T&);

void fill_n (OutputIterator, Size, const T&);

void fill_example ()

{

// příklad 1, zaplnění pole počátečními hodnotami

char buffer[100], * bufferp = buffer;

fill (bufferp, bufferp + 100, '\0');

fill_n (bufferp, 10, 'x');

// příklad 2, inicializace seznamu

list<string> aList(5, "nothing");

fill_n (inserter(aList, aList.begin()), 10, "empty");

// příklad 3, přepsání hodnot v seznamu

fill (aList.begin(), aList.end(), "full");

// příklad 4, zaplnění části kolekce

vector<int> iVec(10);

generate (iVec.begin(), iVec.end(), iotaGen(1));

vector<int>::iterator & seven = find(iVec.begin(), iVec.end(), 7);

fill (iVec.begin(), seven, 0);

}

fill

fill_n

fill

fill_n

nothing

fill_n

empty

fill

full

generate

iotaGen

find

fill

fill_n

copy

copy_backward

OutputIterator copy (InputIterator first, InputIterator last,

OutputIterator result);

BidirectionalIterator copy_backward (BidirectionalIterator first,

BidirectionalIterator last, BidirectionalIterator result);

copy

Duplikování celé sekvence kopírováním do nové sekvence.
Vytváření podsekvence existující sekvence.
Přidávání prvků do sekvence.
Kopírování sekvence ze vstupu na výstup.
Konverze sekvence z jedné formy do jiné.

void copy_example()

{

char * source = "reprise";

char * surpass = "surpass";

char buffer[120], * bufferp = buffer;

// příklad 1, jednoduchá kopie

copy (source, source + strlen(source) + 1, bufferp);

// příklad 2, kopie do sebe sama

copy (bufferp + 2, bufferp + strlen(buffer) + 1, bufferp);

int buflen = strlen(buffer) + 1;

copy_backward (bufferp, bufferp + buflen, bufferp + buflen + 3);

copy (surpass, surpass + 3, bufferp);

// příklad 3, kopírování na výstup

copy (bufferp, bufferp + strlen(buffer),

ostream_iterator<char,char>(cout));

cout << endl;

// příklad 4, použití kopírování pro převod typu

list<char> char_list;

copy (bufferp, bufferp + strlen(buffer),

inserter(char_list, char_list.end()));

char * big = "big ";

copy (big, big + 4, inserter(char_list, char_list.begin()));

char buffer2 [120], * buffer2p = buffer2;

* copy (char_list.begin(), char_list.end(), buffer2p) = '\0';

cout << buffer2 << endl;

}

copy

source

buffer

copy

buffer

copy_backward

copy

buffer

copy

buffer

copy

ostream_iterator

cout

copy

list<string> words;

istream_iterator<string, char> in_stream(cin), eof;

copy(in_stream, eof, inserter(words, words.begin()));

copy

buffer

inserter

copy

surprice

copy

big surprise

copy

fill

fill_n

generate

generate_n

void generate (ForwardIterator, ForwardIterator, Generator);

void generate_n (OutputIterator, Size, Generator);

generate

string generateLabel () {

// generování popisů unikátních řetězců tvaru L_ddd

static int lastLabel = 0;

char labelBuffer[80];

ostrstream ost(labelBuffer, 80);

ost << "L_" << lastLabel++ << '\0';

return string(labelBuffer);

}

void generate_example ()

{

// příklad 1, generování seznamu popisů

list<string> labelList;

generate_n (inserter(labelList, labelList.begin()), 4, generateLabel);

// příklad 2, generování číselných hodnot

vector<int> iVec(10);

generate (iVec.begin(), iVec.end(), iotaGen(2));

generate_n (iVec.begin(), 5, iotaGen(7));

}

generateLabel

L_ddd

lastLabel

generate_n

iotaGen

generate_n

swap

template <class T> void swap (T& a, T& b)

{

T temp(a);

a = b;

b = temp;

}

iter_swap

swap_ranges

ForwardIterator swap_ranges (ForwardIterator first,

ForwardIterator last, ForwardIterator first2);

void swap_example ()

{

// nejprve vytvoříme dvě paralelní sekvence

int data[] = {12, 27, 14, 64}, *datap = data;

vector<int> aVec(4);

generate(aVec.begin(), aVec.end(), iotaGen(1));

// použití swap a iter_swap

swap(data[0], data[2]);

vector<int>::iterator last = aVec.end(); last--;

iter_swap(aVec.begin(), last);

// výměna celých sekvencí

swap_ranges (aVec.begin(), aVec.end(), datap);

}

Vyhledávací rutiny popsané v tomto bodě vrací iterátor, který určuje první prvek odpovídající vyhledávací podmínce. Tuto hodnotu obecně ukládáme do proměnné iterátoru takto:

list<int>::iterator where;

where = find(aList.begin(), aList.end(), 7);

adjacent_find

while ((where = adjacent_find(where, stop)) != stop) {

cout << "double " << *where << " in position "

<< where - start << endl;

++where;

}

find

find_if

InputIterator find_if(InputIterator first,InputIterator last,Predicate);

InputIterator find(InputIterator first,InputIterator last,const T&);

find_if

find

void find_test ()

{

int vintageYears[] = {1967, 1972, 1974, 1980, 1995};

int * start = vintageYears;

int * stop = start + 5;

int * where = find_if (start, stop, isLeapYear);

if (where != stop)

cout << "first vintage leap year is " << *where << endl;

else

cout << "no vintage leap years" << endl;

where = find(start, stop, 1995);

if (where != stop)

cout << "1995 is position " << where - start

<< " in sequence" << endl;

else cout "1995 does not occur in sequence" << endl;

}

adjacent_find

ForwardIterator adjacent_find (ForwardIterator first,

ForwardIterator last [, BinaryPredicate ] );

void adjacent_find_example ()

{

char * text = "The bookkeeper carefully opened the door.";

char * start = text;

char * stop = text + strlen(text);

char * where = start;

cout << "In the text: " << text << endl;

while ((where = adjacent_find(where, stop)) != stop) {

cout << "double " << *where

<< " in position " << where - start << endl;

++where;

}

find_first_of

ForwardIterator1 find_first_of (ForwardIterator1 first1,

ForwardIterator1 last1, ForwardIterator2 first2,

ForwardIterator2 last2 [, BinaryPredicate pred ] );

<first1,last1)

<first2,last2)

void find_test ()

{

int vintageYears[] = {1967, 1972, 1974, 1980, 1995};

int requestedYears[] = [1923, 1970, 1980, 1974 };

int * start = vintageYears;

int * stop = start + 5;

int * where = find_first_of (start, stop,

requestedyears,requestedyears+4 );

if (where != stop)

cout << "first requested vintage year is " << *where << endl;

else cout << "no requested vintage years" << endl;

}

find_first_of

equal

mismatch

search

search_n

ForwardIterator search (ForwardIterator first1,

ForwardIterator last1, ForwardIterator first2,

ForwardIterator last2 [, BinaryPredicate ]);

void search_example ()

{

char * base = "dreams and aspirations";

char * text = "ration";

char * where = search(base, base + strlen(base),

text, text + strlen(text));

if (*where != '\0')

cout << "substring position: " << where - base << endl;

else cout << "substring does not occur in text" << endl;

}

find_end

ForwardIterator find_end (ForwardIterator first1,

ForwardIterator last1, ForwardIterator first2,

ForwardIterator last2 [, BinaryPredicate ]);

void find_end_example ()

{

char * base = "The road less traveled";

char * text = "le";

char * where = find(base, base + strlen(base),

text, text + strlen(text));

if (*where != '\0')

cout << "substring position: " << where - base << endl;

else cout << "substring does not occur in text" << endl;

}

max

min

template <class T> const T& max(const T& a, const T& b[, Compare ]);

template <class T> const T& min(const T& a, const T& b[, Compare ]);

max_element

min_element

ForwardIterator max_element (ForwardIterator first,

ForwardIterator last [, Compare ] );

ForwardIterator min_element (ForwardIterator first,

ForwardIterator last [, Compare ] );

split

void max_min_example ()

{

// vytvoření vektoru náhodných čísel mezi 0 a 99

vector<int> numbers(25);

for (int i = 0; i < 25; i++)

numbers[i] = randomInteger(100);

// výpis maxima

vector<int>::iterator max =

max_element(numbers.begin(), numbers.end());

cout << "largest value was " << * max << endl;

// příklad používající řetězce

string text="It was the best of times, it was the worst of times.";

list<string> words;

split (text, " .,!:;", words);

cout << "The smallest word is "

<< * min_element(words.begin(), words.end())

<< " and the largest word is "

<< * max_element(words.begin(), words.end()) << endl;

}

mismatch

equal

mismatch

pair<InputIterator, InputIterator> mismatch (InputIterator first1,

InputIterator last1, InputIterator first2 [, BinaryPredicate ] );

mismatch_test

mismatch

void mismatch_test (char * a, char * b)

{

pair<char *, char *> differPositions(0, 0);

char * aDiffPosition;

char * bDiffPosition;

if (strlen(a) < strlen(b)) {

// zajištění, že druhý parametr je delší

differPositions = mismatch(a, a + strlen(a), b);

aDiffPosition = differPositions.first;

bDiffPosition = differPositions.second;

}

else {

differPositions = mismatch(b, b + strlen(b), a);

aDiffPosition = differPositions.second;

bDiffPosition = differPositions.first;

}

// porovnání vrácených hodnot

cout << "string " << a;

if (*aDiffPosition == *bDiffPosition)

cout << " is equal to ";

else if (*aDiffPosition < *bDiffPosition)

cout << " is less than ";

else cout << " is greater than ";

cout << b << endl;

}

Následující kategorie algoritmů je používána k modifikaci a transformaci sekvence bez jejího přesunu z jejího původního místa uložení. Některé z nich, jako je replace, zahrnují také kopírovací verzi. Pro ostatní, pokud chceme zachránit originál, si pak musíme vytvořit kopii před zahájením transformace. Např. následuje ukázka otočení vektoru do nově alokovaného vektoru.

vector<int> newVec(aVec.size());

copy (aVec.begin(), aVec.end(), newVec.begin()); // nejprve kopie

reverse (newVec.begin(), newVec.end()); // pak otočení

reverse

void reverse(BidirectionalIterator first,BidirectionalIterator last);

reverse

void reverse_example ()

{

// příklad 1, obracení řetězce

char * text = "Rats live on no evil star";

reverse (text, text + strlen(text));

cout << text << endl;

// příklad 2, obracení seznamu

list<int> iList;

generate_n (inserter(iList, iList.begin()), 10, iotaGen(2));

reverse (iList.begin(), iList.end());

}

replace

replace_if

replace_copy

replace_copy_if

void replace (ForwardIterator first, ForwardIterator last,

const T&, const T&);

void replace_if (ForwardIterator first, ForwardIterator last,

Predicate, const T&);

OutputIterator replace_copy (InputIterator, InputIterator,

OutputIterator, const T&, const T&);

OutputIterator replace_copy (InputIterator, InputIterator,

OutputIterator, Predicate, const T&);

replace

replace_if

void replace_example ()

{

// vytvoření vektoru 0 1 2 3 4 5 4 3 2 1 0

vector<int> numbers(11);

for (int i = 0; i < 11; i++)

numbers[i] = i < 5 ? i : 10 - i;

// nahrazení 3 hodnotou 7

replace (numbers.begin(), numbers.end(), 3, 7);

// nahrazení sudých hodnot hodnotou 9

replace_if (numbers.begin(), numbers.end(), isEven, 9);

// použití kopírovací verze replace

int aList[] = {2, 1, 4, 3, 2, 5};

int bList[6], cList[6], j;

replace_copy (aList, aList+6, &bList[0], 2, 7);

replace_copy_if (bList, bList+6, &cList[0],

bind2nd(greater<int>(), 3), 8);

}

replace_copy

bind2nd

greater

1 2 3 4 5 6 7 8 9 10

7 8 9 10 1 2 3 4 5 6

rotate

void rotate (ForwardIterator first, ForwardIterator middle,

ForwardIterator last);

void rotate_example()

{

// vytvoření seznamu 1 2 3 ... 10

list<int> iList;

generate_n(inserter(iList, iList.begin()), 10, iotaGen(1));

// nalezení místa 7

list<int>::iterator & middle=find(iList.begin(),iList.end(),7);

// rotace okolo tohoto místa

rotate (iList.begin(), middle, iList.end());

// opět rotace okolo stejného místa

list<int> cList;

rotate_copy (iList.begin(), middle, iList.end(),

inserter(cList, cList.begin()));

}

rotate_copy

iList

BidirectionalIterator partition

(BidirectionalIterator, BidirectionalIterator, Predicate);

BidirectionalIterator stable_partition

(BidirectionalIterator, BidirectionalIterator, Predicate);

partition

void partition_example ()

{

// vytvoření vektoru 1 2 3 ... 10

vector<int> numbers(10);

generate(numbers.begin(), numbers.end(), iotaGen(1));

// přesun sudých dopředu a lichých dozadu

vector<int>::iterator result =

partition(numbers.begin(), numbers.end(), isEven);

cout << "middle location " << result - numbers.begin() << endl;

// následuje stabilní rozdělení

generate (numbers.begin(), numbers.end(), iotaGen(1));

stable_partition (numbers.begin(), numbers.end(), isEven);

}

stable_partition

bool next_permutation (BidirectionalIterator first,

BidirectionalIterator last, [ Compare ] );

bool prev_permutation (BidirectionalIterator first,

BidirectionalIterator last, [ Compare ] );

bool nameCompare (char * a, char * b) { return strcmp(a, b) <= 0; }

void permutation_example ()

{

// příklad 1, permutace hodnot 1 2 3

int start [] = { 1, 2, 3};

do

copy (start, start + 3,

ostream_iterator<int,char> (cout, " ")), cout << endl;

while (next_permutation(start, start + 3));

// příklad 2, permutace slov

char * words = {"Alpha", "Beta", "Gamma"};

do

copy (words, words + 3,

ostream_iterator<char *,char> (cout, " ")), cout << endl;

while (next_permutation(words, words + 3, nameCompare));

// příkladle 3, zpětná permutace znaků

char * word = "bela";

do

cout << word << ' ';

while (prev_permutation (word, &word[4]));

cout << endl;

}

inplace_merge

void inplace_merge (BidirectionalIterator first,

BidirectionalIterator middle,

BidirectionalIterator last [, BinaryFunction ] );

inplate_merge

find

inplace_merge

void inplace_merge_example ()

{

// generování sekvence 0 2 4 6 8 1 3 5 7 9

vector<int> numbers(10);

for (int i = 0; i < 10; i++)

numbers[i] = i < 5 ? 2 * i : 2 * (i - 5) + 1;

// hledání 1

vector<int>::iterator midvec =

find(numbers.begin(), numbers.end(), 1);

// kopírování do seznamu

list<int> numList;

copy (numbers.begin(), numbers.end(),

inserter (numList, numList.begin()));

list<int>::iterator midList =

find(numList.begin(), numList.end, 1);

// spojování seznamů do jednoho

inplace_merge (numbers.begin(), midvec, numbers.end());

inplace_merge (numList.begin(), midList, numList.end());

}

random_shuffle

deque

void random_shuffle (RandomAccessIterator first,

RandomAccessIterator last [, Generator ] );

m-1

generate

void random_shuffle_example ()

{

// vytvoření vektoru 1 2 3 ... 10

vector<int> numbers;

generate(numbers.begin(), numbers.end(), iotaGen(1));

// náhodné přeházení prvků

random_shuffle (numbers.begin(), numbers.end());

// zopakování s poskytnutím generátoru náhodných čísel

struct RandomInteger {

{

operator() (int m) { return rand() % m; }

} random;

random_shuffle (numbers.begin(), numbers.end(), random);

}

Následující algoritmy odstraňují hodnoty ze sekvence. Přesouvají zbývající hodnoty na začátek sekvence a vracejí iterátor určující, kde sekvence končí. Hodnoty za iterátorem mohou být zrušeny (např. metodou erase). Podívejme se na jednoduchý příklad. Předpokládejme, že chceme odstranit sudé prvky ze sekvence 1 2 3 4 5 6 7 8 9 10, a tedy použijeme algoritmus remove_if, který mám dodá:

1 3 5 7 9 | 6 7 8 9 10

remove_if

remove

find

ForwardIterator remove

(ForwardIterator first, ForwardIterator last, const T &);

ForwardIterator remove_if

(ForwardIterator first, ForwardIterator last, Predicate);

remove

OutputIterator remove_copy(InputIterator first,InputIterator last,

OutputIterator result, const T &);

OutputIterator remove_copy_if(InputIterator first,InputIterator last,

OutputIterator result, Predicate);

remove

void remove_example ()

{

// vytvoření seznamu čísel

int data[] = {1, 2, 4, 3, 1, 4, 2};

list<int> aList;

copy (data, data+7, inserter(aList, aList.begin()));

// odstranění 2, kopírování do seznamu

list<int> newList;

remove_copy (aList.begin(), aList.end(),

back_inserter(newList), 2);

// odstranění 2 na místě

list<int>::iterator where;

where = remove (aList.begin(), aList.end(), 2);

aList.erase(where, aList.end());

// odstranění všech sudých hodnot

where = remove_if (aList.begin(), aList.end(), isEven);

aList.erase(where, aList.end());

}

unique

ForwardIterator unique (ForwardIterator first,

ForwardIterator last [, BinaryPredicate ] );

OutputIterator unique_copy(InputIterator first,InputIterator last,

OutputIterator result [, BinaryPredicate ] );

void unique_example ()

{

int data[] = {1, 3, 3, 2, 2, 4};

list<int> aList;

set<int> aSet;

copy (data, data+6, inserter(aList, aList.begin()));

// kopírování unikátních prvků do množiny

unique_copy(aList.begin(),aList.end(),inserter(aSet,aSet.begin()));

// unikátní prvky na místě

list<int>::iterator where;

where = unique(aList.begin(), aList.end());

// odstranění zbývajících hodnot

aList.erase(where, aList.end());

}

Následující kategorie algoritmů jsou ty, které redukují celou sekvenci na jednu skalární hodnotu. Nezapomeňte, že algoritmy accumulate a inner_product jsou deklarovány v hlavičkovém souboru numeric.

count

count_if

iterator_traits<InputIterator>::distance_type

count (InputIterator first, InputIterator last, const T& value);

iterator_traits<InputIterator>::distance_type

count_if (InputIterator first, InputIterator last, Predicate pred);

void count(InputIterator first,InputIterator last,const T&,Size &);

void count_if(InputIterator first,InputIterator last,Predicate,Size &);

count

count_if

void count_example ()

{

int eCount = 0;

int vowelCount = 0;

char * text = "Now is the time to begin";

count (text, text + strlen(text), 'e', eCount);

count_if (text, text + strlen(text), isVowel, vowelCount);

cout << "There are " << eCount << " letter e's " << endl

<< "and " << vowelCount << " vowels in the text:"

<< text << endl;

}

accumulate

ContainerType accumulate (InputIterator first, InputIterator last,

ContainerType initial [, BinaryFunction ] );

accumulate

void accumulate_example ()

{

int numbers[] = {1, 2, 3, 4, 5};

// Příklad 1, pouhý součet

int sum = accumulate (numbers, numbers + 5, 0);

int product = accumulate (numbers, numbers + 5, 1, times<int>());

cout << "The sum of the first five integers is " << sum << endl;

cout << "The product is " << product << endl;

// Příklad 2, s různými typy pro počáteční hodnotu

list<int> nums;

nums = accumulate (numbers, numbers+5, nums, intReplicate);

}

list<int>& intReplicate (list<int>& nums, int n)

// přidání sekvence od n k 1 na konec seznamu

{

while (n) nums.push_back(n--);

return nums;

}

ContainerType inner_product(InputIterator first1,InputIterator last1,

InputIterator first2, ContainerType initialValue

[ , BinaryFunction add, BinaryFunction times ] );

accumulate

true

false

equal

void inner_product_example ()

{

int a[] = {4, 3, -2};

int b[] = {7, 3, 2};

// příklad 1, jednoduchý vnitřní produkt

int in1 = inner_product(a, a+3, b, 0);

cout << "Inner product is " << in1 << endl;

// příklad 2, uživatelem definované operace

bool anyequal = inner_product(a, a+3, b, true,

logical_or<bool>(), equal_to<int>());

cout << "any equal? " << anyequal << endl;

}

equal

bool equal (InputIterator first, InputIterator last,

InputIterator first2 [, BinaryPredicate] );

equal

true

greater_equal

true

void equal_example ()

{

int a[] = {4, 5, 3};

int b[] = {4, 3, 3};

int c[] = {4, 5, 3};

cout << "a = b is: " << equal(a, a+3, b) << endl;

cout << "a = c is: " << equal(a, a+3, c) << endl;

cout << "a pair-wise greater-equal b is: "

<< equal(a, a+3, b, greater_equal<int>()) << endl;

}

lexicographical_compare

true

false

bool lexicographical_compare(InputIterator first1,InputIterator last1,

InputIterator first2, InputIterator last2 [, BinaryFunction ] );

void lexicographical_compare_example()

{

char * wordOne = "everything";

char * wordTwo = "everybody";

cout << "compare everybody to everything " <<

lexicographical_compare(wordTwo, wordTwo + strlen(wordTwo),

wordOne, wordOne + strlen(wordOne)) << endl;

int a[] = {3, 4, 5, 2};

int b[] = {3, 4, 5};

int c[] = {3, 5};

cout << "compare a to b:" <<

lexicographical_compare(a, a+4, b, b+3) << endl;

cout << "compare a to c:" <<

lexicographical_compare(a, a+4, c, c+2) << endl;

}

Dále se budeme zabývat algoritmy použitelnými pro generování nové sekvence z existující sekvence provedením nějakého typu transformace. Výstupní sekvence je většinou popsána výstupním operátorem. Jako alternativa může být také použit vkládací iterátor. Algoritmy partial_sum a adjacent_difference jsou deklarovány v hlavičkovém souboru numeric.

transform

OutputIterator transform (InputIterator first, InputIterator last,

OutputIterator result, UnaryFunction);

OutputIterator transform (InputIterator first1, InputIterator last1,

InputIterator first2, OutputIterator result, BinaryFunction);

int square(int n) { return n * n; }

void transform_example ()

{

// generování seznamu hodnot od 1 do 6

list<int> aList;

generate_n (inserter(aList, aList.begin()), 6, iotaGen(1));

// transformace prvků umocněním, kopírování do vektoru

vector<int> aVec(6);

transform (aList.begin(), aList.end(), aVec.begin(), square);

// transformace vektoru na místě, opět použita mocnina

transform (aVec.begin(), aVec.end(), aVec.begin(), square);

// paralelní transformace

vector<int> cubes(6);

transform (aVec.begin(), aVec.end(), aList.begin(),

cubes.begin(), divides<int>());

}

OutputIterator partial_sum (InputIterator first, InputIterator last,

OutputIterator result [, BinaryFunction] );

void partial_sum_example ()

{

// generování hodnot od 1 do 5

vector<int> aVec(5);

generate (aVec.begin(), aVec.end(), iotaGen(1));

// výstup částečných součtů

partial_sum (aVec.begin(), aVec.end(),

ostream_iterator<int> (cout, " ")), cout << endl;

// výstup částečných součinů

partial_sum (aVec.begin(), aVec.end(),

ostream_iterator<int> (cout, " "), times<int>() );

}

OutputIterator adjacent_difference (InputIterator first,

InputIterator last, OutputIterator result [, BinaryFunction ]);

void adjacent_difference_example ()

{

vector<int> aVec(5);

generate (aVec.begin(), aVec.end(), iotaGen(1));

// výstup sousedních rozdílů

adjacent_difference (aVec.begin(), aVec.end(),

ostream_iterator<int,char> (cout, " ")), cout << endl;

// výstup sousedních součtů

adjacent_difference (aVec.begin(), aVec.end(),

ostream_iterator<int,char> (cout, " "), plus<int>() );

}

Ve standardní knihovně zbývá ještě několik algoritmů. Algoritmus for_each přebírá tři parametry. První dva jsou iterátory popisující vyhodnocovanou sekvenci, třetí je unární funkce. Algoritmus aplikuje tuto funkci na každou hodnotu sekvence.

function for_each(InputIterator first, InputIterator last, Function);

print_if_leap

cout << "leap years between 1990 and 1997 are: ";

for_each (1990, 1997, print_if_leap);

cout << endl;

for_each

int vintageYears[] = {1947, 1955, 1960, 1967, 1994};

...

cout << "vintage years which were also leap years are: ";

for_each (vintageYears, vintageYears + 5, print_if_leap);

cout << endl;

countCaps

int capCount = 0;

void countCaps(char c) { if (isupper(c)) capCount++; }

string advice = "Never Trust Anybody Over 30!";

for_each(advice.begin(), advice.end(),countCaps);

cout << "upper-case letter count is " << capCount << endl;

Nyní se začneme zabývat popisem obecných algoritmů ze standardní knihovny, které jsou určené pro řazené kolekce. Jejich popis je uveden v následující tabulce:

Jméno	Popis
	Řadící algoritmy
sort	Řazení sekvence.
stable_sort	Řazení sekvence se zachováním pořadí ekvivalentních prvků.
partial_sort	Řazení pouze části sekvence.
partial_sort_copy	Částečné řazení s kopírováním.
	Hledání n-tého největšího prvku
nth_element	Lokalizace n-tého největšího prvku.
	Binární hledání
binary_search	Vyhledávání, návrat logické hodnoty.
lower_bound	Vyhledávání, návrat první pozice.
upper_bound	Vyhledávání, návrat poslední pozice.
equal_range	Vyhledávání, návrat obou pozic.
	Slučování řazených sekvencí
merge	Sloučení dvou seřazených sekvencí.
	Množinové operace
set_union	Sjednocení dvou množin
set_intersection	Průnik dvou množin.
set_difference	Rozdíl dvou množin.
set_symmetric_difference	Symetrický rozdíl dvou množin.
includes	Zjištění, zda množina je podmnožinou jiné množiny.
	Operace s hromadou
make_heap	Změna sekvence na hromadu.
push_heap	Přidání nové hodnoty do hromady
pop_heap	Odstranění největší hodnoty z hromady
sort_heap	Změna hromady na řazenou kolekci

Řazené kolekce mohou být vytvářeny pomocí standardní knihovny různými způsoby. Např.

Kontejnery množin a mapování jsou řazené kolekce určené definicí.
Seznam může být seřazen vyvoláním metody sort.
Vektor, deque nebo normální pole C++ mohou být řazeny pomocí některého řadícího algoritmu popsaného déle.

Compare

algorithm

# include <algorithm>

Jsou dva základní řadící algoritmy poskytnuté standardní knihovnou:

void sort (RandomAccessIterator first,

RandomAccessIterator last [, Compare ] );

void stable_sort (RandomAccessIterator first,

RandomAccessIterator last [, Compare ] );

sort

stable_sort

deque

sort

void sort_example ()

{

// naplnění vector a deque náhodnými čísly

vector<int> aVec(15);

deque<int> aDec(15);

generate (aVec.begin(), aVec.end(), randomValue);

generate (aDec.begin(), aDec.end(), randomValue);

// vzestupné řazení vektoru

sort (aVec.begin(), aVec.end());

// sestupné řazaní deque

sort (aDec.begin(), aDec.end(), greater<int>() );

// aternativní způsob sestupného řazení

sort (aVec.rbegin(), aVec.rend());

}

partial_sort

void partial_sort(RandomAccessIterator first,RandomAccessIterator middle,

RandomAccessIterator last [ , Compare ]);

RandomAccessIterator partial_sort_copy(InputIterator first,

InputIterator last, RandomAccessIterator result_first,

RandomAccessIterator result_last [, Compare ] );

partial_sort_copy

void partial_sort_example ()

{

// vytvoření vektoru 15 celých náhodných čísel

vector<int> aVec(15);

generate (aVec.begin(), aVec.end(), randomValue);

// částečné seřazení prvních sedmi pozic

partial_sort (aVec.begin(), aVec.begin() + 7, aVec.end());

// vytvoření seznamu náhodných čísel

list<int> aList(15, 0);

generate (aList.begin(), aList.end(), randomValue);

// seřazení pouze prvních sedmi prvků

vector<int> start(7);

partial_sort_copy (aList.begin(), aList.end(),

start.begin(), start.end(), greater<int>());

}

Předpokládejme, že máme sekvenci 2 5 3 4 7 a potřebujeme zjistit prostřední prvek (medián). Můžeme to provést funkcí nth_element. Jeden výsledek může být následující sekvence:

3 2 | 4 | 7 5

nth_element

nth

void nth_element(RandomAccessIterator first,RandomAccessIterator nth,

RandomAccessIterator last [, Compare ] );

void nth_element_example ()

{

vector<int> aVec(10);

generate (aVec.begin(), aVec.end(), randomValue);

vector<int>::iterator nth = aVec.begin() + 4;

nth_element (aVec.begin(), nth, aVec.end());

cout << "fifth largest is " << *nth << endl;

}

Standardní knihovna poskytuje několik různých variant algoritmu binárního vyhledávání. Všechny provádějí pouze přibližně log n porovnávání, kde n je počet prvků v rozsahu popsaném parametry. Algoritmus pracuje dobře s iterátory náhodného přístupu, které poskytuje vektor nebo deque. Pracuje také s iterátory nenáhodného přístupu, které jsou generované seznamy (v tomto případě je použito lineární vyhledávání). Binární vyhledávání není nutno provádět na množinách nebo multiset, neboť tyto třídy kontejnerů poskytují vlastní vyhledávací algoritmy, které jsou mnohem efektivnější.

binary_search

true

Compare(value, arg)

Compare(arg, value)

false

bool binary_search (ForwardIterator first, ForwardIterator last,

const T & value [, Compare ] );

ForwardIterator lower_bound (ForwardIterator first,

ForwardIterator last, const T& value [ , Compare ] );

ForwardIterator upper_bound (ForwardIterator first,

ForwardIterator last, const T& value [, Compare ] );

pair<ForwardIterator,ForwardIterator> equal_range(ForwardIterator first,

ForwardIterator last, const T& value [, Compare ] );

lover_bound

upper_bound

equal_range

void binary_search_example ()

{

// vytvoření seřazeného vektoru 15 náhodných čísel

vector<int> aVec(15);

generate (aVec.begin(), aVec.end(), randomValue);

sort (aVec.begin(), aVec.end());

// zjištění zda kontejner obsahuje 11

if (binary_search (aVec.begin(), aVec.end(), 11))

cout << "contains an 11" << endl;

else

cout << "does not contain an 11" << endl;

// vložení 11 a 14

vector<int>::iterator where;

where = lower_bound (aVec.begin(), aVec.end(), 11);

aVec.insert (where, 11);

where = upper_bound (aVec.begin(), aVec.end(), 14);

aVec.insert (where, 14);

}

Algoritmus merge kombinuje dvě seřazené sekvence do tvaru nové seřazené sekvence. Velikost výsledku je součet velikostí předaných sekvencí. To je v kontrastu s operací set_union, která eliminuje prvky, které jsou opakovaně v obou množinách. Dvě sekvence jsou popsány dvojicí iterátorů, zatímco výsledek jedním výstupním iterátorem.

OutputIterator merge (InputIterator first1, InputIterator last1,

InputIterator first2, InputIterator last2,

OutputIterator result [, Compare ]);

void merge_example ()

{

// vytvoření seznamu a vektoru 10 náhodných čísel

vector<int> aVec(10);

list<int> aList(10, 0);

generate (aVec.begin(), aVec.end(), randomValue);

sort (aVec.begin(), aVec.end());

generate_n (aList.begin(), 10, randomValue);

aList.sort();

// sloučení do vektoru

vector<int> vResult (aVec.size() + aList.size());

merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),

vResult.begin());

// sloučení do seznamu

list<int> lResult;

merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),

inserter(lResult, lResult.begin()));

// sloučení na výstup

merge (aVec.begin(), aVec.end(), aList.begin(), aList.end(),

ostream_iterator<int,char> (cout, " "));

cout << endl;

}

S množinovými operacemi pro třídu set jsme se již seznámili. Algoritmy implementující tyto operace jsou obecné a aplikovatelné na libovolné řazené datové struktury. Algoritmy předpokládají, že vstupní rozsahy jsou řazené kolekce, které reprezentují multiset; tj. prvky se mohou opakovat. Pokud vstupy jsou reprezentované množinami, pak výstup bude také množina.

OutputIterator set_union(InputIterator first1,InputIterator last1,

InputIterator first2, InputIterator last2,

OutputIterator result [, Compare ] );

set_union

set_intersection

set_difference

set_symmetric_difference

merge

includes

true

false

void set_example ()

{

ostream_iterator<int> intOut (cout, " ");

// vytvoření dvou řazených seznamů

list<int> listOne, listTwo;

generate_n (inserter(listOne, listOne.begin()), 5, iotaGen(1));

generate_n (inserter(listTwo, listTwo.begin()), 5, iotaGen(3));

// sjednocení

set_union (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end(), intOut), cout << endl;

// slučování

merge (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end(), intOut), cout << endl;

// průnik

set_intersection (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end(), intOut), cout << endl;

// rozdíl

set_difference (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end(), intOut), cout << endl;

// symetrický rozdíl

set_symmetric_difference (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end(), intOut), cout << endl;

if (includes (listOne.begin(), listOne.end(),

listTwo.begin(), listTwo.end()))

cout << "set is subset" << endl;

else

cout << "set is not subset" << endl;

}

2 * i + 1

2 * i + 2

priority_queue

make_heap

void make_heap (RandomAccessIterator first,

RandomAccessIterator last [, Compare ]);

push_back

push_heap

void push_heap (RandomAccessIterator first,

RandomAccessIterator last [, Compare ]);

pop_heap

void pop_heap (RandomAccessIterator first,

RandomAccessIterator last [, Compare ]);

sort_heap

void sort_heap (RandomAccessIterator first,

RandomAccessIterator last [, Compare ]);

void heap_example ()

{

// vytvoření hromady 15 náhodných čísel

vector<int> aVec(15);

generate (aVec.begin(), aVec.end(), randomValue);

make_heap (aVec.begin(), aVec.end());

cout << "Largest value " << aVec.front() << endl;

// odstranění největšího prvku

pop_heap (aVec.begin(), aVec.end());

aVec.pop_back();

// přidání 97 k hromadě

aVec.push_back (97);

push_heap (aVec.begin(), aVec.end());

// převedení do řazené kolekce

sort_heap (aVec.begin(), aVec.end());

}

Rozhraní standardních alokátorů zaobaluje typy a funkce potřebné ke správě ukládání dat obecným způsobem. Rozhraní poskytuje:

typy ukazatele a odkazu
typ rozdílu mezi ukazateli
typ pro libovolnou velikost objektu
ukládací alokace a dealokace
konstrukce a destrukce objektu

new

delete

my_allocator alloc<int>; // vytvoření alokátoru

vector<int,my_allocator<int> > v(alloc); // Použití alokátoru

allocator<T>

Allocator

template <class T> class my_alloc;

list <int, allocator<int> > my_list(my_alloc()); // Chyba!

list <int, my_alloc<int> > my_list(my_alloc());

Definování našich vlastních alokátorů je relativně jednoduchý proces. Standardní knihovna obsahuje jisté rozhraní obsahující typy a funkce. Alokátor, který vytváříme musí syntakticky vyhovovat těmto metodám a typům. Standardní knihovna také specifikuje část sémantiky pro typ alokátoru.

my_allocator

template <class T>

class my_allocator

{

typedef implementation_defined size_type;

typedef implementation_defined difference_type

typedef implementation_defined pointer;

typedef implementation_defined const_pointer;

typedef implementation_defined reference;

typedef implementation_defined const_reference;

typedef implementation_defined value_type;

template <class U>
struct rebind { typedef allocator other; };
Každý typ ukazatele v tomto rozhraní musí mít konverzi na void*. Musí být možno použít výsledek void* jako hodnotu this v konstruktoru a destruktoru a v převodech na B<void>::pointer (pro příslušné B) pro použití v B::deallocate().
Metoda rebind umožňuje kontejneru vytvářet alokátor pro některé typy poskytnuté jako parametr šablony. Např. kontejner seznamu získává implicitně allocator<T>, ale seznam také potřebuje alokovat list_nodes. Kontejner může vytvořit alokátor pro list_nodes mimo alokátor pro T takto:
Allocator::rebind<list_node>::other list_node_allocator;
Následuje popis metod, které alokátor standardní knihovny musí poskytovat:
my_allocator();
template <class U>
my_allocator(const my_allocator&);
template <class U>
operator=(const my_allocator&);
~my_allocator();
 Konstruktory a destruktor.
pointer address(reference r) const;
 Vrací adresu r jako typ pointer. Tato a následující funkce jsou použity pro převod odkazů na ukazatele.
const_pointer address(const_reference r) const;
 Vrací adresu r jako typ const_pointer.
pointer allocate(size_type n);
 Alokuje místo pro n hodnot T.
template <class T, class U>
types<T>::pointer allocate(size_type n,
 typename my_allocator<void>::const_pointer hint = 0);
 Alokuje místo pro hint hodnot T.
void deallocate(pointer);
 Dealokace místa získaného voláním allocate.
size_type max_size();
 Vrací největší možné místo dostupné pro volání allocate.
void construct(pointer p, const T& val);
 Vytváří objekt typu T na místě p. Efekt je: new((void*)p) T(u);
void destroy(pointer p);
 Volá destruktor na hodnotu určenou p. Efekt je: ((T*)p)->~T()
Následuje popis funkcí (ne metod), které alokátor standardní knihovny musí poskytnout:
template <class T>
my_allocator::pointer
operator new(my_allocator::size_type, my_allocator&);
 Alokuje místo pro jeden objekt typu T pomocí my_allocator::allocate. Efekt je: new((void*)x.template allocate<T>(1)) T;
template <class T, class U>
bool operator==(const my_allocator<T>& a, const my_allocator& b);
 Vrací true, pokud alokátory b a a mohou být úspěšně zaměněny (tj. b může být použit k dealokaci a a naopak).
template <class T, class U>
bool operator!=(const my_allocator<T>& a, const my_allocator& b);
 Vrací !(a == b).
Rogue Wave poskytuje alternativní rozhraní alokátoru pro ty překladače, které nepodporují šablony tříd a šablony metod. Tím se ale zabývat nebudeme.

Standardní knihovna poskytuje množinu tříd pro oznamování chyb. Tyto třídy používají služby zpracování výjimek. Knihovna implementuje jistý model chyb, ve kterém chyby dělíme do dvou kategorií: na logické a běhové chyby.

stdexcept

#include <stdexcept>

exception

logic_error

domain_error

invalid_argument

length_error

out_of_range

runtime_error

range_error

overflow_error

underflow_error

logic_error

runtime_error

exception

logic_error

runtime_error

insert

string s;

int n;

...

try

{

s.insert(n,"Howdy");

}

catch (const exception& e)

{

// práce s výjimkou

}

...

if (n > max)

throw out_of_range("Your past the end, bud");

exception

what

catch

exception

throw exception;

class bad_packet_error : public runtime_error

{

public:

bad_packet_error(const string& what);

};

if (bad_packet())

throw bad_packet_error("Packet size incorrect");

exceptn.cpp

#include <stdexcept>

#include <string>

static void f() { throw runtime_error("a runtime error"); }

int main ()

{

string s;

try

{

s.replace(100,1,1,'c');

}

catch (const exception& e)

{

cout << "Got an exception: " << e.what() << endl;

}

try

{

f();

}

catch (const exception& e)

{

cout << "Got an exception: " << e.what() << endl;

}

return 0;

}

Třída auto_prt zaobaluje libovolný ukazatel získaný pomocí new a poskytuje automatické zrušení tohoto ukazatele. Ukazatel zaobalený objektem auto_ptr je zrušen, když sám auto_ptr je uvolněn. Pro přístup k této třídě je nutno vložit hlavičkový soubor memory:

#include <memory>

auto_ptr

reset

auto_ptr

auto_ptr<string> a(new string);

auto_ptr

auto_ptr<string> b = a;

auto_ptr

operator*

operator->

get

*b = "What's up Doc";

*(b.get()) = "What's up Doc";

b->assign("What's up Doc");

auto_ptr

release

auto_ptr

release

auto_ptr

autoptr.cpp

#include <vector>

#include <memory>

#include <string>

int main()

{

// první chybný způsob

vector<string*> v;

v.insert(v.begin(), new string("Florence"));

v.insert(v.begin(), new string("Milan"));

v.insert(v.begin(), new string("Venice"));

// nyní odstraníme první prvek

v.erase(v.begin());

// řetězec("Venice") je odstraněn, ale není zrušen

}

{

// nyní správný způsob

vector<auto_ptr<string> > v;

v.insert(v.begin(), auto_ptr<string>(new string("Florence")));

v.insert(v.begin(), auto_ptr<string>(new string("Milan")));

v.insert(v.begin(), auto_ptr<string>(new string("Venice")));

// nyní odstraníme první prvek

v.erase(v.begin());

// vše v pořádku

}

return 0;

}

31. Knihovna standardních šablon III