Who wrote STL for c ++

The STL is a highly flexible collection of template classes. Unfortunately, this flexibility comes with a complexity that makes it difficult for the beginner to understand the STL. That will probably be the reason why it is not used by some C ++ programmers and is completely ignored by some C ++ books.

approach

So that you can benefit from the possibilities of the STL, I choose a practice-oriented, somewhat simplified approach. First, you will use arrays to see which algorithms the STL offers. Only then will you get to know the containers. These are data containers defined as templates in which you can store your own data. The algorithms were actually written primarily for these containers. In the third step, the iterators are examined in more detail.

Algorithms and arrays

The STL offers a number of algorithms that work on data containers. The simplest data container could be an array, on which the algorithms are first considered. In order to be able to use the algorithms, you have to include the appropriate header file and the namespace on hours set: #include using namespace std;

Algorithms and iterators

The STL's algorithm library contains functions that are given the area on which they are to work as parameters. The range limits are determined by iterators. The initial iterator points to the first element and the end iterator to the element after the end. With an array, a simple pointer can be used as an iterator replacement. If the algorithm is to work on the entire array, the address of the array is transferred as the initial iterator. The number of elements in the array is simply added to the pointer as an end iterator. The end iterator then points after the last element.

Search

The function searches in the container, the limits of which are specified by the first two parameters, for an element that is specified in the third parameter. The return value is an iterator on the first element found. In this simple case where an array is used as a container, that iterator is simply a pointer. If all elements are to be found, the returned pointer can be incremented and used as the start of the next search.

example

The following example program searches for the number 4 in the integer array. The result here is a pointer to an integer.

[Search for a number in an array (stl / find.cpp)]

#include #include using namespace std; int main () {int numbers [9] = {1,2,3,4,5,6,7,8,9}; int * found; found = find (numbers, numbers + 9, 4); if (found! = numbers + 9) {cout << "Found:" << * found << endl; } else {cout << "Nothing found!" << endl; }}

Failure

If no value was found in the area, the result pointer is identical to the pointer of the end of the area. This points to the first element behind the area to be searched for.

sort by

The function sorts an area of ​​a container. Again, the range is given by the iterators. For the sake of simplicity, an array is again used as the container. Pointers to serve as iterators.

[Sorting an array (stl / sort.cpp)]

#include #include using namespace std; int main () {int numbers [9] = {3,8,1,9,5,6,4,2,9}; sort (numbers, numbers + 9); for (int i = 0; i <9; i ++) {cout << numbers [i] << endl; }}

requirement

The algorithm works on arrays and vectors because it requires direct access to the elements via square brackets. [1] Furthermore, the function can only be used for types for which the less than operator is defined.

Copy: copy ()

The function copies an area of ​​an array into another array.

[Copy]

int main () {int numbers [9] = {1,2,4,9,5,6,7,8,9}; int target [5]; copy (numbers, numbers + 5, destination); }

Here are the first five elements of the array numbers into the array aim copied. The function does not check whether the capacity of the target is exceeded. The function also works with different containers.

Turn around: reverse

The function swaps the elements of the container in such a way that they are in reverse order after the call. The following example uses two STL algorithms. First, the argument of the program call with the call to in a local array named word copied. The function that reverses the character string is then applied to this array.

[Rotate transfer parameters (stl / reverse.cpp)]

#include #include #include using namespace std; int main (int argc, char ** argv) {char word [80]; copy (argv [1], argv [1] + strlen (argv [1]) + 1, word); reverse (word, word + strlen (word)); cout << word << endl; }

Any text can be transferred as a parameter when the program is called. As a result, the program outputs this text in reverse order.

Fill: fill

The function fills an array with values. The beginning and the end of the area to be filled are specified as parameters and the value with which the container is to be filled as the third parameter.

[To fill]

int main () {int numbers [9] = {1,2,4,9,5,6,7,8,9}; fill (numbers, numbers + 9, 4); }

Every element of the array numbers is filled with the value 4.

equal ()

