Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

C++ Standard Template Library

No description
by

Zalán Szűgyi

on 28 April 2016

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of C++ Standard Template Library

C++ Standard Template Library
Szűgyi Zalán
Tárolók
Algoritmusok
Iterátorok
Szekvenciális
Asszociatív
vector

list

deque

array

forward_list
std::vector<int> v1;
std::vector<int> v2(10);
std::vector<int> v3(10, 42);
std::vector<int> v4(v3);
std::vector<int> v5(it1, it2);


std::vector<int> v6 = {1,2,3,4,5}

// üres vector
// 10 elemű vector, 0-val inicializálva
// 10 elemű vector, 42-vel inicializálva
// copy constructor
// iterátorok által meghatározott intervallum
// értékét veszi fel

// csak C++11, közvetlenül adjuk meg az
// elemeket
std::vector<int> v;

v.push_back(5);
v.pop_back();
v.insert(pos, 5);
v.erase(pos);
v.insert(pos, it1, it2);
v.erase(it1, it2);


// beszúr a végére
// töröl a végéről
// a pos iterátor által hivatkozott elem elé szúr be
// törli a pos iterátor által hivatkozott elemet
// intervallum elemeit szúrja be a pos elé
// intervallumot töröl
std::vector<int> v(5);
v[0], ..., v[4]
v.push_back(7);
v[5]
v.back();
v.front();




// 0-tól méret-1 -ig indexelhetjük
// mindig a végére szúr be új elemet

// utolsó eleme
// első eleme
std::vector<int> v;

v.size();
v.empty();
v.begin();
v.end();
v.clear();



// méret lekérdezése
// igaz, ha üres a vector
// iterátor az első elemre
// iterátor az utolsó utáni elemre
// minden elem törlése

Konstruktorok
Beszúrás / Törlés
Elemek elérése
for(std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
std::cout << *it;

Egyéb műveletek
std::list<int> l1;
std::list<int> l2(10);
std::list<int> l3(10, 42);
std::list<int> l4(v3);
std::list<int> l5(it1, it2);


std::list<int> l6 = {1,2,3,4,5}

// üres lista
// 10 elemű lista, 0-val inicializálva
// 10 elemű lista, 42-vel inicializálva
// copy constructor
// iterátorok által meghatározott intervallum
// értékét veszi fel

// csak C++11, közvetlenül adjuk meg az
// elemeket
std::list<int> l;

l.push_back(5);
l.pop_back();
l.push_front(3);
l.pop_front();
l.insert(pos, 5);
l.erase(pos);
l.insert(pos, it1, it2);
l.erase(it1, it2);


// beszúr a végére
// töröl a végéről
// beszúr az elejére
// töröl az elejéről
// a pos iterátor által hivatkozott elem elé szúr be
// törli a pos iterátor által hivatkozott elemet
// intervallum elemeit szúrja be a pos elé
// intervallumot töröl
std::list<int> l(5);

l.back();
l.front();




// nincs indexelés, tagfüggvények segítségével
// csak az első és az utolsó elem érhető el
// minden máshoz iterátorok kellenek


std::list<int> l;

l.size();
l.empty();
l.begin();
l.end();
l.clear();


// méret lekérdezése
// igaz, ha üres a vector
// iterátor az első elemre
// iterátor az utolsó utáni elemre
// minden elem törlése


Konstruktorok
Beszúrás / Törlés
Elemek elérése
for(std::list<int>::iterator it = l.begin(); it != l.end(); ++it)
std::cout << *it;

Egyéb műveletek
std::deque<int> d1;
std::deque<int> d2(10);
std::deque<int> d3(10, 42);
std::deque<int> d4(v3);
std::deque<int> d5(it1, it2);


std::deque<int> d6 = {1,2,3,4,5}

// üres deque
// 10 elemű deque, 0-val inicializálva
// 10 elemű deque, 42-vel inicializálva
// copy constructor
// iterátorok által meghatározott intervallum
// értékét veszi fel

// csak C++11, közvetlenül adjuk meg az
// elemeket
std::deque<int> d;

d.push_back(5);
d.pop_back();
d.push_front(3);
d.pop_front();
d.insert(pos, 5);
d.erase(pos);
d.insert(pos, it1, it2);
d.erase(it1, it2);


// beszúr a végére
// töröl a végéről
// beszúr az elejére
// töröl az elejéről
// a pos iterátor által hivatkozott elem elé szúr be
// törli a pos iterátor által hivatkozott elemet
// intervallum elemeit szúrja be a pos elé
// intervallumot töröl
std::deque<int> d(5);
d[0], ..., d[4]
d.push_front(7);
d[5]
d.back();
d.front();




// 0-tól méret-1 -ig indexelhetjük
// ekkor ő lesz a 0-ás indexű elem

// utolsó eleme
// első eleme
std::deque<int> d;

d.size();
d.empty();
d.begin();
d.end();
d.clear();



// méret lekérdezése
// igaz, ha üres a vector
// iterátor az első elemre
// iterátor az utolsó utáni elemre
// minden elem törlése
Konstruktorok
Beszúrás / Törlés
Elemek elérése
for(std::deque<int>::iterator it = d.begin(); it != d.end(); ++it)
std::cout << *it;

Egyéb műveletek
Egybefüggő memóriaterületen van
Elemeit konstans időben közvetlenül elérhetjük
Elem beszúrása:
végére: amortizált konstans
máshova: lineáris
Elem törlése:
végéről: konstans
máshonnan: lineáris
Elemeit lineáris időben elérhetjük el
Elem beszúrása:
elejére végére: konstans
máshova: konstans (ha van iterátor)
Elem törlése:
elejéről, végéről: konstans
máshonnan: konstans (ha van iterátor)
Elemeit konstans időben közvetlenül elérhetjük
Elem beszúrása:
elejére, végére: amortizált konstans
máshova: lineáris
Elem törlése:
elejéről, végéről: amortizált konstans
máshonnan: lineáris
Fix méretű tömb típus
Hagyományos tömböt burkol be és egészít ki tagfüggvényekkel


array<int, 3> a1;
array<int, 5> a2 = {1,2,3,4,5}
egyirányú láncolt lista
a vissza irányú pointerek hiánya miatt memóriatakarékosabb implementáció
értelemszerűen visszafele nem lehet bejárni
set /
multiset

map /
multimap

unordered_set
unordered_multiset
unordered_map
unordered_multimap
}
halmaz / zsák adatszerkezet
mögöttes implementáció: keresőfa
hatékony műveletek:
beszúrás
törlés
keresés
elemei közvetlen módon nem érhetők el
csak olyan típusú elemei lehetnek, amelyekre értelmezve van az
operator<
std::set<int> s;
std::set<int> s = {1,2,3,4,5};

