Container sind nicht nur bei der Virtualisierung derzeit in aller Munde, auch dem Programmierer sind Behälter für Objekte nützlich. Die Version 11 von C++ enthält einige Algorithmen, die die Arbeit mit solchen Containern deutlich vereinfachen.

Zu den Methoden, die zwar schon eine Weile zu C++ gehören, nun aber neu in den Standard aufgenommen werden sollen, gehören etwa »std::any_of()« , »std::all_of()« und »std::none_of()« . Sie evaluieren alle Elemente eines Containers in einem Schritt. Auch die verschiedenen Varianten der »emplace()« -Methode, die Elemente eines Containers direkt in ihm erzeugt, gehören dazu. Und schließlich geht es um die Methode »shrink_to_fit()« für sequenzielle Container wie den »std::vector« . Mit dieser Methode lässt sich ein Vektor auf seine wahre Größe reduzieren.

Blick in die Zukunft

Die drei Funktionen »std::any_of()« , »std::all_of()« und »std::none_of()« benötigen einen Bereich und ein Prädikat. Sie ermitteln, ob mindestens eines, alle oder keines der Elemente eines Bereiches ein bestimmtes Prädikat erfüllen. Unter einem Prädikat versteht man dabei eine Funktion, die für jedes Argument den Wert »true« oder »false« zurückgibt. Listing 1 zeigt die drei praktischen Funktionen in der Anwendung.

01 #include <algorithm>
02 #include <iostream>
03 #include <vector>
04
05 int main(){
06
07  std::cout << std::boolalpha << std::endl;
08
09  auto even= [](int i){ return i%2 == 0 ;};
10
11  std::vector<int> myVec{1,2,3,4,5,6,7,8,9};
12
13  std::cout << "std::any_of(myVec.begin(),myVec.end(),even): " << std::any_of(myVec.begin(),myVec.end(),even) << std::endl;
14  std::cout << "std::all_of(myVec.begin(),myVec.end(),even): " << std::all_of(myVec.begin(),myVec.end(),even) << std::endl;
15  std::cout << "std::none_of(myVec.begin(),myVec.end(),even: " << std::none_of(myVec.begin(),myVec.end(),even) << std::endl;
16
17  std::cout << std::endl;
18
19 }

Das kleine Programm enthält nicht viel Überraschungspotenzial. Die drei Funktionen benötigen die Headerdatei »algorithm« in Zeile 1. Als Prädikat kommt die Lambda-Funktion (Zeile 9) zum Einsatz. Sie ermittelt, ob ihr Argument eine gerade Zahl ist. Abbildung 1 zeigt die Ausgabe des Programms.

Abbildung 1: »std::any_of()«, »std::all_of()« und »std::none_of()« auf einen »std::vector« angewandt.

Ein genauer Blick in die Onlinedokumentation der drei Funktionen [1] lohnt sich. Die Bereiche, auf denen die Funktionen agieren, werden durch Input-Iteratoren definiert. Zudem muss die Funktion ein Prädikat sein. So steht es in dem Abschnitt “Type Requirements” der Onlinedokumentation. Dabei stellen sowohl Input-Iterator [2] als auch Predicat [3] ein so genanntes Concept [4] dar.

Mit Konzept

Ein Concept definiert eine verbindliche Bedingung für einen Typparameter eines Template. Concepts sind den Typklassen in Haskell sehr ähnlich. Auch der nächste Standard C++17 wird mit großer Wahrscheinlichkeit Concepts erhalten. Diese heißen umgangssprachlich meist Concepts Lite und besitzen zwei große Vorteile. Zum einen beschreiben sie in der Template-Deklaration eindeutig die Bedingungen, die die Typparameter zu erfüllen haben, zum anderen erzeugt der Compiler nun gut leserliche Fehlermeldungen, falls die Bedingungen durch die Typparameter nicht erfüllt werden. Insbesondere für die viele Seiten langen Fehlermeldungen, die der Programmierer früher heraufbeschwor, wenn er ein Template mit unpassenden Template-Parametern verwendete, war C++ leider legendär.

