Standard Template Library
STL
Claudio Esperança
Paulo Roma Cavalcanti
 2008 LCG/UFRJ. All rights reserved.
1
O que é a STL?
• STL é uma biblioteca padrão com as
estruturas de dados mais usadas em
Computação.
▪ Foi criada para evitar a implementação e teste
das mesmas estruturas de dados eternamente.
▪ Por isso, economiza muito tempo e evita “dor
de cabeça” desnecessária.
• Por que templates?
▪ Elas lhe poupam da tarefa de reimplementar o
código para cada novo tipo de dado da sua
aplicação.
 2008 LCG/UFRJ. All rights reserved.
2
STL
• Quando usadas apropriadamente, as templates são
bastante eficazes.
▪ No entanto, as mensagens de erro costumam ser
pouco elucidativas.
• Uma boa fonte sobre a STL é o guia de programação
da SGI.
▪ Ou então a nossa implementação de um subconjunto
da STL.
• Na nossa implementação, cada classe tem o prefixo
“utl” (não havia namespace ainda).
▪ Se a variável de compilação USE_STL estiver definida,
o prefixo será suprimido, “cgcUtil::” será substituído
por “std::”, e o compilador usará a STL nativa então.
 2008 LCG/UFRJ. All rights reserved.
3
Estrutura da STL
• A STL oferece:
▪ Containers (recipientes).
▪ Iterators (iteradores).
▪ Algorithms (algoritmos).
• Recipientes servem para armazenar dados e
podem ser classificados como:
▪ Seqüências de dados
▪ Recipientes associativos para pares de objetos
(chave, dado).
▪ Adaptadores que provêem um subconjunto
da funcionalidade de um recipiente.
◦ Pilhas, filas, filas de prioridade.
 2008 LCG/UFRJ. All rights reserved.
4
Iteradores
• Iteradores foram criados para permitir uma
maneira unificada de percorrer ou recuperar
dados de recipientes.
▪ Escondem os detalhes de implementação,
principalmente ponteiros, das aplicações.
▪ Portanto, geralmente é possível trocar o tipo
de recipiente e ainda assim usar o mesmo
código.
• A STL adota a filosofia de manter os
algoritmos fora das classes dos recipientes.
▪ A razão é permitir que o mesmo algoritmo
possa agir sobre recipientes diferentes.
 2008 LCG/UFRJ. All rights reserved.
5
Exemplo
• Geralmente os algoritmos são
implementados usando iteradores apenas.
▪ Ordenação, busca, contagem, substituição,
etc...
▪ Iteradores tem operadores de incremento “++”
definidos.
▪ Ponteiros podem ser usados como iteradores.
 2008 LCG/UFRJ. All rights reserved.
6
#include <vector>
#include <iostream>
using namespace std;
/** função objeto.
*
Insere T em um stream de saída.
*
Substitui “passar ponteiro para função” de C.
*/
template <class T>
struct print : public unary_function <T, void>
{
print(ostream& out) : os(out), count(0) {}
void operator() (T x) { os << x << ' '; ++count; }
ostream& os;
int count;
};
Construtor
int
{
Redefine
operador ( )
7
Imprimindo
elementos de um
vetor
Calcula o
Chama print()
tamanho de
para cada
main()
A
Guarda
elemento de A Dois
int A[] = {1, 4, 2, 8, 5, 7};
número de
const int N = sizeof(A) / sizeof(int);iteradores
elementos
print<int> P = for_each(A, A + N, print<int>(cout));
impressos
cout << endl << P.count << " objects printed." << endl;
return 1;
}
1 4 2 8 5 7
6 objects printed.
 2008 LCG/UFRJ.
All rights reserved.
Vector
• vector é o recipiente mais simples da STL.
▪ É uma seqüência que suporta acesso aleatório
aos seus elementos.
▪ Inserção e remoção de elementos no final em
O(1).
▪ Inserção e remoção de elementos no meio em
O(n).
▪ Busca em O(n).
▪ Gerenciamento automático de memória.
▪ Iteradores estão invalidados após realocação
de memória, inserção e remoção no meio.
▪ Descrição e implementação.
 2008 LCG/UFRJ. All rights reserved.
