Shulou(Shulou.com)05/31 Report--

This article mainly explains "C++ 's STL serial container and adapter how to use", interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn how to use C++ 's STL serial containers and adapters.

Container Overview

The following containers or container adapters are provided in the C++ standard:

Sequential container adapter associative container unordered associative container arraystacksetunordered_setvectorqueuemapunordered_maplistpriority_queuemultisetunordered_multisetdeque

Multimapunordered_multimapforward_list

Sequential container

Array

Array is a static contiguous space, once configured, the size cannot be changed.

It's just an array, which is very similar to vector except for the lack of space flexibility. Use is also relatively small, generally use vector, here will not say much.

Vector

The data arrangement and operation of vector is very similar to that of array. The only difference between the two is the flexibility in the use of space.

Array is a static space, once the configuration cannot be changed

Vector is a dynamic space, and as elements are added, the internal mechanism expands the space itself to accommodate the new elements.

Vector maintains a continuous linear space, whose pointers are ordinary pointers.

Vector::iterator iter

So iter is actually the int* type.

Between the two iterators start and finish is the space that has been used in the continuous space, and the end_of_storage points to the tail end of the whole continuous space.

In order to reduce the cost of frequent space configuration, the actual configuration size of vector will be larger than that of customers, in case of possible expansion in the future. This is the concept of capacity.

[start,finish] is size ()

[start, end_of_storage] is capacity ()

[finish, end_of_storage] is the spare space.

Once size () = = capacity (), it is fully loaded. The next time there are new elements, the whole vector will have to find another place. The process of "finding another place" will go through a series of actions of "reconfiguring the large space, moving the elements, and releasing the original space", which is a huge project.

The so-called dynamic increase in size is not to follow the new space after the original space (because there is no guarantee that there is space available for configuration after the original space), but to configure a larger space with twice the size of the original space, and then copy the original content over, and then begin to construct new elements behind the original content and release the original space.

Therefore, as soon as any operation on vector causes space reconfiguration, all iterators pointing to the original vector will fail, which is a common mistake, so be careful.

List

List is a circular two-way linked list. Its advantage is that every time you insert or delete an element, you configure or release an element space. Compared with vector, list is more accurate in the use of space and will never be wasted. And list is always a constant time for insertion or removal of elements anywhere.

The vector and list scenarios are related to the following:

Number of elements

Construction complexity of the element (with or without non-trival copy constructor, non-trival copy assignment operator)

Characteristics of element access behavior

The node structure of list is as follows:

Template struct _ _ list_node {typedef void* void_pointer; void_pointer prev; void_pointer next; T data;}

Because list's memory space is not guaranteed to be contiguous, its iterators are no longer ordinary pointers. List iterators must be able to point to list nodes and perform correct increments, decrements, values, member access, and so on.

Most list operations do not invalidate the iterator, and even if it is a delete operation, only the iterator that points to the deleted element is disabled.

Because list is a circular two-way linked list, it only needs a pointer to traverse the entire linked list.

For insert operations, the new node will be located in front of the node referred to by the Sentinel iterator (indicating the insertion point), which is the standard STL specification for insert operations.

Deque

Vector is a continuous linear space with one-way opening, while deque is a kind of linear continuous space with two-way opening. The so-called two-way opening, that is, elements can be inserted and deleted at both ends.

Deque is actually composed of piecewise continuous spaces dynamically. But these segmented contiguous spaces are indeed a whole continuous space in the eyes of users, which is actually an illusion made by deque. This illusion is maintained by map, the central controller of deque (note, not the map container in STL).

This map can be understood as a mapping, which is a pointer to a small piece of contiguous memory space, and each element in this space is a pointer, and each pointer points to a segment of deque's piecewise contiguous space. The default is 512 bytes per segment.

Forward_list

Forward_list is an one-way linked list.

As mentioned earlier, for insert operations, the new node will be located in front of the node referred to by the Sentinel iterator (indicating the insertion point), which is the STL standard specification for insert operations.

But forward_list as an one-way linked list, it has no convenient way to go back to the previous location, it can only start from scratch, so in addition to the area near the starting point of forward_list, insert () or erase () is very slow in other locations. For this, forward_list specially provides insert_after () and erase_after ().

Also for efficiency reasons, it does not provide push_back (), only push_front ().

Adapter (adapter)

Stack

Stack is the data structure of first in and then out (FILO). It has only one exit, and there is no other way to get the elements of stack except the top element. That is, stack does not allow ergodic behavior, so naturally there is no iterator.

In fact, stack in STL is not container, but adapter, because the bottom layer defaults to deque, which closes the head end of deque to form a stack.

A person who has the nature of "modifying the interface of something to form another style" is called adapter.

In addition to the fact that deque,list is also open in both directions, list can also serve as the underlying structure of stack.

Queue

Queue is a first-in, first-out (FIFO) data structure. It has two entrances and exits, but both are restricted, with no entry and exit at the tail end and no exit at the head end. Apart from tail-in and head-out, there is no other way to access other elements of queue, that is, queue does not allow traversal, and naturally there is no iterator.

Queue is also a kind of adapter, which, like stack, defaults to deque as the underlying structure, and list can also do its underlying structure.

The head-end entrance and tail-end exit of the deque become a queue.

Priority_queue

Priority_queue is a queue with the concept of weight.

The so-called concept of owning weights can be understood as orderly, in which the elements are not arranged in the order in which they are added, but according to the weights of the elements, and those with the highest weights are at the forefront.

By default, priority_queue is done with a large root heap (max-heap), which is a complete binary tree represented as vector.

Big root heap: max-heap, complete binary tree in which the parent node value is greater than or equal to the child node value

Small root heap: min-heap, a complete binary tree in which the parent node value is less than or equal to the child node value.

Therefore, priority_queue is implemented with vector as the underlying structure, supplemented by heap processing rules, so it is also an adapter.

Priority_queue also does not allow traversal, and naturally there is no iterator.

At this point, I believe you have a deeper understanding of "how to use C++ 's STL serial containers and adapters". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.