Im konkreten Fall benötigen die Funktionen einen Input-Iterator. Das ist ein Iterator, der nur in eine Richtung vorwärtsschreiten und dabei jedes Element nur einmal lesen kann. Diese Eigenschaft erfüllen die Container der Standard Template Library und selbst ein Dateistream. Daher ist zugesichert, dass sich die drei Funktionen auch auf einem assoziativen Container wie »std::unordered_map« anwenden lassen (Listing 2).

01 #include <algorithm>
02 #include <iostream>
03 #include <string>
04 #include <unordered_map>
05
06 int main(){
07
08  std::cout << std::boolalpha << std::endl;
09
10  auto even= [](std::pair<int,std::string> p ){ return p.first % 2 == 0;};
11
12  std::unordered_map<int,std::string> myUnordMap{{1,"one"},{2,"two"},{3,"three"},{4,"four"},{5,"five"}};
13
14  std::cout << "std::any_of(myUnordMap.begin(),myUnordMap.end(),even): " << std::any_of(myUnordMap.begin(),myUnordMap.end(),even) << std::endl;
15  std::cout << "std::all_of(myUnordMap.begin(),myUnordMap.end(),even): " << std::all_of(myUnordMap.begin(),myUnordMap.end(),even) << std::endl;
16  std::cout << "std::none_of(myUnordMap.begin(),myUnordMap.end(),even: " << std::none_of(myUnordMap.begin(),myUnordMap.end(),even) << std::endl;
17  std::cout << std::endl;
18
19 }

Die Lambda-Funktion »even()« in Zeile 10 ermittelt für alle Paare »p« der »std::unordered_map« , ob deren Schlüssel »p.first« gerade sind. Die Antwort gibt die Ausgabe des Programms, sie fällt ähnlich aus, wie schon bei Listing 1 und in Abbildung 1 zu sehen.

So direkt wie möglich

Die Container der Standard Template Library enthalten viele Methoden, um diese um weitere Elemente zu erweitern. Gemeinsam ist diesen Methoden, dass sie das neue Element zuerst außerhalb des Containers erzeugen und dann in den Container kopieren oder verschieben. Das hört sich nicht nur umständlich an, das ist es auch. Allen Methoden gesellt C++11 ein Pendant hinzu, das das neue Element direkt im Container erzeugt. Exemplarisch ist das direkte oder indirekte Erzeugen der Elemente eines Vektors in Listing 3 und außerdem in der Abbildung 3 dargestellt.

01 #include <deque>
02 #include <iostream>
03 #include <map>
04 #include <vector>
05
06 class MyVal{
07 public:
08  MyVal(int i):val(i){
09  std::cout << "MyVal(" << i << ") " << std::endl;
10  }
11 private:
12  int val;
13 };
14
15 int main(){
16
17  std::cout << std::endl;
18
19  std::vector<MyVal> myVec;
20  myVec.push_back(MyVal(6));
21  myVec.emplace_back(MyVal(7));
22  myVec.insert(myVec.end(),MyVal(8));
23  myVec.emplace(myVec.end(),MyVal(9));
24
25  std::deque<MyVal> myDeq;
26  myDeq.push_back(MyVal(10));
27  myDeq.push_front(MyVal(11));
28  myDeq.emplace_back(MyVal(12));
29  myDeq.emplace_front(MyVal(13));
30
31  std::map<int,MyVal> myMap;
32  myMap.insert(std::make_pair(1,MyVal(14)));
33  myMap.emplace(std::make_pair(1,MyVal(15)));
34
35  std::cout << std::endl;
36
37 }

Abbildung 3: Direktes und indirektes Erzeugen der Elemente eines »std::vector«.

Die neuen Methoden lassen sich im neuen Standard leicht finden, enthalten sie doch alle den Ausdruck »emplace« im Namen. Abbildung 4 stellt die »emplace« -Variationen in der Anwendung dar.

Abbildung 4: »emplace«-Variationen in der Anwendung.

Mach mich kleiner