8
#include <vector>
#include <iostream>
#include <iterator>
#include <ext/algorithm>
using namespace std;
using __gnu_cxx::is_sorted;
Insere no
final
de V.
int
main()
{
vector<int> V;
Insere V no
V.push_back(20);
Ordena V
V.push_back(30);
stream de
V.push_back(-1);
com merge
saída
V.push_back(-1);
sort.
V.push_back(-1);
Verifica se
cout << "V: \n";
copy(V.begin(), V.end(), ostream_iterator<int>(cout,
" "));
V está
stable_sort (V.begin(), V.end());
ordenado.
cout << "\nV: sorted\n";
copy(V.begin(), V.end(), ostream_iterator<int>(cout, " "));
cout << "\nV: is sorted? ";
cout << is_sorted ( V.begin(), V.end() ) << "\n";
}
V:
20
V:
-1
V:
30 -1 -1 -1
sorted
-1 -1 20 30
is sorted? 1
9
Uso da classe
vector.
 2008 LCG/UFRJ.
All rights reserved.
/**
copies elements from a container to another.
*
*
Copies elements from the range [first, last) to the
*
range [result, result + (last - first)).
*
That is, it performs the assignments
*
*result = *first, *(result + 1) = *(first + 1), and so on.
*
Generally, for every integer n from 0 to last - first,
*
copy() performs the assignment *(result + n) = *(first + n).
*
Assignments are performed in forward order, i.e. in order of
*
increasing n.
*
*
The return value is result + (last - first)
*
*
@param first where to start copying.
*
@param last where to end copying.
*
@param result where to copy.
*
@return result + (last-first).
*/
template<class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
OutputIterator result) {
for( InputIterator itr = first; itr != last; ++itr, ++result ) {
*result = *itr;
}
return result;
}
Apenas percorre o
recipiente de
entrada.
10
Função copy.
Derivados da
mesma classe
base.
E atribui ao
recipiente
da saída.
 2008 LCG/UFRJ.
All rights reserved.
Deque
• deque (Double Ended Queue) é como um vetor com
inserção eficiente na frente também.
▪ É uma seqüência que suporta acesso aleatório aos
seus elementos.
▪ Inserção e remoção de elementos no meio em O(n).
▪ Busca em O(n).
▪ Inserção e remoção de elementos na frente e no final
em O(1).
▪ Gerenciamento automático de memória.
▪ Iteradores estão invalidados após realocação de
memória, inserção e remoção no meio.
▪ Descrição e implementação.
 2008 LCG/UFRJ. All rights reserved.
11
#include <deque>
#include <iostream>
#include <iterator>
12
using namespace std;
int main() {
Uso da classe deque.
deque<int> Q;
Q.push_back(3);
Insere 5 três
Q.push_front(1);
Q.insert(Q.begin() + 1, 2);
vezes após a
Q[2] = 0;
primeira
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));
posição.
cout << "\n";
// The values that are printed are 1 2 0
Q.insert(Q.begin() + 1, (size_t)3, 5);
Q.push_front(7);
Q.push_front(8);
Q.push_front(9);
 2008 LCG/UFRJ.
All rights reserved.
Redimensiona
copy(Q.begin(),
Q.end(),
P completando
cout << "\n";
comP 88
no final.
deque<int>
= Q;
13
ostream_iterator<int>(cout, " "));
copy(Q.begin(), Q.end(), ostream_iterator<int>(cout,
" "));
Remove os dois
cout << "\n";
primeiros
P.resize ( 18, 88 );
elementos de P.
P.push_front ( 99 );
P.push_front ( 98 );
copy(P.begin(), P.end(), ostream_iterator<int>(cout, " "));
P.erase ( P.begin(), P.begin()+2
);
Último
cout << "\n";
elemento de P
cout << P.back();
cout << "\n";
Primeiro
cout << P.front();
elemento de P
cout << "\n";
cout << *P.begin();
cout << "\n";
}
1 2 0
9 8 7 1 5 5 5 2 0
9 8 7 1 5 5 5 2 0
98 99 9 8 7 1 5 5 5 2 0 88 88 88 88 88 88 88 88 88
88
9
9
Uso da classe deque.
 2008 LCG/UFRJ.
