10. stl - partea ii
Post on 03-Apr-2018
219 Views
Preview:
TRANSCRIPT
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
http://slidepdf.com/reader/full/10-stl-partea-ii 2/44
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
http://slidepdf.com/reader/full/10-stl-partea-ii 3/44
D. Lucanu STL – Partea 2 3
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
http://slidepdf.com/reader/full/10-stl-partea-ii 4/44
D. Lucanu STL – Partea 2 4
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
http://slidepdf.com/reader/full/10-stl-partea-ii 5/44
D. Lucanu STL – Partea 2 5
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
http://slidepdf.com/reader/full/10-stl-partea-ii 6/44
D. Lucanu STL – Partea 2 6
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
http://slidepdf.com/reader/full/10-stl-partea-ii 7/44
D. Lucanu STL – Partea 2 7
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
http://slidepdf.com/reader/full/10-stl-partea-ii 8/44
D. Lucanu STL – Partea 2 8
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
http://slidepdf.com/reader/full/10-stl-partea-ii 9/44
D. Lucanu STL – Partea 2 9
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
http://slidepdf.com/reader/full/10-stl-partea-ii 10/44
D. Lucanu STL – Partea 2 10
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
http://slidepdf.com/reader/full/10-stl-partea-ii 11/44
D. Lucanu STL – Partea 2 11
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
http://slidepdf.com/reader/full/10-stl-partea-ii 12/44
D. Lucanu STL – Partea 2 12
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
http://slidepdf.com/reader/full/10-stl-partea-ii 13/44
D. Lucanu STL – Partea 2 13
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
http://slidepdf.com/reader/full/10-stl-partea-ii 14/44
D. Lucanu STL – Partea 2 14
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
http://slidepdf.com/reader/full/10-stl-partea-ii 15/44
D. Lucanu STL – Partea 2 15
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
http://slidepdf.com/reader/full/10-stl-partea-ii 16/44
D. Lucanu STL – Partea 2 16
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
http://slidepdf.com/reader/full/10-stl-partea-ii 17/44
D. Lucanu STL – Partea 2 17
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
http://slidepdf.com/reader/full/10-stl-partea-ii 18/44
D. Lucanu STL – Partea 2 18
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
http://slidepdf.com/reader/full/10-stl-partea-ii 19/44
D. Lucanu STL – Partea 2 19
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
http://slidepdf.com/reader/full/10-stl-partea-ii 20/44
D. Lucanu STL – Partea 2 20
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
http://slidepdf.com/reader/full/10-stl-partea-ii 21/44
D. Lucanu STL – Partea 2 21
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
http://slidepdf.com/reader/full/10-stl-partea-ii 22/44
D. Lucanu STL – Partea 2 22
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
http://slidepdf.com/reader/full/10-stl-partea-ii 23/44
D. Lucanu STL – Partea 2 23
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);
7/29/2019 10. Stl - Partea II
http://slidepdf.com/reader/full/10-stl-partea-ii 24/44
D. Lucanu STL – Partea 2 24
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);
7/29/2019 10. Stl - Partea II
http://slidepdf.com/reader/full/10-stl-partea-ii 25/44
D. Lucanu STL – Partea 2 25
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
http://slidepdf.com/reader/full/10-stl-partea-ii 26/44
D. Lucanu STL – Partea 2 26
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
7/29/2019 10. Stl - Partea II
http://slidepdf.com/reader/full/10-stl-partea-ii 27/44
D. Lucanu STL – Partea 2 27
STL::ex:: agenda telefonica
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
http://slidepdf.com/reader/full/10-stl-partea-ii 28/44
D. Lucanu STL – Partea 2 28
STL::ex:: agenda telefonica
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
http://slidepdf.com/reader/full/10-stl-partea-ii 29/44
D. Lucanu STL – Partea 2 29
STL::ex:: agenda telefonica
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
http://slidepdf.com/reader/full/10-stl-partea-ii 30/44
D. Lucanu STL – Partea 2 30
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
http://slidepdf.com/reader/full/10-stl-partea-ii 31/44
D. Lucanu STL – Partea 2 31
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
http://slidepdf.com/reader/full/10-stl-partea-ii 32/44
D. Lucanu STL – Partea 2 32
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
http://slidepdf.com/reader/full/10-stl-partea-ii 33/44
D. Lucanu STL – Partea 2 33
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
http://slidepdf.com/reader/full/10-stl-partea-ii 34/44
D. Lucanu STL – Partea 2 34
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
http://slidepdf.com/reader/full/10-stl-partea-ii 35/44
D. Lucanu STL – Partea 2 35
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
http://slidepdf.com/reader/full/10-stl-partea-ii 36/44
D. Lucanu STL – Partea 2 36
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
http://slidepdf.com/reader/full/10-stl-partea-ii 37/44
D. Lucanu STL – Partea 2 37
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
http://slidepdf.com/reader/full/10-stl-partea-ii 38/44
D. Lucanu STL – Partea 2 38
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;
7/29/2019 10. Stl - Partea II
http://slidepdf.com/reader/full/10-stl-partea-ii 39/44
D. Lucanu STL – Partea 2 39
Obiecte de tip functie cu stare interna
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
http://slidepdf.com/reader/full/10-stl-partea-ii 40/44
D. Lucanu STL – Partea 2 40
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 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
http://slidepdf.com/reader/full/10-stl-partea-ii 41/44
D. Lucanu STL – Partea 2 41
Obiecte de tip functie cu stare interna
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
http://slidepdf.com/reader/full/10-stl-partea-ii 42/44
D. Lucanu STL – Partea 2 42
Obiecte de tip functie cu stare interna
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
http://slidepdf.com/reader/full/10-stl-partea-ii 43/44
D. Lucanu STL – Partea 2 43
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
http://slidepdf.com/reader/full/10-stl-partea-ii 44/44
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
top related