10. Stl - Partea II

7/29/2019 10. Stl - Partea II

http://slidepdf.com/reader/full/10-stl-partea-ii 1/44

1

STL

Partea 2

7/29/2019 10. Stl - Partea II


D. Lucanu STL – Partea 2 2

Cuprins

STL C++

• containere standard

• algoritmi

• clasificare

• exemple:• liste

• tablouri asociative

•agenda telefonica

• functori (obiecte functii)

7/29/2019 10. Stl - Partea II



STL :: algoritmi

definitie (in STL): un set de template-uri care

actioneaza asupra secventelor de elemente

clasificare

• Nonmodifying algorithms

• Modifying algorithms

• Removing algorithms

• Mutating algorithms

• Sorting algorithms• Sorted range algorithms

• Numeric algorithms

7/29/2019 10. Stl - Partea II



STL: algoritmi care nu modifica

for_each() Performs an operation for each element

count() Returns the number of elements

count_if() Returns the number of elements that

match a criterion

min_element() Returns the element with the

smallest value

max_element() Returns the element with the

largest value

find() Searches for the first element with the passed

value

find_if() Searches for the first element that matches

a criterion

7/29/2019 10. Stl - Partea II



STL: algoritmi care nu modifica

search_n() Searches for the first n consecutive elements with

certain properties search() Searches for the first occurrence of a subrange

find_end() Searches for the last occurrence of a subrange

find_first_of() Searches the first of several possible elements

adjacent_find() Searches for two adjacent elements that areequal(by some criterion)

equal() Returns whether two ranges are equal

mismatch() Returns the first elements of two sequences that

differ lexicographical_compare() Returns whether a range is

lexicographically less than another range

7/29/2019 10. Stl - Partea II



STL: algoritmi care modifica

for_each() Performs an operation for each element

copy() Copies a range starting with the first element

copy _backward() Copies a range starting with the

last element

transform() Modifies (and copies) elements;

combines elements of two ranges

merge() Merges two ranges

swap_ranges() Swaps elements of two ranges

fill() Replaces each element with a given value fill_n() Replaces n elements with a given value

7/29/2019 10. Stl - Partea II



STL: algoritmi care elimina

remove() Removes elements with a given value

remove_if() Removes elements that match a given

criterion

remove_copy() Copies elements that do not match

a given value

remove_copy_if() Copies elements that do not

match a given criterion

unique() Removes adjacent duplicates (elements

that are equal to their predecessor)

unique_copy() Copies elements while removing

adjacent duplicates

7/29/2019 10. Stl - Partea II



STL: algoritmi care schimba ordinea

reverse() Reverses the order of the elements

reverse_copy() Copies the elements while

reversing their order

rotate() Rotates the order of the elements

rotate_copy() Copies the elements while rotating

their order

next_permutation() Permutates the order of the

elements

prev_permutation() Permutates the order of the

elements

7/29/2019 10. Stl - Partea II



STL: algoritmi care schimba ordinea

random_shuffle() Brings the elements into a

random order

partition() Changes the order of the elements so

that elements that match a criterion are at the front

stable_partition() Same as partition() but preserves

the relative order of matching and nonmatchingelements

7/29/2019 10. Stl - Partea II



STL: algoritmi care modifica

generate() Replaces each element with the result of

an operation

generate_n() Replaces n elements with the result of

an operation

replace() Replaces elements that have a special

value with another value

replace_if() Replaces elements that match a

criterion with another value

replace_copy() Replaces elements that have a

special value while copying the whole range

replace_copy_if() Replaces elements that match a

criterion while copying the whole range

7/29/2019 10. Stl - Partea II



STL: algoritmi de sortare

sort() Sorts all elements

stable_sort() Sorts while preserving order of equal

elements

partial_sort() Sorts until the first n elements are

correct

partial_sort_copy() Copies elements in sorted

order

nth_element() Sorts according to the nth position

partition() Changes the order of the elements so

that elements that match a criterion are at the front

7/29/2019 10. Stl - Partea II



STL: algoritmi de sortare

stable_partition() Same as partition() but preserves

the relative order of matching and nonmatchingelements

make_heap() Converts a range into a heap

push_heap() Adds an element to a heap

pop_heap() Removes an element from a heap

sort_heap() Sorts the heap (it is no longer a heap

after the call)

7/29/2019 10. Stl - Partea II



STL: algoritmi pe intervale sortate

binary_search() Returns whether the range

contains an element includes() Returns whether each element of a

range is also an element of another range

lower_bound() Finds the first element greater thanor equal to a given value

upper _bound() Finds the first element greater thana given value

equal_range() Returns the range of elements equalto a given value

merge() Merges the elements of two ranges

set_union() Processes the sorted union of tworanges

7/29/2019 10. Stl - Partea II



STL: algoritmi de sortare pe intervale

set_intersection() Processes the sorted intersection

of two ranges

set_difference() Processes a sorted range that

contains all elements of a range that are not part of

another

set_symmetric_difference() Processes a sortedrange that contains all elements that are in exactly

one of two ranges

inplace_merge() Merges two consecutive sorted

ranges