Sequenzielle Container wie der »std::vector« haben eine Größe und eine Kapazität. Die Größe bezeichnet dabei die Anzahl der Elemente, die der Vektor besitzt, wogegen die Kapazität die potenzielle Anzahl der Elemente meint, die der Container an der aktuellen Position im Speicher besitzen kann. Dass die Kapazität die Größe übersteigt, ist übrigens durchaus erwünscht, denn so lässt sich vermeiden, dass neuer Speicher angefordert und der Vektor gegebenenfalls verschoben werden muss, sobald ein neues Element hinzukommt. Das Verschieben eines Vektors wäre dann erforderlich, wenn er an seiner aktuellen Position nicht mehr wachsen kann.

Da das Anfordern wie das Verschieben von Speicher sehr teure Operation sind, befolgt der Vektor die Strategie, seine Kapazität um etwa 50 Prozent größer zu dimensionieren. Der Vektor verkleinert aber nicht seine Kapazität, falls der Programmierer seine Größe reduziert. Allein das Wachstum erfolgt in diesem Fall vollautomatisch.

Reserve unerwünscht

Wo es auf Speicherplatz ankommt, ist diese stille Reserve eines Vektors nicht immer erwünscht. Um die Kapazität eines Vektors »std::vector<int>v« auf seine tatsächliche Größe zu reduzieren, gibt es in C++ das Shrink-to-fit-Idiom: »std::vector<int>(v).swap(v)« .

01 #include <iostream>
02 #include <vector>
03
04 int main(){
05
06  std::cout << std::endl;
07
08  std::vector<int> myVec;
09  myVec.push_back(1);
10  myVec.push_back(2);
11  std::cout << "myVec.capacity(): " << myVec.capacity() << std::endl;
12  std::cout << "myVec.size(): " << myVec.size() << std::endl;
13
14  std::cout << std::endl;
15
16  myVec.reserve(100);
17
18  std::cout << "myVec.capacity(): " << myVec.capacity() << std::endl;
19  std::cout << "myVec.size(): " << myVec.size() << std::endl;
20
21  std::cout << std::endl;
22
23  myVec.shrink_to_fit();
24
25  std::cout << "myVec.capacity(): " << myVec.capacity() << std::endl;
26  std::cout << "myVec.size(): " << myVec.size() << std::endl;
27
28  std::cout << std::endl;
29
30 }

Dabei erzeugt »std::vector<int>(v)« einen temporären Vektor von natürlichen Zahlen, der nur die Elemente von »v« besitzt. Die »swap« -Methode des Vektors tauscht anschließend den Inhalt des temporären Vektors mit dem ursprünglichen Vektor »v« aus. Das geht in C++11 deutlich einfacher. Denn neben »std::vector« erhalten auch »std::deque« und »std::string« eine neue Methode »shrink_to_fit()« .

Listing 4 zeigt die neue Methode in der Anwendung: Gut ist in der Ausgabe des Programms in Abbildung 5 zu sehen, dass die Größe »myVec.size()« des Vektors genau seiner Kapazität »myVec.capacity()« (Zeilen 25 und 26) entspricht.

Abbildung 5: »shrink_to_fit« auf einen »std::vector« angewandt.

Wie geht es weiter?

Die Standard Template Library erhielt nicht nur neue Algorithmen und deren Container neue Methoden. Mit dem C++-Array »std::array« und der einfach veketteten Liste »std::forward_list« bietet C++ zwei neue Container an, die insbesondere auf minimale Speicheranforderungen getrimmt sind.

Hinzu kommt noch der heterogene Container »std::tuple« , der im Gegensatz zu seinem kleinen Bruder »std::pair« beliebig viele Elemente annehmen kann. Die Details dazu beschreibt die nächste Folge dieser Artikelserie.

Der Autor

Rainer Grimm arbeitet als Software-Architekt und Gruppenleiter bei der Metrax GmbH in Rottweil. Besonders die Software der hauseigenen Defibrillatoren ist ihm eine Herzensangelegenheit. Seine Bücher “C++11 für Programmierer”, “C++” und “C++11-Standardbibliothek” sind bei O’Reilly erschienen.