Cpp standard containers

C++ standarten definerer en lang række standart general purpose containere til brug i mange forskellige situationer. Man bør overveje om man kan bruge en af disse inden at man gå i gang med at kode sin egen løsning - ligeledes kan disse være at foretrække frem for containere der kommer sammen med et bestemt toolkit, da C++'s for det første er template baserede og derfor virker på alle former for data og for det andet er man sikker på at std. containerne er tilgængelige hvis man skulle flytte til et andet toolkit / platform.

• std::vector
• std::list
• std::stack
• std::queue
• std::deque
• std::priority_queue
• std::set
• std::map
• std::multi_map

TR1 (men ikke ISO) containers:

• std::hash_set
• std::hash_map

Eksempler

Her præsenterer jeg nogle eksempler på nogle af C++'s forskellige container klasser. Eksemplerne viser et typisk brug af containerne men kan langt fra vise alle aspekter og funktioner.

Læg mærke til at mange af disse containere kan kombineres med funktionerne fundet i <algortihm>

Alle eksempler antager at man har inkluderet std namespacet vha.:

using namespace std;

Vector eksempel

Vector'en kan betragtes som et dynamisk udvideligt array. Istedet for subscripting operatoren [] kan man bruge vector::at(int n) funktionen som lavet et tjek på index-tallet og ser om dette er inden for 0<=n<size. Husk at vector'en også har funktionerne back() til at se det sidst indsatte object og pop_back() til at fjerne det sidste tal

vector<int> vec;

vec.push_back(2);
vec.push_back(5);
vec.push_back(7);

for (int i=0; i<vec.size(); i++)
{
	cout << vec[i] <<",";
}
cout << endl;

Vector og iterator eksempel

Som ovenstående, men bruger en iterator i stedet for en indexerings variabel

vector<int> vec;

vec.push_back(2);
vec.push_back(5);
vec.push_back(7);

for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
{
	cout << *it << ",";
}
cout << endl;

Stack eksempel

En ganske almindelig stack

Output: 7,5,2,

stack<int> stck;
stck.push(2);
stck.push(5);
stck.push(7);

while (!stck.empty() )
{
	cout << stck.top() << ",";
	stck.pop();
}
cout << endl;

Queue eksempel

queue<int> q;
q.push(2);
q.push(5);
q.push(7);
while (!q.empty() )
{
	cout << q.front() << ",";
	q.pop();
}
cout << endl;

Deque eksempel

Deque = double-ended queue, dvs. en kø hvor at man kan tilføje/fjerne i begge ender.

Læg mærke til at de to første inserts sker i bagenden og den 3. skubbes ind forrest

deque<int> dq;
dq.push_back(5);
dq.push_back(7);
dq.push_front(2);

while (! dq.empty() )
{
	cout << dq.back() << ","; //kunne også have brugt front()
	dq.pop_back(); // kunne have brugt pop_front()
}
cout << endl;

Priority queue eksempel

Priority_queue = prioriteret kø hvor data med højeste prioritet kommer forrest. Kræver at dataene kan sammenlignes med < operatoren. I dette eksempel defineres en klasse som implementerer en < operator.

Output:

Bent : 60
Finn : 41
Per : 12

/*
 * Simpel storage klasse til at repræsentere en person med tilhørende alder
 */
class Person
{
public:
	string name;
	int age;
	Person(string n, int a) {name = n; age=a;} 

	//Sammenlign to personer ud fra deres alder
	//operator overloading af less-than operatoren
	//husk at en operator som denne skal være const
	bool operator< (const Person& p) const {return age < p.age;}
};

priority_queue<Person> pq;
pq.push( Person("Per", 12) );
pq.push( Person("Bent", 60) );
pq.push( Person("Finn", 41) );

while (!pq.empty()) //Udskriv personerne efter alder
{   
	cout << pq.top().name << " : " << pq.top().age << endl;
	pq.pop();
}
cout <<endl;

List eksempel

List er en dobbelhægtet liste. Studér selv funktionerne list::splice(), list::merge() og list::sort()

output: 7,12,2

list<int> lst;
lst.push_back(2); //kunne også have brugt push_front();
lst.push_back(5);
lst.push_back(7);

list<int>::iterator it = lst.begin();

it++; //iterér frem til værdien 5
lst.erase(it); //fjern det element som iteratoren peger på, herefter er iteratoren invalid og skal re-initialseres

//man kunne også have fjernet 5 med lst.remove(5), men så skal man have en værdi/object der matcher det der skal fjernes
//og kræver at objektet kan sammenligned med == operatoren

it = lst.begin();
it++; //iterér frem til værdien 7
lst.insert(it,12); //indsæt en ny værdi på iteratorens plads

//demonstrér en reverse iterator
for (list<int>::reverse_iterator it = lst.rbegin(); it != lst.rend(); it++)
	cout << *it << ",";

cout << endl;

Søgning i en liste

/* Sådan kan man bruge find() til at søge i en std::list */

#include <list>
#include <iostream>

using namespace std;

int main()
{
   typedef list<int>::iterator ListIt;
   list<int> ints;

   ints.push_back(3);
   ints.push_back(5);
   ints.push_back(7);

   ListIt it1 = find(ints.begin(), ints.end(), 3);
   if (it1 != ints.end())
       cout << "Has 3" << endl;
   else
       cout << "No 3"<< endl;

   ListIt it2 = find(ints.begin(), ints.end(), 4);
   if (it2 != ints.end())
       cout << "Has 4" << endl;
   else
       cout << "No 4"<< endl;
}

Find alle elementer i en liste

#include <list>
#include <iostream>
#include <vector>
#include <algorithm>

template<class In, class T> std::vector<typename In::iterator>  find_all( In& container, const T& val)
{
   std::vector< typename In::iterator > buffer;

   typename In::iterator start = container.begin();

   while ( true )
   {
       typename In::iterator it = find(start, container.end(), val);
       if (it != container.end())
       {
           buffer.push_back(it);
           start = it;
           start++;
       }
       else
           break;
   }
   return buffer;
}


int main()
{
   std::list<int> l;
   l.push_back(3);
   l.push_back(4);
   l.push_back(4);
   l.push_back(4);
   l.push_back(5);

   std::vector<std::list<int>::iterator> v = find_all(l, 4);

   std::cout << "Found " << v.size() << " instances of 4" << std::endl;
}

Map eksempel

Map er en associativ container dvs. at der et data par (key & value) med et bestemt sammenhæng - se også på std::pair klassen.

Klasser i familie med map: set, multi_map, hash_set og hash_map

Output:

We have 5 hammers in stock
hammers : 5
nails : 1000
screwdrivers : 20

typedef map<string,int>::iterator MapIt;
map<string,int> inventory;

inventory["hammers"] = 5; //hvis der ikke er et entry for "hammers" oprettes det automatisk
inventory["nails"] = 1000;
inventory["screwdrivers"] = 20;

cout << "We have " << inventory["hammers"] << " hammers in stock" << endl << endl;

//udskriv hele inventar listen
for (MapIt it = inventory.begin(); it != inventory.end(); it++)
{
	cout << (*it).first << " : " << (*it).second << endl;
}