7/29/2019 10. Stl - Partea II



STL: algoritmi numerici

accumulate() Combines all element values

(processes sum, product, and so forth)

inner_product() Combines all elements of two

ranges

adjacent_difference() Combines each element with

its predecessor

partial_sum() Combines each element with all of its

predecessors

7/29/2019 10. Stl - Partea II



STL :: algoritmi::liste

header

#include <algorithm> declarare lista

list<string> amici;

afisare componentelor listei

void print_string(string s){

cout << s << endl;

}

//... p = amici.begin();

q = amici.end();

for_each(p, q, print_string);

7/29/2019 10. Stl - Partea II



STL :: algoritmi::liste

numara Popestii

int n = count(p, q, "Popescu"); cauta dupa criteriu

• defineste criteriu (rau = nu incepe cu litera)

int bad(const string& s)

{

return !isalpha(s[0]);

}

•insereaza un element rau

amici.insert(q, "12cai");

• gaseste primul element rau (care nu incepe cu litera)

p = find_if(amici.begin(), amici.end(), bad );

7/29/2019 10. Stl - Partea II



STL :: inseratori

fie functia:

void f(list<int>& li)

{

fill_n(li.begin(), 100, 77);

}

f() atribuie 77 elementelor li[0], ..., li[99]

dar daca sunt mai putin de 100 de elemente?

7/29/2019 10. Stl - Partea II



STL :: inseratori

in <iterator> exista trei clase parametrizate create pentru a

rezolva astfel de probleme template <class Cont>

back_insert_iterator<Cont>

back_inserter(Cont& c);

template <class Cont>

front_insert_iterator<Cont>

front_inserter(Cont& c);

template <class Cont>

insert_iterator<Cont>

inserter(Cont& c, Out p);

7/29/2019 10. Stl - Partea II



STL :: inseratori

adaugarea de elemente la sfarsit:

void g(list<int>& li){

fill_n(back_inserter(li), 100, 77);

}

// se vor adauga 100 copii ale lui 77 la sf. inserare mai simpla

insert_inserator<list<int>> ii(li, p);

...

*ii = 55;// este echivalent cu

li.insert(p, 55)

7/29/2019 10. Stl - Partea II



STL :: algoritmi::liste (cont)

// creeaza o copie numai cu unicate

list<string> copie;unique_copy(amici.begin(), amici.end(), \

back_inserter(copie));

amici = copie;

inserarea unei liste in alta listalist<string> temp;

temp.push_back("Albu");

//...

q = find(amici.begin(), amici.end(), "Popescu");copy(temp.begin(), temp.end(), \

inserter(amici, q));

7/29/2019 10. Stl - Partea II



STL :: algoritmi::map

clasa Persoana

class Persoana {//. . .friend bool operator<(const Persoana& lhs, \

const Persoana& rhs);//...

}; clasa Info (despre persoana) class Info {// . . .

private:string adr;string nr;

};

7/29/2019 10. Stl - Partea II




declarare agenda telefonica

multimap<Persoana, Info> agTel; afisare agenda

• afisare intrare

void print_intrare(pair<Persoana, Info> p)

{cout << p.first.getNume() // ...;

}

• apelare alg. for_each()

p = agTel.begin();q = agTel.end();

for_each(p, q, print_intrare);

7/29/2019 10. Stl - Partea II




numara Popestii

• declarare criteriu

bool eqPopescu(pair<Persoana, Info> p)

{

return p.first.getNume() =="Popescu";

}

• apelare algoritm count_if()

p = agTel.begin();q = agTel.end();

cout << count_if(p, q, eqPopescu);

7/29/2019 10. Stl - Partea II



STL::ex:: agenda telefonica

cheia va fi un nume

typedef std::string Nume; clasa AgTel deriveaza din multimap<>class AgTel : public std::multimap<Nume, Info> {

public:

AgTel (); AgTel(char* numeFisier);void adIntrare();void afiseazaTot();void incarca(char* numeFisier);

void salveaza(char* numeFisier);//. . .

};

7/29/2019 10. Stl - Partea II




memorarea agendei in fisier

• fiecare intrare este memorata pe 3 linii:

<nume>

<adresa>

<numar tel>

• fisierul va avea 3*nr_intrari linii

7/29/2019 10. Stl - Partea II




void AgTel::incarca(char* numeFisier) {

//... bool ok = std::getline(inp, nume); while(ok){ok = std::getline(inp, adr);

//...if (ok)

this->insert(end(),std::make_pair(nume,Info(adr, nr)));

ok = std::getline(inp, nume);}inp.close();

}

7/29/2019 10. Stl - Partea II




void AgTel::adIntrare()

{

//...

std::cout << "Nume: ";

std::cin >> s;

Nume nume(s);

//...

this->insert(end(), \

std::make_pair(nume, info));}

7/29/2019 10. Stl - Partea II




void AgTel::salveaza(char *numeFisier)

{std::ofstream out(numeFisier);

AgTel::iterator i;

for (i=this->begin(); i!=this->end(); ++i)

{out << i-> first << std::endl;

out << i->second.getAdr() << std::endl;

out << i->second.getNr() << std::endl;

}out.close();

}

