Container

Es gibt verschiedene Konzepte, welche in einem Container in der STL vereint sind. Zum einen kann man auf alle STL Container über Iteratoren zugreife, dafür verfügen sie über begin() und end() Methoden. Zum anderen sollte der Inhalt in einem Container kopierbar sein, denn es wird beim Einfügen in den Container immer das Element kopiert. Bei einer Klasse heißt dies, das der Copykonstruktor aufgerufen wird. Mit C++11 kommen einige neue Container in den C++ Standard, neben einer single-linked List (std::slist) auch HashMaps und HashSets (std::unordered_map/set), sowie std::array, welches aber ein statischer Container ist, welcher nicht in der Größe veränderbar ist.

Die STL Container std::vector und std::deque verhalten sich wie arrays, welche ihre Größe dynamisch ändern können und über einen Indexoperator ([]) verfügen. Mit C++11 kommt hier noch std::array hinzu, welches eine Wrapperklasse für ein statisches Array ist. Hiermit bekommt man also ein normales Array mit den Schnittstellen der STL Container.

Ein kurzes Beispiel:

 

std::deque<int> mydeque;
std::vector<int> myvec;
for(int i = 0; i < 10; ++i)
{
    if(i % 2 ==0)
        mydeque.push_back(i);
    else
        myvec.push_back(i);
}
for(int i =0; i < 5; ++i)
    std::cout << mydeque[i] << std::endl << myvec[i] << std::endl;

Es werden jeweils in den std::vector und std::deque int Variablen gepusht, und danach ausgegeben.

Ein weiterer dynamischer Containertyp sind Listen, wo die verschiedenen Elemente im Speicher untereinander verlinkt sind. Mit Hilfe von Iteratoren kann man durch den Inhalt einer Liste iterieren, einen Indexoperator (wie in anderen Sprachen) gibt es für die Standard Listen nicht, würde er doch nur umsetzbar sein mit dem iterieren aller vorheriger Elemente. Dies ist aber z.b. mit der Funktion std::advance möglich, diese nimmt einen Iterator auf die Liste sowie die Anzahl der Iterierungen. Eine weitere Sonderform ist std::string, welches ebenfalls viele Methoden mit den Containern teilt, denn aus C++ Sicht sind Strings auch Container für Characterzeichen.

Ein kurzes Beispiel:

 

std::list<int> mylist;
for(int i = 0; i < 10; ++i)
{
    mylist.push_back(i);
}
std::list<int>::iterator it = mylist.begin(),end = mylist.end();
std::advance(it,5);
mylist.erase(it);
it = mylist.begin();
for(; it != end; ++it)
{
    std::cout << *it << std::endl;
}

Ähnlich wie oben werden einfach Dummyzahlen in die Liste gepusht. Neu ist der Zugriff über Iteratoren, dieser ist auch auf alle anderen STL Container genauso möglich. Durch den Aufruf von std::advanced zeigt der Iterator 'it' auf das 5 Element der Liste. Dieses wird nun mit der Methode erase gelöscht. Danach wird durch die gesamte Liste iteriert, und der Wert jeweils ausgegeben. Um auf den Inhalt eines Iterators zu zugreife, kann man diesen mit * dereferenzieren, Iteratoren verhalten sich hier ähnlich wie Pointer, zumindest von der Syntax her.

Assoziative Container bietet die STL auch. Hier gibt es einmal std::map und std::multimap welche jeweils einen Container für Datenpaare (std::pair) darstellen, und std::set welches sicherstellt, das es jeden Wert innerhalb des Containers nur einmal gibt. Es gibt auch ein std::multiset. Mit C++11 kommen auch Hash basierte Container (unordered_[multi]map, unordered_[multi]set.

Ein kurzes Beispiel:

 

std::set<int> myset;
std::map<int,int> mymap;
for(int i = 0; i < 10; ++i)
{
    myset.insert(i);
    mymap.insert(std::make_pair(i,i*i));
}
myset.insert(5);
std::set<int>::iterator set_it = myset.begin(), set_end=myset.end();
for(;set_it != set_end;++set_it)
    std::cout << *set_it << std::endl;
std::map<int,int>::iterator map_it=mymap.begin(),map_end = mymap.end();
for(;map_it != map_end;++map_it)
    std::cout << map_it->first << " * " << map_it->first << " = " << map_it->second << std::endl;
 

Für die Befüllung dieser Container muss insert genutzt werden, da sie per Definition kein Anfang oder Ende haben, an das man anfügen könnte. Die Werte werden intern in einem Baum verwaltet, welcher nach dem Key aufgebaut ist. Bei Map ist dies der erste Wert, der Zweite wird als Value bezeichnet, bei Set ist Key = Value. Auch erwartet Map bei insert ein std::pair, welches man mit std::make_pair erzeugen kann.

Die Ausgabe erfolgt wieder über Iteratoren, allerdings mit der Besonderheit, dass bei map auf die Werte mit first und second zugegriffen wird.

Es gibt noch einige weitere Container wie std::bitset, std::stack, std::queue und std::priority_queue.