1 STL Partea 2. D. Lucanu STL – Partea 2 2 Cuprins STL C++ containere standard algoritmi...

1

STL

Partea 2

D. Lucanu STL – Partea 2 2

Cuprins

STL C++

• containere standard

• algoritmi

• clasificare

• exemple:

• liste

• tablouri asociative

• agenda telefonica

• functori (obiecte functii)


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


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


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 are

equal(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


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


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


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


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 nonmatching elements


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


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


STL: algoritmi de sortare

stable_partition() Same as partition() but preserves the relative order of matching and nonmatching elements

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)


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 than

or equal to a given value upper _bound() Finds the first element greater than

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

to a given value merge() Merges the elements of two ranges set_union() Processes the sorted union of two

ranges


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 sorted range that contains all elements that are in exactly one of two ranges

inplace_merge() Merges two consecutive sorted ranges


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


STL :: algoritmi::liste header#include <algorithm> declarare listalist<string> amici; afisare componentelor listeivoid print_string(string s){cout << s << endl;

}//... p = amici.begin();q = amici.end();for_each(p, q, print_string);


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);


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?


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);


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 simplainsert_inserator<list<int>> ii(li, p);...*ii = 55; // este echivalent culi.insert(p, 55)


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));


STL :: algoritmi::map clasa Persoanaclass Persoana { //. . . friend bool operator<(const Persoana& lhs, \ const Persoana& rhs); //...}; clasa Info (despre persoana)class Info {// . . .private: string adr; string nr;};


STL :: algoritmi::map

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);


STL :: algoritmi::map

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);


STL::ex:: agenda telefonica cheia va fi un numetypedef 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);

//. . .};


STL::ex:: agenda telefonica

memorarea agendei in fisier

• fiecare intrare este memorata pe 3 linii:

<nume>

<adresa>

<numar tel>

• fisierul va avea 3*nr_intrari linii


STL::ex:: agenda telefonicavoid 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();

}



void AgTel::adIntrare()

{

//...

std::cout << "Nume: ";

std::cin >> s;

Nume nume(s);

//...

this->insert(end(), \

std::make_pair(nume, info));

}



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();

}


STL::ex:: agenda telefonica:: demo

int main(){int optiune;AgTel agTel;do {

std::cout << "1. Initializeaza ...”;//. . .std::cout << "0. Terminare.\n";std::cin >> optiune;


STL::ex:: agenda telefonica:: demo

switch (optiune){case 1:

agTel.clear();break;

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

//. . . }

} while (optiune != 0);return 0;

}


Obiecte de tip functie

A function object (or functor), is an object that has operator () defined so that in the following example

FunctionObjectType fo;

...

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

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


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 }

};


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 can pass the type of a function object to a template to specify a certain behavior, and you have the advantage that container types with different function objects differ.

A function object is usually faster than a function pointer.


Obiecte de tip functie: sortareclass 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()); }};


Obiecte de tip functie: sortare int main() { //declare set type with special sorting criterion typedef set<Person,PersonSortCriterion> PersonSet; //create such a collection PersonSet coll; ... //do something with the elements PersonSet::iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) { ... } ... }


Obiecte de tip functie cu stare interna In this example, a function object is used that generates a

sequence of integral values. Each time operator () is called, it returns its actual value and increments it. You can pass the start value as a constructor argument.

class IntSequence {private: int value;public: //constructor IntSequence (int initialValue) : value(initialValue) { } //''function call'' int operator() () { return value++; }};


Obiecte de tip functie cu stare interna

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;



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


Obiecte de tip functie cu stare interna Function objects are passed by value rather than by

reference.

IntSequence seq(1); //integral sequence //starting with value 1

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

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



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);



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


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 % param2

equal_to<type>() param1 == param2

not_equal_to<type>() param1 ! = param2


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

1 STL Partea 2. D. Lucanu STL – Partea 2 2 Cuprins STL C++ containere standard algoritmi...

Documents

Transcript of 1 STL Partea 2. D. Lucanu STL – Partea 2 2 Cuprins STL C++ containere standard algoritmi...