C ++ standard library

The C ++ standard library is the basic program library of the C ++ programming language defined by the C ++ standardization committee of the ISO . It contains a collection of the most important subroutines and other basic program components , for example various generic containers, functions for their manipulation, function objects, generic character strings (also called "strings"), data streams and the like. a. for file access, language support and simple functions (for example from mathematics ). It also contains the entire standard library for the C programming language .

Emergence

The C ++ library has its origins in the 1980s and was revised in the course of standardization through the influence of a library developed at Hewlett-Packard called the Standard Template Library (STL). Today the C ++ standard library is still often mistakenly called STL, even though they are two independent libraries.

Extensions

Since April 2006 there has been a library extension ( Technical Report 1, TR1 for short ). B. regular expressions , various smart pointers , hash containers and a random number library. The namespace was std::tr1 assigned to these extensions . Many of these extensions are suggestions to change the functions of the standard libraries. Some have been incorporated into the standard library as regular functions since the C ++ 11 standard was published. This means that they can now be reached directly via the namespace std.

Since 2012, new functions of the standard library and of C ++ are generally no longer formatted as technical reports but as technical specifications and are therefore included in the namespace std::experimental.

Components of the C ++ standard library

The C ++ standard library offers:

Container (container classes)
Iterators
Algorithms
Functional objects
Strings
Input and output
Localization
Numerics
Exceptions
RTTI (Runtime Type Information)
Random number generators and transformers for probability distributions (since C ++ 11)
Tools for multithreading (since C ++ 11)
Regular expressions (since C ++ 11)
Time measurement tools (since C ++ 11)

Most of the components of the C ++ standard library are available in the form of template classes . This concept has the great advantage of being reusable , for example containers for any data types can be created by simply declaring them; Algorithms apply to a wide variety of data types. In addition, templates ensure type safety during compilation, which minimizes runtime errors. One disadvantage is the extremely difficult to read error messages that are generated, for example, in the event of type conflicts.

Container

Containers (container classes) are objects that store other types of data and objects, for example lists and fields . The container provides methods and iterators to access the individual elements. The container takes care of the memory management for the elements and therefore has functions for inserting and deleting elements. The container owns the elements . This means that the lifetime of a saved object does not exceed the lifetime of the list. If the content is then required, the user must either make copies of it or use pointers allocated himself .

In sequential containers, the objects are arranged linearly. In associative containers, access takes place with the help of keys.

Sequential containers
Surname	Class name	description	Available since
Dynamic size fields, vector	`std::vector`	Insertion and deletion at the end is possible in and for other elements in . ${\ displaystyle {\ mathcal {O}} (1)}$ ${\ displaystyle {\ mathcal {O}} (n)}$ The container supports random access in . ${\ displaystyle {\ mathcal {O}} (1)}$
Fixed-size fields	`std::array`	The size must already be fixed during the compilation process.	C ++ 11
doubly linked lists	`std::list`	Insertion and deletion is possible in. Random access is not possible. ${\ displaystyle {\ mathcal {O}} (1)}$
simply linked lists	`std::forward_list`	Insertion and deletion is possible in. Random access and size inquiries are not possible ${\ displaystyle {\ mathcal {O}} (1)}$	C ++ 11
Queues	`std::queue`	The container does not support iterators.
Two-ended queues	`std::deque`	The data type behaves like the vector, but can insert elements at the beginning and end . ${\ displaystyle {\ mathcal {O}} (1)}$
Priority queues	`std::priority_queue`	Like the heap , the structure guarantees that the element with the highest priority is always at the beginning.
stack	`std::stack`	The container does not support iterators.

Ordered associative containers
Surname	Class name	description
amounts	`std::set` and `std::multi_set`	Sets are associative containers in which unique elements are stored as keys.
Associative fields (maps)	`std::map` and `std::multi_map`	Maps store elements together with their keys in a strict weak ordering . Each key has to be unique.

Disordered Associative Containers (also known as Hashmaps / Hashsets)
Surname	Class name	description	Available since
amounts	`std::unordered_set` and `std::unordered_multiset`	The sequence is sorted by a hash function. Only available since technical review 1 .	C ++ 11
Associative fields	`std::unordered_map` and `std::unordered_multimap`	In contrast to the map, the data is saved unsorted. Internally, hash tables are used as an index. Only available since technical review 1 .	C ++ 11

Other containers
Surname	Class name	description
Bit sets	`std::bitset`	The bitset behaves very similarly to a normal array, but is optimized for space consumption, since the smallest data type in C ++ is char with at least 7 bits.

Iterators