All rights reserved.
List
• list é de fato uma lista duplamente
encadeada.
▪ É uma seqüência que suporta percurso para
frente e para trás.
▪ Busca em O(n).
▪ Inserção e remoção de elementos na frente, no
meio e no final em O(1).
▪ Iteradores ainda estão válidos após inserção,
splicing ou remoção.
▪ Descrição, Implementação.
 2008 LCG/UFRJ. All rights reserved.
14
#include <list>
#include <iostream>
#include <iterator>
15
using namespace std;
Insere 0 no
final de L Insere 1 no
int main()
{
início de L.
Uso da classe list.
list<int> L;
L.push_back(0);
L.push_front(1);
L.insert(++L.begin(), 2);
copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));
cout << "\n";
list<int> M ( L );
Insere 2
L.splice ( ++++L.begin(), M );
após a
copy(L.begin(), L.end(), ostream_iterator<int>(cout,
" "));
cout << “\n”;
primeira
copy(M.begin(), M.end(), ostream_iterator<int>(cout, " "));
posição.
}
Move
elementos de
M para L.
1 2 0
1 2 1 2 0 0
M está
vazia.
 2008 LCG/UFRJ.
All rights reserved.
String
• string toma o lugar de um “array of char”.
▪ Não é mais necessário se preocupar com o
tamanho do arranjo.
▪ Oferece todas as funções de C pertinentes a
strings como membros da classe.
▪ Evita erros relacionados com ponteiros, na
chamada de funções que recebem ou
retornam strings.
▪ Descrição, Implementação.
 2008 LCG/UFRJ. All rights reserved.