7/29/2019 10. Stl - Partea II



STL::ex:: agenda telefonica:: demo

int main()

{int optiune;

AgTel agTel;

do {

std::cout << "1. Initializeaza ...”; //. . .

std::cout << "0. Terminare.\n";

std::cin >> optiune;

7/29/2019 10. Stl - Partea II



STL::ex:: agenda telefonica:: demo

switch (optiune)

{case 1:

agTel.clear();

break;

case 4:agTel.salveaza("test.at");

break;

//. . .

}} while (optiune != 0);

return 0;

}

7/29/2019 10. Stl - Partea II



Obiecte de tip functie

A function object (or functor), is an object that has

operator () defined so that in the following exampleFunctionObjectType fo;

...

fo(...);

the expression fo() is a call of operator () for the

function object fo instead of a call of the function fo()

7/29/2019 10. Stl - Partea II



Obiecte de tip functie

Instead of writing all the function statements inside

the function body,void fo()

{

statements

}

you write them inside the body of operator () of the

function object class:

class FunctionObjectType {

public:

void operator()() { statements }

};

7/29/2019 10. Stl - Partea II



Obiecte de tip functie: avantaje

A function object might be smarter because it may

have a state. In fact, you can have two instances of the same function, represented by a function object,which may have different states at the same time.This is not possible for ordinary functions.

Each function object has its own type. Thus, you canpass the type of a function object to a template tospecify a certain behavior, and you have theadvantage that container types with different functionobjects differ.

A function object is usually faster than a functionpointer.

7/29/2019 10. Stl - Partea II



Obiecte de tip functie: sortare

class Person {

public:string firstname() const;string lastname() const;//...

};class PersonSortCriterion {

public: bool operator() (const Person& p1,

const Person& p2) const{return p1.lastname() < p2.1astname() ||

((p2.1astname() == p1.lastname()) && p1.firstname() < p2.firstname());

}};

7/29/2019 10. Stl - Partea II



Obiecte de tip functie: sortare

int main(){//declare set type with special sorting criteriontypedef set<Person,PersonSortCriterion>

PersonSet;//create such a collectionPersonSet coll;

...//do something with the elementsPersonSet::iterator pos;for (pos = coll.begin(); pos != coll.end();

++pos)

{ ...}...

}

7/29/2019 10. Stl - Partea II



Obiecte de tip functie cu stare interna

In this example, a function object is used that generates asequence of integral values. Each time operator () is called, it

returns its actual value and increments it. You can pass thestart value as a constructor argument.

class IntSequence{

private:

int value; public://constructorIntSequence (int initialValue)

: value(initialValue) { }//''function call''int operator() () {

return value++;}

};

7/29/2019 10. Stl - Partea II




utilizarea a unei functii cu generate_n()

list<int> coll;

//insert values from 1 to 9

generate_n (back_inserter(coll), //start

9, //number of elements

IntSequence (1)); //generates

//values

coll’s contents:

1; 2; 3; 4; 5; 6; 7; 8; 9;

7/29/2019 10. Stl - Partea II




utilizarea a unei functii cu generate_n()

generate (++coll.begin(), //start--coll.end(), //end

IntSequence (42)); //generates

// values

coll’s contents:

1; 42; 43; 44; 45; 46; 47; 48; 9;

demo

7/29/2019 10. Stl - Partea II




Function objects are passed by value rather than by

reference.

IntSequence seq(1); //integral sequence

//starting with value 1

//insert sequence beginning with 1

generate_n (back_inserter(coll), 9, seq);

//insert sequence beginning with 1 againgenerate_n (back_inserter(coll), 9, seq);

demo

7/29/2019 10. Stl - Partea II




However, access to the final state might be

necessary, so the question is how to get a "result"from an algorithm. There are two ways to get a

"result" or "feedback" from using function objects

with algorithms:

• You can pass the function objects by reference.• You can use the return value of the for_each()

algorithm.

create a function object:IntSequence seq(1);

7/29/2019 10. Stl - Partea II




to pass seq by reference in generate_n() , the template

arguments are qualified explicitly:

generate_n<back_insert_iterator<list<int> >,

int,

IntSequence&>

(back_inserter(coll), //start

4, //number of elements

seq); //generates values demo

7/29/2019 10. Stl - Partea II



Obiecte de tip functie predefinite

Expression Effect

negate<type>() - param

plus<type>() param1 + param2

minus<type>() param 1 - param2

multiplies<type>() param1 * param2

divides<type>() param1 / param2

modulus <type>() param1 % param2equal_to<type>() param1 == param2

not_equal_to<type>() param1 ! = param2

7/29/2019 10. Stl - Partea II


Obiecte de tip functie predefinite

Expression Effect

less<type>() param1 < param2

greater<type>() param1 > param2

less_equal<type>() param1 <= param2

greater_equal<type>() param1 >= param2

logical_not<type>() ! param

logical_and<type>() param1 && param2

logical_or<type> () param1 | | param2

10. Stl - Partea II

Documents

Transcript of 10. Stl - Partea II