Shulou(Shulou.com)06/02 Report--

This article mainly introduces "introduction to the underlying data structure of C++ container". In daily operation, I believe many people have doubts about the introduction of the underlying data structure of C++ container. The editor consulted all kinds of materials and sorted out simple and easy-to-use methods of operation. I hope it will be helpful to answer the doubts about "introduction to the underlying data structure of C++ container". Next, please follow the editor to study!

Built-in array: int arr [10] [10]; memset (arr,0,10*10*sizeof (int)); / / initialize int tmp [10] [10]; memcpy (arr, tmp, 10*10*sizeof (int)); / / copy

Void * memcpy (void * destin, void * source, unsigned n); / / Source * destination memory coverage problem

The memcpy function is used to copy the resource memory (the area of memory pointed to by src) to the target memory (the area of memory pointed to by dest); how many copies? There is a size variable that controls the number of bytes copied

Sequence containers: array, vector, deque, list, forward_list

Array (array container): an array-based, fixed-length sequence with N T-type objects.

Vector (Vector Container): a variable-length sequence based on an array that stores T-type objects, reserves a larger piece of contiguous space, and allocates a larger copy when it is exceeded.

Deque (double-ended queue container): a variable-length sequence, used to store T-type objects, can efficiently add or delete elements at both ends of the sequence, and consists of a segment of quantitative continuous space. Subscript access must be a secondary pointer dereference, compared with vector subscript access only once. Deque with only one element must allocate its entire internal array (for example, 8 times the size of the object on 64-bit libstdc++) The 64-bit libc++ is 16 times the size of the object or the larger of 4096 bytes.

List (linked list container): a variable-length sequence of T-type objects that organizes elements in a two-way linked list, where elements can be efficiently added or deleted anywhere in the sequence. Accessing any element in the container is slower than the first three containers, because list must start with the first or last element and move along the linked list until you reach the desired element.

Forward list (forward linked list container): a variable-length sequence of T-type objects that organizes elements in the form of a single linked list. It is a faster and more memory-saving container than a linked list container, but its internal elements can only be accessed from the first element.

String: a container similar to vector, but dedicated to saving characters. Random access. Quick. Insert / delete at the tail is fast.

The function member max_size () of all sequence containers returns the maximum number of elements it can store. This is usually a large value, usually 2 ^ 32-1.

Stack

The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

Deque is used by default instead of vector as the underlying container

How to choose the underlying data structures of set, map, multimap, unordered_set, unordered_map, unordered_multimap, and several map containers?

Set, map and multimap are based on the red-black tree. They are non-strictly balanced binary search trees with orderly elements, high insertion and deletion efficiency and high space occupancy.

Unordered_set, unordered_map and unordered_multimap are based on hash table, the elements are out of order, and the search efficiency is high.

The problem of memory share translates into the red-black tree VS hash table, or the unorder_map takes up more memory, and the establishment of the hash table takes more time.

Map empty_map1; map1.swap (empty_map1); map1.clear (); or StrategyMap () .swap (_ stg_flows)

Map.clear () just empties map, but memory is not freed. If you want to free memory, you not only need to clear (), but also swap with an empty map to free memory.

Note that if the element in map is not a basic type, memory should also be released, such as pointers, vector should pay special attention, otherwise map takes up too much memory and will cause the program to crash.

Vector

Array: a fixed-length array that uses a stack (static memory allocation), so it is as efficient as an array.

Data filling is realized by using fill method.

Use the size method to get the size of the array.

Although the at (I) method implements reads and writes with out-of-bounds checking.

The comparison results of writing speed: the built-in array is the fastest, the vector container is the second, and the array container is the slowest.

Copy speed: https://blog.csdn.net/qq_35976351/article/details/82940121

Copy: / * off optimization: array=466ms vector=7923ms memcpy=198ms * / / *-O3 optimization, maximum speed: array=0ms vector=453ms memcpy=0ms * /

Iterator iterator

In STL, use an iterator (built-in type iterator) to give the location of the data in the table

Forward iterator: containerType::iterator itr

Constant forward iterator (immutable): containerType::const_iterator itr

Reverse iterator: containerType::reverse_iterator itr

Constant reverse iterator: containerType::const_reverse_iterator itr

Common container methods that require the use of iterators:

Iterator insert (iterator pos, const Object & x): adds x to the table before the location pointed to by the iterator pos. It is a constant time operation for 1ist, but not for vector. The return value is an iterator that points to the location of the insert

Iterator erase (iterator pos): deletes the object at the location given by the iterator. It is a constant time operation for 1ist, not for vector. The return value is the location of the next element of the element that pos points to before the call. This operation invalidates pos. Pos is no longer useful because the container variable it points to has been deleted

Iterator erase (iterator start, iterator end): removes all elements from location start to location end (but not including end)

At this point, the study of "introduction to the underlying data structure of C++ container" is over. I hope to be able to solve your doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.