16
#include <string>
#include <iostream>
using namespace std;
int main () {
//test constructors
string str0;
cout << "empty constructor: " << str0 << endl;
cout << "str0 size = " << str0.size() << endl;
mesmo que world!");
string O
str1("hellow
Comprimento
Capacidade
da
//
0123456789012
length.
Tamanho
cout << atual
"const
constructor:
string
da char
string
sem
termáximo" << str1 << endl;
cout << "data de
= "realocar.
<< str1.data()
que
uma string << endl;
cout << "size = " << pode
str1.size()
<< endl;
ter.
cout << "length = " << str1.length() << endl;
cout << "capacity = " << str1.capacity() << endl;
cout << "max_size = " << str1.max_size() << endl;
// empty
cout << "str0 empty = " << str0.empty() << endl;
cout << "str1 empty = " << str1.empty() << endl;
empty constructor:
str0 size = 0
const char constructor: hellow world!
data = hellow world!
size = 13
length = 13
capacity = 13
max_size = 13
str0 empty = 1
str1 empty = 0
17
Uso da classe string.
 2008 LCG/UFRJ.
All rights reserved.
string str2(str1);
cout << “copy constructor: " << str2 << endl;
string str3(str1, 4, 6);
cout << "string&, pos, npos, str3 constructor: "
<< str3 << endl;
string str4("hellow word!", 6);
Troca o npos, str4 constructor: " << str4 << endl;
cout << "char[],
string str5(12,
conteúdo 'h');
de
cout << “n, char str5 constructor: " << str5 << endl;
str5 por str1.
cout << "str5 size = " << str5.size() << endl;
// swap
str5.swap(str1);
cout << "swap str1 and str5" << endl;
cout << "str1 = " << str1 << endl;
cout << "str5 = " << str5 << endl;
}
copy constructor: hellow world!
string&, pos, npos, str3 constructor: ow wor
char[], npos, str4 constructor: hellow
n, char str5 constructor: hhhhhhhhhhhh
str5 size = 12
swap str1 and str5
str1 = hhhhhhhhhhhh
str5 = hellow world!
18
Uso da classe string.
 2008 LCG/UFRJ.
All rights reserved.
Set
• set é uma coleção ordenada de objetos do tipo
“key” sem duplicatas.
▪ Operações de conjunto como interseção, união
e diferença são eficientes.
▪ Implementado por uma árvore balanceada de
busca (Red Black, Splay).
▪ Busca em O(log n).
▪ Descrição, Implementação.
• multiset é a versão que permite duplicatas.
▪ Descrição, Implementação.
 2008 LCG/UFRJ. All rights reserved.
19
#include <set>
#include <iostream>
using namespace std;
20
Retorna se s1 é
lexicograficamente
/// função
objeto. Compara duas
struct ltstr
menor que s2
{
seqüências de caracteres.
bool operator()(const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
Uso da classe set.
int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
const char* b[N] = {"flat", "this", "artichoke",
"frigate", "prosaic", "isomer"};
Construtor a
partir de dois
iteradores
set<const char*,ltstr> A(a, a + N);
set<const char*,ltstr> B(b, b + N);
set<const char*,ltstr> C;
 2008 LCG/UFRJ.
All rights reserved.
cout << "Set A:
copy(A.begin(),
cout << endl;
cout << "Set B:
copy(B.begin(),
cout << endl;
A ∪ B.
";
A.end(), ostream_iterator <const char*>(cout, " "));
21
";
B.end(), ostream_iterator <const char*>(cout, " "));
cout << "Union: ";
set_union(A.begin(), A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, " "), ltstr());
cout << endl;
Uso da classe set.
A ∩ B.
cout << "Intersection: ";
set_intersection(A.begin(), A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, " "), ltstr());
cout << endl;
A – B.
set_difference(A.begin(), A.end(), B.begin(), B.end(),
inserter(C, C.begin()), ltstr());
cout << "Set C (difference of A and B): ";
copy(C.begin(), C.end(), ostream_iterator <const char*>(cout, " "));
cout << endl;
}
Insere o
resultado em
C.
Set A: artichoke ephemeral isomer nugatory prosaic serif
Set B: artichoke flat frigate isomer prosaic this
Union: artichoke ephemeral flat frigate isomer nugatory prosaic serif this
Intersection: artichoke isomer prosaic
Set C (difference of A and B): ephemeral nugatory serif
 2008 LCG/UFRJ.
All rights reserved.
Map
• map associa objetos do tipo “key” a objetos do
tipo “data”.
▪ Nenhum par de elementos possui a mesma
chave.
▪ Percurso é ordenado.
▪ Indicada para implementação de dicionários.
▪ Implementada por uma árvore balanceada de
busca (Red Black, Splay).
▪ Busca em O(log n).
▪ Descrição, Implementação.
• multimap é a versão que permite duplicatas.
▪ Descrição, Implementação.
 2008 LCG/UFRJ. All rights reserved.