s.insert(42);
s.erase(42);
s.find(42); --> iterátort ad vissza
s.count(42);


for( std::set<int>::const_iterator it = s.begin();
it != s.end(); ++it)
{
std::cout << *it;
}
kulcs, érték párok tárolására szolgál
mögöttes implementáció: keresőfa
kulcs alapján hatékony műveletek:
beszúrás
törlés
keresés
az értékek a kulcs alapján közvetlen módon elérhetőek (log n időben)
kulcs csak olyan típusú elem lehet, amelyre értelmezve van az
operator<
std::map<std::string, int> m;

m.insert( std::pair<std::string, int>("jan", 31);
m.insert( std::make_pair("jan", 31)); //

m.find("jan");

m["feb"] = 28;
std::cout << m["mar"]; //beteszi az értéktípus
default elemével
m.erase("feb");
template<typename Key, typename Value>
std::pair<Key, Value>
make_pair(const Key& k, const Value& v)
{
return std::pair<Key, Value>(k, v);
}
std::map<std::string, int> m;
std::string s;
std::ifstream ifs("input.txt");

while(ifs >> s)
{
++m[s];
}

for(std::map<std::string, int>::iterator it = m.begin();
it != m.end(); ++it)
{
std::cout << (*it).first << " " << (*it).second;
// std::cout << it->first << " " << it->second;
}
Ugyanaz az interfészük mint a korábbiaknak.

A különbség csak az, hogy hasító adatszerkezet van a háttérben.
input iterator
output iterator
forward iterator
bidirectional iterator
random access iterator
* (r), ++, ==, !=
* (w), ++, ==, !=
* (r/w), ++, ==, !=
* (r/w), ++, ==, !=,
--
* (r/w), ++,

==, !=, --,
+= n, -= n, <, <=, >, >=, -
find
find_if
copy
for_each
accumulate
...

Adapterek
stack
queue
priority_queue
Nem tárolók, mert nincs saját implementációjuk.
Meglevő tárolót használnak, csak lecserélik az interfészét.
template<typename T, typename C = std::deque<T> >
class stack
{
public:
void push(const T& t) { cont.push_back(t); }
void pop() { cont.pop_back(); }
T& top() { return cont.back(); }
bool empty() const { return cont.size(); }
int size const { return c.size(); }
private:
C cont;
};
Iterátorokon keresztül érik el a tárolók adatait
Bemenetük egy intervallum, amit egy iterátorpár definiál
Ez az intervallum balról zárt és jobbról nyílt
==> [it, it) üres intervallumot jelent
==> A jobb oldali iterátor nem része az intervallumnak (használhatjuk extremális elemnek)
template<typename InputIterator, typename T>
InputIterator find( InputIterator first, InputIterator last, const T& t )
{
while ( first != last )
{
if ( *first == t )
{
return first;
}
++first;
}
return last;
}
std::vector<int> v = {1,2,3,4,5,6,7,8};
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 5);

