Szablon definiuje klasę std::string reprezentującą tablicę znakową, która może dynamicznie zmieniać swoje rozmiary.
Poza funkcjami do
zarządzania pamięcią, klasa zawiera szereg metod umożliwiających dostęp do
znaków lub działania na całych tekstach (konkatenacja, usuwanie, wstawianie,
zastępowanie, itd.)
|
capacity() Zwraca rozmiar bufora. |
|
reserve (size_type n =0) Zmienia rozmiary bufora.
Gwarantuje, że po jej wykonaniu funkcja capacity() będzie zwracała co najmniej n. |
|
size()
lub length() Zwraca długość tekstu
(liczbę znaków umieszczonych w buforze). |
|
resize(size_type
n, E c = E()) Gwarantuje, że funkcja size()będzie zwracała co najmniej n. W razie potrzeby powiększa tablicę i
wypełnia znakiem c. |
Przykład
#include <string>
#include <iostream>
#include <fstream>
using namespace std;
Przykład
–cd
int main(int argc, char*
argv[])
{
string s;
ifstream is("readme.txt");
s.reserve(40);
for(int i=0;;i++){
int c=is.get();
if(c<0)break;
s+=(char)c;
// lub: s.append(1,c);
if(i%100==0){
cout<<s.capacity()<<"
";
cout<<"("<<s.size()<<")
";
}
}
cout<<endl<<s;
return 0;
}
Rezultat:
63
(1) 127 (101) 223 (201) 319 (301) 415 (401) 511 (501) 607 (601) 703 (701) 831
(801) 927 (901) 1023 (1001) 1119 (1101) 1215 (1201)
tekst
pliku…
Metoda zwraca stały wskaźnik do tekstu. Może być uzyta tam, gdzie wymagane jest użycie danych typu const char*.
void main(){
s="Tekst";
cout<<strcmp(s.c_str(),"Tekst")<<endl;
}
Użytkownik klasy string
może zrealizować dostęp do znaków z wykorzystaniem operatora [], funkcji at() lub
iteratorów.
Przykład
int main(int
argc, char* argv[])
{
string s="abcdefghij";
s[5]='F';
string::iterator it=s.begin();
*it='A';
s.at(1)='B';
for(string::const_iterator
ci=s.begin();
ci!=s.end();ci++)cout<<*ci;
cout<<endl;
for(string::reverse_iterator ri=s.rbegin();
ri!=s.rend();ri++)cout<<*ri;
cout<<endl;
string s2;
s2.resize(10);
for(ri=s.rbegin(),it=s2.begin();ri!=s.rend();
ri++,it++)*it=*ri;
cout<<s2<<endl;
return 0;
}
Rezultat:
ABcdeFghij
jihgFedcBA
jihgFedcBA
Uwaga: iterator begin() i funkcja c_str() zazwyczaj zwracają wskaźnik do tego samego obszaru pamięci. Jednakże nie należy używać ich zamiennie. Wywołanie iteratora nie gwarantuje obecności znaku 0 na końcu.
Do konkatenacji (łączenia) tekstów służy metoda append()
występująca w kilku przeciążonych wersjach lub operator + i +=.
Przykład
int main(int argc, char* argv[])
{
string s("Ala
ma");
s.append("
kota");
s+=" i
psa";
cout<<endl<<s;
return 0;
}
Rezultat: Ala ma kota i psa
Do wyodrębniania fragmentów tekstu służy metoda substr(). Jej parametrami są indeks początkowy i długość tekstu.
Przykład
int main(int argc, char* argv[])
{
string
s="abcdefgijklmn";
cout<<s.substr(3,3)<<endl;
return 0;
}
Rezultat: def
W klasie string
zdefiniowano kilka przeciążonych wersji metody erase()
pozwalającej na usuwanie fragmentów tekstu (lub całego tekstu).
Przykład
int main(int argc, char* argv[])
{
string
s="abcdefgijklmn";
int n1= s.find('d');
int n2 = 3; //
ile znakow
s.erase(n1,n2);
cout<<s<<endl;
s="abcdefgijklmn";
s.erase(s.begin()+2,s.begin()+4);
cout<<s<<endl;
return 0;
}
Rezultat:
abcgijklmn
abefgijklmn
Do wstawiania fragmentów tekstu służy
(przeciążona na kilka sposobów) funkcja
insert(). Funkcja
wstawia w miejsce określone przez indeks lub iterator teskt, który może być
tablicą znaków, fragmentem innego obiektu klasy string
lub sekwencją identycznych znaków.
Przykład
int main(int argc, char*
argv[])
{
string s("Ala ma kota");
s.insert(strlen("Ala
ma "), "psa i ");
cout<<s<<endl;
s="abcdefgijklmn";
s.insert(1,2,'x');
cout<<s<<endl;
return 0;
}
Rezultat:
Ala ma psa i kota
axxbcdefgijklmn
Funkcja find() pozwala na wyszukanie w tekście łańcucha znaków lub wystąpienia znaku. Funkcja replace() pozwala na zastąpienie wskazanego fragmentu tekstu innym.
Przykład
int main(int
argc, char* argv[])
{
string s("Witaj $user, jestes
zalogowany");
string userTag="$user";
int start=s.find(userTag);
s.replace(start,userTag.size(),"Piotr
Szwed");
cout<<s<<endl;
return 0;
}
Rezultat:
Witaj Piotr Szwed, jestes zalogowany
Klasa string nie jest szablonem, ale klasą powstałą w wyniku instancjacji szablonu basic_string typem char. Jest ona zdefiniowana w postaci deklaracji typedef:
typedef basic_string<char> string;
Intencją autorów biblioteki było stworzenie
ogólnego szablonu, który pozwalałby na obsługę łańcuchów znakowych także dla
innych platform i języków (Unicode, jezyków azjatyckich).
Szablon basic_string zdefiniowany jest jako:
template<class charT, class traits = char_traits<charT>, class allocator = allocator<charT> > class basic_string;
Klasa traits
„własności” definiuje kilkanaście funkcji statycznych określających podstawowe
cechy znaków:
static
void assign(E&
x, const E& y);
static
E *assign(E
*x, size_t n, const E& y);
static
bool eq(const
E& x, const E& y);
static
bool lt(const
E& x, const E& y);
static
int compare(const
E *x, const E *y, size_t n);
static
size_t length(const
E *x);
static
E *copy(E
*x, const E *y, size_t n);
static
E *move(E
*x, const E *y, size_t n);
static
const E *find(const
E *x, size_t n, const E& y);
static
E to_char_type(const
int_type& ch);
static
int_type to_int_type(const
E& c);
static
bool eq_int_type(const
int_type& ch1, const int_type& ch2);
static
int_type eof();
static
int_type not_eof(const
int_type& ch);
Przykład
Klasa typu string, której operator == ignoruje wielkość liter (na podst. Thinking In C++)
class ichar_traits
:
public std::char_traits<char>
{
public:
static int compare(const char* str1,
const char* str2, size_t n) {
return
strnicmp(str1,str2,n);
}
};
typedef
basic_string<char, ichar_traits,
allocator<char> > istring;
int main() {
istring first = "tHis";
istring second = "ThIS";
cout << (first==second) << endl;
}
Drugim parametrem szablonu jest klasa allocator,
czyli klasa odpowiedzialna za zarządzanie pamięcią. Metody:
· allocate() i deallocate() przydzielają i zwalniają pamięć dla tablicy obiektów
· construct() i destroy() tworzą (klonują) obiekt i zwalniają pamięć obiektu
Każdy obiekt klasy powstałej w wyniku instancjacji szablonu basic_string ma pole typu allocator. Rozmiar sizeof (allocator<char>) wynosi 1b.
Klasa SparseMatrix jest rodzajem słownika (funkcji) odwzorowuje int ´ int ® double. Do przechowywania elementów odwzorownia wykorzystywany jest szablon vector.
class SparseMatrix
{
struct
element{
int row,col;
double value;
};
vector<struct
element> elements;
public:
double get(int
r, int c)const{
for(int i=0;i<elements.size();i++){
if(elements[i].row==r &&
elements[i].col==c)
return elements[i].value;
}
return 0;
}
void
set(int r, int c, double v){
for(int i=0;i<elements.size();i++){
if(elements[i].row==r &&
elements[i].col==c){
elements[i].value=v;
return;
}
}
struct element e;
e.row=r;e.col=c; e.value=v;
elements.push_back(e);
}
int getRowsCount()const{
int rc=0;
for(int
i=0;i<elements.size();i++)
if(elements[i].row>rc)
rc=elements[i].row;
return
rc;
}
int
getColsCount()const{
int cc=0;
vector<struct element>::
const_iterator
it;
for(it=elements.begin();
it!=elements.end();it++)
if(it->col>cc)cc=it->col;
return cc;
}
};
void main() {
SparseMatrix m;
for(int k=0;k<10;k++)m.set(k,k,1);
for(int i=0;i<m.getRowsCount();i++){
for(int
j=0;j<m.getColsCount();j++)
cout<<m.get(i,j)<<" ";
cout<<endl;
}
}
Rezultat:
1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1
Szablon definiuje listę
dwukierunkową. Możliwe jest dodawanie elementów na początku i końcu listy,
wstawianie, usuwanie, łączenie ze sobą list. Nie jest możliwy swobodny dostęp
do elementów za pośrednictwem operatora [].
Lista jest efektywna, jeżeli liczba elementów i ich miejsce wstawienia nie są z
góry określone. Możliwe jest automatyczne sortowanie listy.
#include <list>
void main()
{
list<int> li;
for(int i=0;i<10;i++)
li.push_back(-rand()%100);
for(i=0;i<10;i++)
li.push_front(rand()%100);
for(list<int>::const_iterator
it=li.begin();
it!=li.end();it++) cout<<*it<<" ";
cout<<endl;
li.sort();
for(it=li.begin();it!=li.end();it++)
cout<<*it<<"
";
cout<<endl;
}
Rezultat:
36 27 42 95 91 61 27 81 45 5 -41 -67 -34 0 -69 -24 -78
-58 -62 -64
-78 -69 -67 -64 -62 -58 -41 -34 -24 0 5 27 27 36 42 45 61
81 91 95
Aby możliwe było
automatyczne sortowanie elementów listy za pomocą metody sort(),
klasa, której obiekty są umieszczone na liście musi zapewniać operatory do
porównywania elementów.
class A
{
public:
bool operator==(const A&)const{return
false;}
bool operator<(const A&)const{return
false;}
};
void main()
{
list<A> ali;
for(int i=0;i<10;i++)ali.push_back(A());
ali.sort();
}
Stos jest kontenerem implementowanym wewnętrznie za pomocą bardziej ogólnego szablonu deque (dwukierunkowa lista wektorów).
Stos zapewnia interfejs pozwalający na dodawanie i usuwanie elementów na końcu oraz odczyt ostatniej wartości.
Przykład – kalkulator
odwrotnej notacji polskiej
Odwrotna notacja polska (Reverse Polish Notation) jest pozbawioną nawiasów formą zapisu ułatwiającą maszynową interpretację wyrażeń. Zasadą jej interpretacji jest umieszczenie na stosie argumentów, a następnie operatora. Podczas ewaluacji operator pobiera ze stosu wymaganą liczbę argumentów, oblicza wartość i umieszcza rezultat na stosie.
Na przykład: wyrażenie (12.5 + (-5)) *2 /3 zapisywane jest w ONP jako „12.5 -5 + 2 * 3 /”
#include <stack>
#include <strstream>
#include <stdlib.h>
using namespace std;
class RPNCalc
{
stack<double>
dstack;
void
evaluate(char op)
{
if(dstack.size()<2){
cout<<"Too little
args"<<endl;
return;
}
double arg2=dstack.top();dstack.pop();
double arg1=dstack.top();dstack.pop();
double result;
switch(op){
case '+':result=arg1+arg2;break;
case '-':result=arg1-arg2;break;
case '*':result=arg1*arg2;break;
case '/':result=arg1/arg2;break;
}
dstack.push(result);
}
public:
void
push(const string&s){
if(s=="+" ||s=="-" ||
s=="*"||s=="/"){
evaluate(s.c_str()[0]);
return;
}
double arg=atof(s.c_str());
dstack.push(arg);
}
void
getResult(){
if(dstack.size()<1)return;
double result=dstack.top();dstack.pop();
cout<<result<<endl;
}
void
evaluate(const char*s){
istrstream is(s);
while(is){
string a;
is>>a;
if(a.empty())break;
push(a);
}
getResult();
}
};
void main() {
RPNCalc
calc;
calc.evaluate("12.5
-5 + 2 * 3 /"); //5
for(;;){
char command[256];;
cin.getline(command,256);
if(!strcmp(command,"exit"))return;
calc.evaluate(command);
}
}
Słownik jest zapisem
funkcji odwzorowującej klucze w wartości. Jest więc zbiorem par (klucz, wartość). W słowniku
może wystąpić tylko pojedyncza instancja klucza. Dana wartość może być
przypisana wielu kluczom. Szablon map jest
optymalizowany, aby zapewnić dużą prędkość wyszukiwania elementów słownika,
dlatego jest implementowany jako drzewo.
Klasa może być użyta jako klucz, jeżeli zapewnia operatory do porównywania elementów == oraz < lub jest typem wbudowanym zapewniającym te operatory domyślnie.
Przykład – słownik poleceń.
#include <map>
void main()
{
map<string,int>
dict;
dict.insert(map<string,int>::value_type("open",0));
dict.insert(map<string,int>::value_type("o",0));
dict["close"]=1;
dict["c"]=1;
dict["exit"]=-1;
map<string,int>::const_iterator
i;
for(i=dict.begin();i!=dict.end();i++){
cout<<i->first<<" ->
"<<i->second<<endl;
}
for(;;){
char command[256];;
cin.getline(command,256);
i = dict.find(command);
if(i==dict.end()){
cout<<command<<"
???";continue;
}
cout<<i->second<<endl;
if(i->second==-1)return;
}
}
Rezultat:
c -> 1
close -> 1
exit
-> -1
o
-> 0
open
-> 0
... Liczby
odpowiadające poleceniom
Jak widać, iterator słownika wypisuje elementy w porządku alfabetycznym.
Zbiór jest kontenerem, który przechowuje unikalne
wartości elementów. Szablon definiuje trzy podstawowe metody:
·
insert() – dodaje element
·
empty() – testuje czy zbiór jest pusty
·
find() – znajduje element w zbiorze
Zbiór może być traktowany
jak zdegenerowana postać słownika: zapisuje odwzorowanie klucz®wartość, ale to, w co odwzorowany jest klucz jest nieistotne: liczy się obecność
klucza w zbiorze.
Zbiór jest implementowany
jako drzewo, dlatego elementy zbioru muszą spełniać takie same wymagania
dotyczące interfejsu, jak klucze dla słownika: definiować operatory == oraz <.
Przykład
#include <set>
void main()
{
set<int>
cont;
cout<<(cont.empty()?"empty":"!empty")<<endl;
for(int
i=10;i>=0;i--)cont.insert(i);
for(i=5;i<15;i++)cont.insert(i);
cout<<(cont.empty()?"empty":"!empty")<<endl;
set<int>::const_iterator
it = cont.find(10);
if(it !=
cont.end())cout<<"has:"<<*it<<endl;
for(it=cont.begin();it!=cont.end();it++)
cout<<*it<<" ";
cout<<endl;
}
Rezultat
empty
!empty
has:10
0 1
2 3 4 5 6 7 8 9 10 11 12 13 14
Bilblioteka STL klasyfikuje
iteratory ze względu na możliwość:
·
odczytu (input
iterator) InIt
·
zapisu (output
iterator) OutIt
·
kierunek ruchu (w
przód FwdIt, w przód i tył BidIt,
random acces RanIt)
Nową cechą zmodyfikowanej
biblioteki iostream jest zdefiniowanie iteratorów umożliwiających
odczyt lub zapis do strumieni (traktowanych jak kontenery).
#include <list>
#include <iostream>
void main()
{
list<int> li;
istream_iterator<int> ist(cin);
for(;ist!=istream_iterator<int>();ist++){
li.push_back(*ist);
}
// istream_iterator<int>() –
koniec strumienia
for(int i=0;i<10;i++)li.push_back(rand()%10);
for(i=0;i<10;i++)li.push_front(rand()%10);
ostream_iterator<int> out(cout,
" ");
for(i=0;i<10;i++){
*out=i;
out++;
}
cout<<endl;
cout<<endl;
copy(li.begin(),li.end(),out);
cout<<endl;
li.sort();
copy(li.begin(),li.end(),out);
cout<<endl;
}
W nagłówku <algorithm> zdefiniowano szereg szablonów funkcji implementujących standardowe algorytmy
działające na kontenerach różnych typów (w tym strumieniach).
Parametrami tych funkcji są
zazwyczaj iteratory (wejściowe i wyjściowe) oraz dla niektórych algorytmów obiekty
funkcyjne.
Obiekty funkcyjne pozwalają
na adaptację działania algorytmu przez przekazanie do niego funkcji. Zamiast
wskaźnika do funkcji (w stylu C) przekazywany jest obiekt klasy, która
definiuje operator () . Operator () jako jedyny
może przyjąć dowolną liczbę argumentów – listę formalnych parametrów funkcji.
Przykład
template
<class T, class FO>
void
callFunctionObject(T&t,FO&foo)
{
foo(t);
}
class Incrementer
{
public:
void operator()(int&t)
{
t++;
}
};
void main()
{
int
x=10;
callFunctionObject(x,Incrementer());
cout<<x<<endl;
}
Rezultat: 11
Algorytmy STL wykorzystują w
zasadzie cztery podstawowe rodzaje funkcji (obiektów funkcyjnych):
·
Funkcja
jednoargumentowa (unarna)
·
Funkcja dwuargumentowa
(unarna)
·
Predykat
(jednoargumentowa funkcja zwracająca typ bool)
·
Predykat
dwuargumentowy (binarny)
Algorytm pozwala na przekopiowanie zawartości kontenera (wszystkie elementy lub pewien obszar) do innego kontenera w miejsce wskazane przez iterator wyjściowy.
#include <list>
#include <algorithm>
void main()
{
list<int> li;
for(int i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
list<int> li2;
li2.resize(li.size());
copy(li.begin(),li.end(),li2.begin());
copy(li2.begin(),li2.end(),
ostream_iterator<int>(cout,"
"));
cout<<endl;
}
Rezultat:
9 8 7 6 5 4 3 2 1
0 0 1 2 3 4 5 6 7 8 9
Algorytm oblicza liczbę wystąpień elementu w kontenerze.
#include <list>
#include <algorithm>
void main()
{
list<int>
li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
cout<<count(li.begin(),li.end(),0)<<endl;
}
Rezultat: 2
Algorytm oblicza liczbę elementów w kontenerze spełniających predykat przekazany jako obiekt funkcyjny.
#include <list>
#include <algorithm>
class LessThen
{
int v;
public:
LessThen(int _v){v=_v;}
bool operator()(int k){return k<v;}
};
void main()
{
list<int> li;
for(int i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
cout<<
count_if(li.begin(),li.end(),LessThen(3))
<<endl;
}
Rezultat: 6
Algorytm wykonuje dla każdego obiektu należącego do wskazanej sekwencji w kontenerze jednoargumentową funkcję przekazaną w postaci obiektu funkcyjnego.
#include <list>
#include <algorithm>
class Dump
{
public:
void operator()(int k){cout<<k<<"
";}
};
void main()
{
list<int> li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
for_each(li.begin(),li.end(),Dump());
cout<<endl;
}
Rezultat:
9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9
Algorytm działa na uporządkowanych kolekcjach elementów. Pozwala na sprawdzenie, czy wszystkie elementy danego kontenera są zawarte w drugim kontenerze. Algorytm może być używany do porównywania zbiorów.
#include <set>
#include <algorithm>
void main()
{
set<int>
s1;
for(int
i=0;i<20;i++){s1.insert(i);}
set<int>
s2;
for(i=0;i<10;i++){s2.insert(i);}
cout<<"s1
includes s2 "<<
includes(s1.begin(),s1.end(),s2.begin(),s2.end())
<<endl;
cout<<"s2
includes s1 "<<
includes(s2.begin(),s2.end(),s1.begin(),s1.end())
<<endl;;
}
Rezultat:
s1 includes s2 1
s2 includes s1 0
Algorytm
pozwala na wyznaczenie minimalnego elementu w kontenerze. Przykłady pokazują
dwie wersje wywołania algorytmu: opartą na naturalnym porządku elementów i z
dostarczonym obiektem funkcyjnym (dwuargumentowym predykatem) do porównywania
elementów.
#include <list>
#include <algorithm>
void main()
{
list<int>
li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
list<int>::const_iterator
m= min_element(li.begin(),li.end());
cout<<*m<<endl;
}
Rezultat: 0
#include <list>
#include <algorithm>
class
ReverseLess
{
public:
bool
operator()(int e1,int e2){return e1>e2;}
};
void main()
{
list<int>
li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
list<int>::const_iterator
m= min_element(li.begin(),li.end(),ReverseLess());
cout<<*m<<endl;
}
Rezultat: 0
Algorytm pozwala na zastąpienie w kontenerze każdego wystąpienia elementu o danej wartości nową wartością.
Przykład
#include <list>
#include <algorithm>
void main()
{
list<int> li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
replace(li.begin(),li.end(),5,-5);
copy(li.begin(),li.end(),
ostream_iterator<int>(cout," "));
cout<<endl;
}
Rezultat:
9 8 7 6 -5 4 3 2 1 0 0 1 2 3 4 -5 6 7 8 9
Algorytm zastępuje nową wartością wszystkie elementy spełniające określony
predykat przekazany jako obiekt funkcyjny.
Przykład
#include <list>
#include <algorithm>
class LessThen
{
int
v;
public:
LessThen(int
_v){v=_v;}
bool
operator()(int k){return k<v;}
};
void main()
{
list<int> li;
for(int
i=0;i<10;i++)
{li.push_back(i);li.push_front(i);}
replace_if(li.begin(),li.end(),LessThen(5),0);
copy(li.begin(),li.end(),
ostream_iterator<int>(cout,"
"));
cout<<endl;
}
Rezultat:
9 8 7 6 5 0 0 0 0 0 0 0 0 0 0 5 6 7
8 9