22
#include <map>
#include <string>
#include <iostream>
23
using namespace std;
Chave e dado.
typedef map < long, string > mapType;
typedef mapType::value_type ValuePair;
int main()
Duas formas
de inserção
{
Uso da classe map.
mapType Map;
Map[836361136] = "Andrew";
Map[274635328] = "Berni";
Map[974635328] = "Ulisses";
Map[277735328] = "Paulo";
Map[277825328] = "Pedro";
Map[266735328] = "Peter";
Map[275734328] = "Paula";
Map[275839328] = "Paulos";
Map.insert(ValuePair(260736622, "John"));
Map.insert(ValuePair(720002287, "Karen"));
Map.insert(ValuePair(138373498, "Thomas"));
Map.insert(ValuePair(135353630, "William"));
// insertion of Xaviera is not executed, because
// the key already exists.
Map.insert(ValuePair(720002287, "Xaviera"));
Cria um par
(chave,dado).
mapType Map2 ( Map.begin(), Map.end() );
cout << "equality operator " << (Map2 == Map) << endl;
equality operator 1
Output:
974635328:Ulisses
836361136:Andrew
720002287:Karen
277825328:Pedro
277735328:Paulo
275839328:Paulos
275734328:Paula
Ordem
decrescente.
 2008 LCG/UFRJ.
All rights reserved.
cout << "Output:\n";
Iterador
720002287
reverso. );
Map.erase (
Map2.swap ( Map );
Cast para
iterador
constante.
mapType::const_reverse_iterator iter = Map.rbegin();
while( iter != (mapType::const_reverse_iterator)Map.rend() ) {
cout << (*iter).first << ':'
<< (*iter).second
<< endl;
++iter;
}
24
Uso da classe map.
cout << "Output of the name after entering the number\n"
<< "Number: ";
long Number;
Se
encontrado.
>>
Number;
Busca é
O(log n).
cin
mapType::const_iterator it = Map.find(Number);
if(it != Map.end()) {
cout << (*it).second << ' ' // O(1)
<< endl;
} else
cout << "Not found!" << endl;
}
274635328:Berni
266735328:Peter
260736622:John
138373498:Thomas
135353630:William
Output of the name after entering the number
Number: 275734328
Paula
 2008 LCG/UFRJ.
All rights reserved.
Hash Map
• hash_map associa objetos do tipo “key” a objetos do
tipo “data”.
▪ Nenhum par de elementos possui a mesma chave.
▪ Não há ordem de percurso.
▪ Implementada por uma hash table.
◦ Há uma função de hash que gera endereços a partir de
chaves.
▪ Busca em O(1).
▪ Descrição, Implementação.
• hash_multimap é a versão que permite duplicatas.
▪ Descrição, Implementação.
 2008 LCG/UFRJ. All rights reserved.
25
#include <ext/hash_map>
#include <string>
#include <iostream>
26
using namespace std;
using __gnu_cxx::hash_map;
using __gun_cxx::hash;
Recebe
string e
// define your own hash function
template <class T> class my_hash: public hash<T> {
passa char*.
public:
// initial hash table size
#define table_size 11
Uso da classe
hash_map.
my_hash() {}
size_t operator()(const string& p) const {
hash<const char*> h;
return h(p.c_str());
}
};
typedef hash_map<string, string, my_hash<string> > mapType;
typedef mapType::value_type ValuePair;
int main() {
mapType Map ( table_size, my_hash <string>() );
Map["ANDREW"]="Andrew";
Map["BERNI"]="Berni";
Map["JOHN"]="John";
Map.insert(ValuePair("KAREN", "Karen"));
Map.insert(ValuePair("THOMAS", "Thomas"));
Map["WILLIAM"]="William";
// insertion of Xaviera is not executed, because
// the key already exists.
Map.insert(ValuePair("BERNI", "Xaviera"));
 2008 LCG/UFRJ.
All rights reserved.
cout << "Output:\n";
27
mapType::iterator iter = Map.begin();
while(iter != Map.end()) {
cout << (*iter).first << ':'
<< (*iter).second
<< endl;
++iter;
}
Elimina \n
do final de
name after entering
buf.
cout << "Output of the
the key\n"
<< "Key: ";
char buf[256]; buf[0] = '\0';
fgets ( buf, 256, stdin );
if ( buf[strlen(buf)-1]=='\n' ) buf[strlen(buf)-1] = '\0';
string key ( buf );
iter = Map.find(key);
if(iter != Map.end()) {
cout << (*iter).second << ' '
<< Map[key]
<< endl;
} else
cout << "Not found!" << endl;
Uso da classe
hash_map.
Busca é
O(1)
}
Output:
JOHN:John
BERNI:Berni
KAREN:Karen
ANDREW:Andrew
THOMAS:Thomas
WILLIAN:Willian
Output of the name after entering the key
Key: KAREN
Karen Karen
Não há
ordem.
 2008 LCG/UFRJ.
All rights reserved.