if ( it != v.end() )
std::cout << "talált";
else
std::cout << "nem talált";

template<typename InputIterator, typename Pred>
InputIterator find_if( InputIterator first, Input Iterator last, Pred p )
{
while ( first != last )
{
if ( p(*first) )
{
return first;
}
++first;
}
return last;
}
std::vector<int> v = {1,2,3,4,5,6,7,8};
LessThan5 lt5;
std::vector<int>::iterator it = std::find(v.begin(), v.end(), lt5);
//std::vector<int>::iterator it = std::find(v.begin(), v.end(), LessThan5());

if ( it != v.end() )
std::cout << "talált";
else
std::cout << "nem talált";

struct LessThan5
{
bool operator()(int x) const
{
return x < 5;
}
}
template<typename InputIterator, typename OutputIterator>
OutputIterator copy( InputIterator first, InputIterator last, OutputIterator target )
{
while ( first != last )
{
*target++ = *first++
}
return target;
}
std::vector<int> v = {1,2,3,4,5,6,7,8};
std::list<int> lst(15);

std::copy(v.begin()+2, v.end()-1, ++lst.begin());
// A vektor harmadiktól az utolsó előttiig tartó elemeinek átmásolása a
// listába. (A lista első eleme változatlan marad, majd a második
// elemtől felülíródik a vektor megfelelő elemeivel.)

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{
for (; first != last; ++first)
{
f(*first);
}
return f;
}
template<class InputIt, class T>
T accumulate(InputIt first, InputIt last, T init)
{
for (; first != last; ++first) {
init = init + *first;
}
return init;
}
template<class InputIt, class T, class BinaryOperation>
T accumulate(InputIt first, InputIt last, T init,
BinaryOperation op)
{
for (; first != last; ++first) {
init = op(init, *first);
}
return init;
}
std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = std::accumulate(v.begin(), v.end(), 0);

int multiply(int x, int y) {
return x*y;
}

std::string magic_function(std::string res, int x) {
return res += (x > 5) ? "b" : "s";
}


std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int productt = std::accumulate(v.begin(), v.end(), 1, multiply);
std::string magic = std::accumulate(v.begin(), v.end(), std::string(), magic_function);

Linkek:
http://en.cppreference.com/w/
http://www.cplusplus.com/
http://www.sgi.com/stl
int t[] = { 1,2,3,4,5,6,7,8 };

int* find( int* t, int size, int x)
{
for (int i=0; i<size; ++i)
{
if (t[i] == x)
{
return t+i;
}
}

return 0;
}
int t[] = { 1,2,3,4,5,6,7,8 };

int* find( int* first, int* last, int x)
{
for (; first != last; ++first)
{
if (*first == x)
{
return first;
}
}

return last;
}
find(t, sizeof(t) / sizeof(t[0]), 5);
find(t, t + sizeof(t) / sizeof(t[0]), 5);
int t[] = { 1,2,3,4,5,6,7,8 };

template<typename T>
T* find( T* first, T* last, const T& x)
{
for (; first != last; ++first)
{
if (*first == x)
{
return first;
}
}

return last;
}
find(t, t + sizeof(t) / sizeof(t[0]), 5);
int t[] = { 1,2,3,4,5,6,7,8 };

template<typename Iterator typename T>
Iterator find( Iterator first, Iterator last, const T& x)
{
for (; first != last; ++first)
{
if (*first == x)
{
return first;
}
}

return last;
}
find(t, t + sizeof(t) / sizeof(t[0]), 5);
Full transcript