The function can be used to check two areas for equality. The beginning and end of the output range are initially specified as parameters. The third parameter is the start of the range to be compared with: if (equal (numbers, numbers + 3, cf.))

The statement after the is executed when the first three values ​​of the array numbers equal to those of the array see are.

Functions as parameters

Some of the STL functions call functions that are passed to them as parameters. A simple representative is the function. Your third parameter is a function, the return type of which must be and the parameter of which must be of the type that the container is taking.

predicate

In propositional logic, a Boolean term is called a predicate. This designation is used in the STL for functions with a return type. Like the function, the function searches an area of ​​a container. However, a constant value is not transferred as the third parameter, but a function that is called by for each element of the area to be searched. If this function supplies the value, the function ends and supplies the iterator (in this simple case a pointer) to the value found as the return value. So that the element to be checked can be transferred to the predicate, it must accept a parameter of the type whose variables the container accepts as elements.

Flexible

The function can be used to search for elements that are only the same in certain partial properties or that are searched for on the basis of properties that cannot be expressed by the simple combination of logical operators.

example

The following program uses the function as a predicate. The function must have a transfer parameter of the type and return. As its name suggests, it becomes true when the passed parameter is 9.

[Search for a number in an array]

#include #include using namespace std; bool is nine (int parameter) {return (parameter == 9); } int main () {int numbers [9] = {1,2,3,9,5,6,7,8,9}; int * found; found = find_if (numbers, numbers + 9, is nine); if (found! = numbers + 9) {cout << * found << "-" << endl; } else {cout << "nothing" << endl; }}

Since a function is extremely flexible, you can search for almost all criteria. For example, the predicate could determine whether the number is a prime number. In some cases, however, a function is still not flexible enough. Let us consider the case that we are looking for the first number that is smaller than its predecessor in the container. In the previous example this would be 5. As a function, you could formulate it like this:

bool KleinerAlsVorgaenger (int parameter) {static last = INT_MIN; bool return; return = parameter Recurrence trap In fact, it works wonderfully the first time you use it. However, the function becomes unusable immediately afterwards, since it is in its static variable last has noticed the value 5. If it were used again for the same array, 1 would already be reported as the number sought because it is less than 5. To solve this problem, you could use the variable last use as a global variable that must be reset before calling. Apart from the fact that global variables should be avoided, this solution leaves a bad taste in the mouth.

Functional object

When it comes to initialization problems, a class can be used. Here a variable can easily be reset in the constructor. The function operator can be overloaded to meet the requirements of the function. The full program looks like this:

[Use of a function object (stl / findif.cpp)]

#include #include #include using namespace std; class tKleinerAlsVorgaenger {public: tKleinerAlsVorgaenger () {last = INT_MIN; } bool operator () (int a); private: int last; }; bool tKleinerAlsVorgaenger :: operator () (int a) {bool return; return = a boundary conditions It should not go unmentioned, however, that for each call to a new object of the class Smaller than the predecessor must be used for the constructor to use the data item last can reset. Alternatively, of course, a member function could be built into the class that does this. But you can also use the following variant: found = find_if (numbers, numbers + 9, tKleinerAlsVorgaenger ());

This is where the class constructor Smaller than the predecessor called, which passes a temporary object to the function, which in turn is called as a predicate. Then the line with the definition of the variable could also be used relapse be omitted.

for_each

Functionality

The function executes the function that is passed as the third parameter for all elements of a container, the limits of which it is passed in the first two parameters. The following example calls the function for each element that outputs the element on the screen. The result of the program is therefore an output of the array on the screen.

[Output via for_each (stl / foreach.cpp)]

#include #include using namespace std; int show (int a) {cout << a << endl; } int main () {int numbers [9] = {1,2,4,9,5,6,7,8,9}; for_each (pay, pay + 9, show); }

The parameter of the function must accept an element of the container. The return value should be of the same type. The function passes the return value of the last function on to its caller.

Containers and Iterators

Template container

The algorithms of the STL were not specially developed for arrays, but for the various containers that the STL offers the programmer. A container is a data structure that holds and organizes other data. An example of such a container can be a list or a tree. Since the containers are based on templates, any data types can be stored in the containers. How a data holder can be created for any data type with the help of templates was already discussed with the class Stack shown.

specialization

The STL offers very different containers. They are specialized for certain missions. Vectors are optimal when the individual elements have to be accessed at will. A list is ideal when the number of elements fluctuates extremely, and trees are suitable for data that needs to be sorted and quickly found.

Iterator

The STL uses iterators to access the elements of the container. They are very similar to pointers, but are adapted to their containers. They form the link between the container and the application.

The container class vector

Flexible array

The vector is arguably the easiest container to understand. It is similar to the array, but is much more flexible. As with an array, all elements are located next to each other in memory and can be accessed directly by their position number. Even the square brackets work like you know from the array.

In the following example, the lottery numbers are implemented as known with an array:

int main () {const int MAX = 6; int lotto [MAX]; for (int i = 0; i int main () {const int MAX = 6; std :: vector lotto (MAX); for (int i = 0; i dynamics In the case of the lottery, we know that there are six values ​​and that there are not surprisingly more. In many cases, however, one does not know beforehand how many values ​​are to be expected.

In the following example the vector is defined without specifying a size. The vector function push_back adds a value to the vector at the end. The size of the vector changes constantly. The current size of the vector supplies its function size.

#include #include int main () {const int MAX = 6; std :: vector lotto; for (int i = 0; i Capacity and size So that memory does not have to be requested each time it is added, a few more fields are reserved in advance when the size changes. This expansion is called capacity. This is the reserve that can be filled before an enlargement leads to a new memory area being created and the previous vector to be copied over.
  • The information about the size is provided by the member function. The size of the array can be changed using the member function. The parameter indicates the future size.
  • The capacity can be determined using the member function. The function can be used to expand the capacity. The parameter indicates the future capacity.

Crossing borders

Access outside of the capacity does not lead to the program being terminated. The number 12 is placed outside the reserved area. You can also output the value afterwards. However, it is not in the control area of ​​the vector. So you don't know where the value is going and you have to expect that the value will reach into another variable and generate incalculable errors. #include int main () {std :: vector v (16); v [2000] = 12; // Uncontrolled memory change

Access via the square brackets should be as efficient as possible. So C ++ foregoes an exam. However, if the verification is desired, you can access it via the member function at To run.

#include

In contrast to the access via the square brackets, the access via the member function is checked and an exception is raised in the event of errorsout_of_range out.

Algorithms

The library of algorithms demonstrated above using arrays also works on a vector. In fact, the STL's algorithm library was primarily developed for the containers. That they also work on arrays is actually a side effect.

example

So let's look at the sorting of a vector. First the vector is filled with random numbers. The function is then called with the start and end iterator as parameters.

[Sorting a Vector]

#include #include #include using namespace std; int main () {int MaxVec = 9; vector numbers (MaxVec); srand (0); for (int i = 0; i Iterators When the function is called, the limits are not determined by the pointers to the first and after the last position, as is the case with the array. In contrast to an array variable, the object exists numbers the class vector yes not from the data elements. A pointer on numbers points to the object that manages the data. Iterators are used to describe the limits of the vector. All container classes have the member functions to provide an iterator on the first element and the member function that returns the iterator that points after the last element. The iterator of a vector is very similar to a pointer, since the structure is linear in memory. Not only can you walk forwards and backwards through the container, you can also access individual elements directly. Because of its ease of use, this iterator is also called "Random Access Iterator", translated as "Iterator with random access".

Binary search

If there is a sorted area in a vector, the function can be used to search for a value in it. This search is very fast, but depends on the elements of a container being directly accessible. Accordingly, it can be used for vectors and arrays, but not for linked lists. if (binary_search (numbers.begin (), numbers.end (), search value))

The function returns a Boolean value, depending on whether the value was found or not. The following table shows the most important member functions of the container vector in an overview: [The most important member functions of vector]

function importance
begin () Returns the first position of the vector
end() Shows behind the last position of the vector
at (int) Approved access to element of the vector
size () Returns the number of elements in a vector
capacity () Returns the capacity of a vector
resize (int) Changes the size
reserve (int) Changes the capacity

Vector as a stack

push_back ()

Functions are defined for the vector that make it possible to implement a stack with the vector. By calling the member function, elements can be added at the end of the vector. A value of the type via which the vector is defined is transferred to the function as a parameter. The vector grows in size by one.

back ()

There is a function to read the last element. The function has no parameters and only returns the value of the last element. The stack or the vector is not reduced.

pop_back ()

The function removes an element from the stack. This function also has no parameters. It has the return type, so it does not return the value of the last element, nor does it indicate whether the operation was successful. This is particularly unfortunate because, for example, the GNU compiler sets the vector size to 4,294,967,295 in the event of an excess pop. The value must therefore be read out with the function before calling. The application must ensure that no pop is executed on an empty stack.

[Stack functions of the vector]

#include #include using namespace std; int main () {vector numbers; Numbers.push_back (8); Numbers.push_back (7); Numbers.push_back (6); do {cout << ":" << numbers.back (); Numbers.pop_back (); } while (numbers.size ()); cout << endl; }

The container class deque

The container deque (The word is pronounced like "deck." You will probably be better understood if you say "double ended queue.") Acts much like a vector. For example, the index operator is available. So you can access an element using the square brackets. However, there is no way to determine or inquire about the capacity. The name “double ended queue” (roughly translated: snake with two ends) already indicates that the container can grow not only at the end, but also at the beginning. You can visualize a deque as two vectors. One vector realizes the beginning, the other the end of the deque. The index numbers are counted from the first element to the last. If an element is added at the beginning, the numbering for each element is increased by one, and the new element is given the number 0. For the user of the Deque, the impression arises as if all elements have been moved by one position.

Here in the book is the figure "Deque" (picdeque)

Functions

In order to be able to work at the beginning of the list, there are functions that correspond to those for the end of the list. The function returns the first element. With the function, a new element is added at the beginning of a deque. The function expects the new element as a parameter. Finally, there is the function that removes an element from the beginning of the deque. The functions known from the vector,, and are used to carry out the operations at the end of the deque.

gpexample

The following example shows a FIFO buffer (FIFO: first in first out). Each queue is a FIFO. Whoever got in line first comes first in line. The elements appear in the order in which they were placed. In the example, a thousand times a thousand elements are pushed into the buffer and then taken out again immediately. The function counts the CPU ticks and is therefore used to measure the runtime.

[Deque as FIFO (stl / deque.cpp)]

#include #include using namespace std; #include int main () {clock_t start, end; start = clock (); deque buffer; for (int i = 0; i <1000; i ++) {for (int j = 1; j <1000; j ++) {buffer.push_front (j); } do {buffer.pop_back (); } while (buffer.size ()); } end = clock (); cout << start << ":" << end << endl; }

If you instead deque the container list using the next section, you will find that the deque is much faster. The reason lies in the internal structure. The measurement shows that it is important to know which container is optimal for the desired application. The following list summarizes the functions with which elements can be attached and removed at the beginning and at the end:

push_front (obj)
An object is inserted at the beginning of the list.
push_back (obj)
An object is inserted at the end of the list.
pop_front (obj)
An object is taken from the beginning of the list.
pop_back (obj)
An object is taken from the end of the list.
front (obj)
Returns a reference to the element at the beginning of the list.
back (obj)
Returns a reference to the element at the end of the list.
While it is possible to insert and delete elements from the middle, it is less efficient. If these operations are required more frequently, the container should list be used. The insertion takes place via the member function. Elements are deleted again with.

The container class list

Double chained

While the vector is similar to an array, the container is similar list more of a doubly linked list and should be implemented that way in most cases. A linked list was already presented at various points in the book when the stack was programmed. Each element points to the next element with a pointer. The elements can be located anywhere in the memory. That is why this container does not have to be copied over when it grows. A new element is requested and integrated into the chain. To get to the last element, the program has to work its way through from element to element. A doubly linked list is structured so that each element has two pointers. One pointer points to the successor, the other to the predecessor in the list. This leads to a certain amount of extra work when attaching new elements. This makes it easier to attach or detach elements at both ends and to navigate in both directions.

Advantages and disadvantages

Compared to the deque or the vector, a list is particularly advantageous if new elements are to be added or deleted in the middle of the list. In a list, the other elements do not have to be moved to make room or to fill a gap. When inserting with, space is requested for an element. It is hooked into the chain at the point designated by the iterator. The neighboring elements do not have to be arranged next to one another, and therefore they do not have to be moved. The same goes for deleting it from the middle of the list with. The gap does not need to be filled. The price for this is that it is not very efficient to access a particular item on the list by its position. To reach the fiftieth element, the program has to move fifty times. For this reason, the list does not support access using the square brackets.

List iterators

You need an iterator to designate a position in the list at which new elements are to be inserted or existing ones to be deleted. Each container contains the definition for a suitable iterator under the name iterator. In order to define such an iterator, the container type must first be named. This is followed by two colons to indicate that the iterator type defined in this class is meant, and then of course the name of the iterator. The following line defines an iterator for an integer list: list :: iterator IntegerListenIterator;

begin () and end ()

In order to use the iterators, they have to be initialized. They are typically initially placed at the top of the list. The member function always supplies the initial iterator of a container. In order to run through the container, the iterator is incremented. The element function of the container returns the iterator position after the last element. As soon as the run parameter is equal to the return value of, the run is finished. This results in the following typical loop for iterating through a list: list :: iterator Iter; for (Iter = List.begin (); Iter! = List.end (); ++ Iter) If a position is found within such a loop at which a new element is to be inserted, then Iter used as the first parameter for the member function. The iterator points to the list element before which the new element is to be inserted. List.insert (iter, new element);

The function is used to remove an element from the list. Your only parameter is the iterator that points to the list item that you want to delete. Since this iterator becomes invalid after deletion, the function returns the iterator that points to the next element. This iterator is required if the list is to be continued through after deletion.

Iter = list.erase (iter);

Extinguishing is a little ticklish as it's easy to saw off the branch you're sitting on.

for (auto iter = c.begin (); iter! = c.end (); / * do not increment * /) {if (kannWeg (iter)) iter = c.erase (i); else ++ iter; }

example

The following listing is used to play around with a list to demonstrate the various function calls.

[List games]

#include #include using namespace std; int main () {list numbers; list :: iterator lIter; // define iterator srand (0); for (int i = 0; i <10; i ++) {numbers.push_back (rand ()% 9 + 1); } // Run through and display for (lIter = numbers.begin (); lIter! = Numbers.end (); ++ lIter) {cout << * lIter << endl; } // insert a -1 before every 8 and delete every 2 for (lIter = numbers.begin (); lIter! = numbers.end (); ++ lIter) {if (8 == * lIter) {numbers.insert (lIter, -1); } else if (2 == * lIter) {lIter = numbers.erase (lIter); }} // Run through and display for (lIter = numbers.begin (); lIter! = Numbers.end (); ++ lIter) {cout << * lIter << endl; }}

Here, too, the program is explained step by step. The listing begins with the definition of the list:

list numbers;

The list includes values. It should contain numbers, that's why it's called a little unimaginative numbers.

list :: iterator lIter; // define iterator

Next, an iterator is created. It should later run through the list and form the basis for inserting and deleting elements. But first the list should be filled:

for (int i = 0; i <10; i ++) {numbers.push_back (rand ()% 9 + 1); }

In this loop, ten random numbers are simply formed and appended to the end of the list with the help of the member function.

// Run through and display for (lIter = numbers.begin (); lIter! = Numbers.end (); ++ lIter) {cout << * lIter << endl; }

Here you can see how the iterator works. As a start instruction, the iterator is set to the beginning of the container. The member function returns an iterator that points to the beginning of a container. The member function returns the position after the last element. As soon as the iterator has reached the end of the list, it will have the same value that the function returns. As long as the iterator is not equal to the return value of, the loop is not exited. The iterator can be increased by the increment operator. Another property of the iterator can be seen within the loop. It can be used like a pointer when accessing the object. The iterator is prefixed with an asterisk to reach the element it points to. A loop then begins again and runs through the list. To demonstrate inserting and deleting, a -1 should be inserted in front of every 8 and every 2 should be deleted.

if (8 == * lIter) {numbers.insert (lIter, -1);

Whether the list element contains an 8 is checked again by accessing the iterator with the asterisk. Then the member function of the list is called. It contains the current iterator as the first parameter. The new element is inserted at the position of the iterator - and thus before the current element. The second parameter of contains the new object to be inserted, here the -1.

lIter = numbers.erase (lIter);

The function is used to delete. As a parameter, it receives the iterator on the object that is to be deleted. The iterator that is passed as a parameter becomes invalid after the call. The element it pointed to was deleted. The return value of delivers the next valid iterator. By assigning the return value to the previous iterator, you can simply continue working with it.

Reassigning elements: splice

The member function is used to move elements from one list to another list. Such processes can be implemented extremely efficiently with lists because the actual data does not have to be moved, only a few pointers have to be reassigned. Depending on its parameters, the function performs slightly modified operations. In this way, individual elements as well as entire lists can be reassigned.

example

To demonstrate the different variants, two lists are prepared. The list source contains the elements 0, 1, 2, 3 and the list aim the elements 100 and 200. The iterator Item points to element 200 of the list aim. The iterator Source points to 1, the iterator Source end on 3.

Insert list

The function adds to the current list in front of the position Item the elements of the list OrgList a. void splice (iterator Pos, list & source);

The iterator Item must be an iterator of the list being executed on. The call is:

Target.splice (pos, source);

After that the list contains aim the elements 100, 0, 1, 2, 3, 200. The list source is then empty.

Reassemble the single element

This function can also be used to move a single element from one list to the other. void splice (iterator Pos, list & source, iterator QuelleAnf);

With these parameters the function adds to the current list in front of the position Item the item that is at the position Source the list source stands. The element Source from the list source away. The call is:

Ziel.splice (Pos, Quelle, QuellAnf);

After that the list contains aim the elements 100, 1, 200. The list source contains 0, 2, 3.

Reassign part list

In the last variant, consecutive elements of the list source slung around. void splice (iterator Pos, list & source, iterator source start, iterator source end);

In this variant, all elements of the list source of Source to Source end to the position Item slung around. As usual with the iterators, shows here as well Source end as an end delimiter on the position behind the last element that is taken.

Ziel.splice (Pos, Source, SourceAnf, SourceEnd);

After that the list contains aim the elements 100, 1, 2, 200. The list source contains 0, 3.

Merge sorted lists

The element function allows you to sort another sorted list into a sorted list. The target list then contains all elements in sorted order. The inserted list is empty after the call. Target.merge (source);

Container adapter

Container adapters are based on containers to provide special interfaces. For example, a stack can be implemented with the help of a vector. The stack only offers the user a restricted interface. An adapter has no iterators. On the basis of the sequential container vector, deque and list become the container adapters stack, queue and priority_queue Are defined.

Container adapter stack

A stack saves its elements in the order in which they arrive and releases them in the reverse order. So it corresponds to a stack that can only be accessed from above. The container adapter stack offers the following three functions as an interface:
push (obj)
The object is placed on the stack.
Top()
The top object of the stack is supplied as a return value. However, it is not removed from the stack.
pop()
The topmost object is removed from the stack. There is no return value.
In order to read and remove an object from the stack, the functions and must be called one after the other. A small example shows how such a stack is used.

[Stack adapter (stl / stack.cpp)]

#include #include using namespace std; int main () {stack stack; Stack.push (3); Stack.push (2); Stack.push (1); while (! Stack.empty ()) {cout << Stack.top () << endl; Stack.pop (); }}

By default, a deque-based stack is implemented. If you want to see the stack represented as a list, you have to list embed. Finally, when defining the stack, it is specified which container is used as the basis. You need to make the following changes:

#include #include ... stack > stack;

Don't forget the space between the two lower-case characters in front of the word "stack". Otherwise, one of the compilers may mistake the double greater than sign for a redirection operator.

The container adapter queue

Similar to the stack, there is an adapter that works as a FIFO: the queue. A queue has in addition to the functions of the container adapter stack the functions and, each of which returns an item. The function is no longer available for this.
push (obj)
An object is pushed into the back of the buffer.
pop()
removes the first inserted object from the front.
front()
provides a reference to the foremost element.
back ()
supplies a reference to the element last set.

[Queue (stl / queue.cpp)]

#include // # include #include using namespace std; int main () {queue FIFO; // queue > FIFO; FIFO.push (4); FIFO.push (3); FIFO.push (2); FIFO.push (1); while (! FIFO.empty ()) {cout << FIFO.front () << endl; FIFO.pop (); }}

You can use the commented out lines to use the queue on the basis of a list. A deque is used by default.

Container adapter priority_queue

This adapter is different from one queue by the fact that the inserted elements receive a priority. The functions are comparable to those of a stack. The queue is saved as a priority_queue Are defined. The difference can be seen in the internal behavior: the queue checks the elements for their priority with the help of the smaller operator and delivers the element with the highest priority first. In the following example, whole numbers are put into the queue, which are then sorted out again. In a real application, you would of course define a data class that overloads the smaller operator and can thus supply the priorities.

[Priority Queue (stl / pqueue.cpp)]

#include #include using namespace std; int main () {priority_queue FIFO; FIFO.push (4); FIFO.push (7); FIFO.push (5); FIFO.push (1); while (! FIFO.empty ()) {cout << FIFO.top () << endl; FIFO.pop (); }}

The container classes set and multiset

The container set immediately puts the inserted elements down in a sorted order. In one set each element may only appear once. In one multiset elements may appear multiple times. The container set is an associative container. This means that it sorts the elements according to a key value in a binary tree.

Advantages and disadvantages

If you want to store data in a structure according to a sorting criterion and want to access it again quickly, then the container is set the ideal structure. In a list, the unsorted insertion is very efficient, but finding the corresponding position takes too much time and the sorting has to be done afterwards by calling up.

Insert and delete

The operations for inserting,, and deleting,, need on the container set no more iterator, but expect the value to be inserted or deleted. The function returns an iterator that points to the newly inserted element. The following example inserts random numbers into a set. Duplicate numbers are not inserted because it is a set and not a multi-set. Then the number 4 is deleted from the set.

[Insert and delete in set (stl / set.cpp)]

#include #include using namespace std; void show (set & numbers) {set :: iterator iter; for (iter = numbers.begin (); iter! = numbers.end (); ++ iter) {cout << * iter << "-"; } cout << endl; } int main () {set numbers; int new number; srand (0); for (int i = 0; i <10; i ++) {new number = rand ()% 9 + 1; pay.insert (new number); cout << new number << "-"; } cout << endl; show (numbers); pay.erase (4); show (numbers); }

Search

Searching in a binary tree is very efficient. That is why the member function of the container is set also much faster than the general function that is intended for all containers. The function expects the value to be searched for as a parameter and returns an iterator that points to the element. Does the element exist in the container set not, the iterator is identical to the return value of the member function.

Sorting

So that the container set To be able to sort elements in the correct order, the less than symbol must be defined for the type of element. Alternatively, when creating a container set a predicate can be specified for the type that replaces the less than relation. For this purpose, a class is created as a function object that provides the comparison. In the following example, a predicate is created that, instead of a smaller comparison, creates a larger relation. This reverses the order of the set.

[Comparison class (stl / setsort.cpp)]

#include #include using namespace std; class Anders {public: bool operator () (int a, int b) {return a> b; }}; void show (set & numbers) {set :: iterator iter; for (iter = numbers.begin (); iter! = numbers.end (); ++ iter) {cout << * iter << "-"; } cout << endl; } int main () {set numbers; srand (0); for (int i = 0; i <10; i ++) {numbers.insert (rand ()% 9 + 1); } show (numbers); }

The class Different is used as the second template parameter. This sorts the elements in descending order in this case. With the class Different it is a very typical functional object. You can see that the call operator has been defined. Since the return type is, it is a predicate. The function also shows how a container is passed as a parameter to a function.

The container classes map and multimap

The container map accepts two types of elements. The first type is the search key, which is stored in a binary tree like a set. The second type is the actual data element that should be found by the key. When defining a map container, two types are specified: the first for the key, the second for the value. The map overloads the square brackets so that the key is specified in between. The entire expression then designates the data element. In this way, programming can be done very clearly with the map.

[Example for map (stl / map.cpp)]

#include #include #include using namespace std; int main () {map identifier; License plate ["HH"] = "Hanseatic City of Hamburg"; cout << identifier ["HH"] << endl; cout << "size:" << tag.size () << endl; cout << identifier ["HG"] << endl; cout << "size:" << tag.size () << endl; }

If you run the program you will get the following output:

Hanseatic City of Hamburg Size: 1 Size: 2

find ()

Obviously, an element is created for the key HG simply by using it in the square brackets. If you just want to check whether there is such an element at all, you should use the member function: if (Kennzeichen.find ("KI") == Kennzeichen.end ()) {cout << "Not found!" << endl; }

Iterator types

Iterators offer the possibility of accessing elements of a container in a standardized form. Since the various containers are accessed in different ways, each container supplies the appropriate iterator type under the name iterator With.

interface

The iterators thus form the connection for the STL algorithm functions to access the containers. In this way the container can be exchanged without affecting the STL function. However, not all containers are suitable for all types of access. A distinction is made between different types of iterators, depending on the access options they offer. The types of iterators are the RandomAccessIterator, the BidirectionalIterator, the ForwardIterator, the InputIterator and the OutputIterator. Table (tabiter1) shows the operations that are possible with the respective iterator types. [Iterators]
output Input Forward Bidirectional RandomAccess
Read
access,
Write
iteration, , , , , ,
comparison, , , , , , , ,

Container dependency

Behind the guy iteratorthat the container offers is one of the iterators mentioned above. Which iterator the container can offer naturally depends on the access options that the container offers. Table (tabiter2) shows which container offers which iterator.
Container Iterator
vector RandomAccessIterator
deque RandomAccessIterator
string RandomAccessIterator
list BidirectionalIterator

[Containers and Iterators]

Container Iterator
map BidirectionalIterator
multimap BidirectionalIterator
set BidirectionalIterator
multiset BidirectionalIterator

The template class bitset

construction

The template class bitset also belongs to the STL, but is not a container because it does not accept any user types in order to organize them. Rather, it offers a way of managing bit structures. The parameter that the template receives is not a data type, but an integer constant that specifies how many bits the bitset contains.

Bit operations

You can set individual bits with the member function and delete them with. The member function toggles one bit. The position of the required bit is specified as a parameter. If no parameter is specified, the function is applied to all bits of the bitset.

Check

The member function returns a value that indicates whether the bit whose position is transferred as a parameter is set. [Bitset functions]
effect
bool test (size_t pos) returns true if bit is set
bitset set (size_t pos, int var = 1) Sets the bit at position pos
bitset reset (size_t pos, int var = 0) Deletes the bit at position pos
bitset flip (size_t pos) Switches the bit at position pos

Index operator

The bitset can be treated like an array with the help of the index operator. This makes the accesses clearer. The member function supplies the number of bits set in a bit set, the function its size in bits. The function returns when at least one bit of the bit set is set. The function becomes true if none of the bits are set. [Other bitset functions]
function effect
size_t count () Number of bits set in the bit set
size_t size () Number of bits in the bit set
bool any () returns true if either bit is set
bool none () returns true if none of the bits are set
The bitset knows the functions and, in order to convert the complete bitset into an integer or a character string.
[1]
In concrete terms: it needs random access iterators. What these iterators are all about will be clarified in the course of this chapter.