Iterators (from the Latin iterare : repeat) are intelligent pointers that can be used to iterate over the elements of a container and to access individual elements of the container. The iterators form a central concept for the containers. In relation to their task, the iterators are pure access objects. They decouple algorithms from the containers so that algorithms can be formulated independently of container types. The diagram below shows the relationship between the iterator and the containers and algorithms:

The iterators have the following categories:

Input iterators: read access for a single pass
Output iterators: write access for a single pass
Forward iterators: sequential access with relative reference to iterators, in one direction
Bidirectional iterators: like forward iterators, but in both directions
Iterators with random access: random access, also with index operator ([])

Not every container provides all iterators. The list container allows e.g. B. no random, but only sequential access. In contrast, the input and output exterators are very general and are always provided.

Algorithms

Algorithms are functions with specific manipulation rules that are applied to a container. They are independent of the specific implementation of the container. You can only access the elements in the containers through iterators. They contain u. a. the standard algorithms in computer science, such as B. Sorting algorithms or methods for generating random numbers. The most used are:

std::for_each: applies an operation to all elements of a data set
std::transform: transforms a data set with one function into another
std::copy: copies the data set to another
std::sort: sorts the record
std::find: searches for a specific element in a data set
std::search: searches for a row of elements in a data set

These and other algorithms are in the header <algorithm>.

Functional objects

Function objects or functors are objects that can be called as a function. The function operator " operator()" is overloaded here. There are the following categories of functional objects:

Generators without function parameter "f ()"
Unary functions with a function parameter "f (x)"
Binary functions with two function parameters "f (x, y)"

In principle, the algorithms of the C ++ standard library do not require any function objects with more than two parameters.

Strings

The character string library defines a class template std::basic_stringfor the representation of character strings ("strings") of variable length. The methods of the class template offer manipulations and operations, such as B. inserting, deleting, replacing and searching in character strings. There are two type definitions of this class template:

std::stringis an instantiation of std::basic_string, parameterized with char. charcan store a character from the basic character set.
std::wstringis an instantiation of std::basic_string, parameterized with wchar_t(wide character). wchar_tcan save all elements of the largest supported character set.

Examples

std::vector<int> daten(10); // Datenfeld mit int der Länge 10 anlegen, [0] .. [9]

// Iterator anlegen und initialisieren; Iterator zeigt dann auf ersten Eintrag (also Index 0).
std::vector<int>::iterator dIter(daten.begin());

// Zähler i initialisieren,
for (int i = 0;
     // Schleife solange durchgehen, bis dIter auf erste Position NACH dem Ende des Datenfeldes zeigt (also Index 10).
     dIter != daten.end();
     // Zähler i erhöhen, Iterator auf den nächsten Eintrag zeigen lassen.
     ++i, ++dIter) {
    // i dem Datenfeld zuweisen, auf das dIter zeigt.
    *dIter = i;
}
// daten: 0 1 2 3 4 5 6 7 8 9

std::vector<int> datenZwei(10);

std::copy(daten.begin(), daten.end(), // welche Daten sollen kopiert werden
    datenZwei.begin()); // und wohin
// datenZwei: 0 1 2 3 4 5 6 7 8 9

// binärer Funktor std::multiplies<int>() braucht zwei Argumente
std::transform(
    daten.begin(), daten.end(), // auf welchem Bereich soll Algorithmus arbeiten
    datenZwei.begin(), // zweite Datenquelle
    datenZwei.begin(), // wohin sollen Ergebnisse gehen
    std::multiplies<int>()); // miteinander multiplizieren
// datenZwei: 0 1 4 9 16 25 36 49 64 81

// unärer Funktor std::negate<int>() braucht ein Argument
std::transform(daten.begin() + 4, // dieses Mal nicht vom Anfang, sondern vom fünften Element an
    daten.end(), 
    daten.begin() + 4, // dito, Ziel
    std::negate<int>()); // Negation
// daten: 0 1 2 3 -4 -5 -6 -7 -8 -9

std::sort(daten.begin(), daten.end()); // sortieren
// daten: -9 -8 -7 -6 -5 -4 0 1 2 3

Web links

C ++ - Reference (English)
Apache C ++ Standard Library (STDCXX) (English)
Standard Template Library Programmer's Guide SGI

Individual evidence

↑ TR1 (PDF; 1.43 MB)
↑ cplusplus.com
↑ Container . sgi.com
↑ cplusplus.com bitset

[1] TR1 (PDF; 1.43 MB)

[2] usplus.com

[3] Container . sgi.com

[4] usplus.com bitset