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

This article shares with you the content of an example analysis of the underlying implementation mechanism of vector in the C language. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

First, an analysis of the underlying implementation mechanism of vector

By analyzing the source code of the vector container, it is not difficult to find that it is represented by three iterators (which can be understood as pointers):

Where statrt points to the starting byte position of the vector container object

Finish points to the last byte of the current last element

The end_of points to the last byte of the memory space occupied by the entire vector container.

The figure shows where the above three iterators point to respectively.

The figure shows where the above two iterators point respectively.

On this basis, the pairwise combination of three iterators can also express different meanings, such as:

Start and finish can be used to represent the memory space currently used in the vector container

Finish and end_of can be used to represent the current free memory space of the vector container

Start and end_of can be used to represent the capacity of the vector container.

Second, the simulation of the core framework interface of vector. Iterator implementation of 1.vector.

Typedef T* Iteratot

Typedef T* const_Iteratot

Iteratot cend () const {return final_end;} Iteratot cbegin () const {return start;} Iteratot end () {return final_end } Iteratot begin () {return start;}

Vector's iterator is a native pointer, and his iterator, like String, operates pointers to traverse data:

Begin () returns the starting byte position of the vector container object

End () returns the last byte of the current last element

2.reserve () expand void reserve (size_t n) {if (n > capacity ()) {T * temp = new T [n]; / / copy the data from statrt to temp size_t size1 = size () Memcpy (temp, start, sizeof (T*) * size ()); start = temp; final_end = start + size1; finally = start + n;}}

When the vector is equal in size and capacity (size==capacity), that is, it is fully loaded, if you add elements to it, then the vector needs to be expanded. The expansion of vector container needs to go through the following three steps:

Completely abandon the existing memory space and reapply for more memory space

Move the data from the old memory space to the new memory space in the original order

Finally, the old memory space is freed.

This explains why pointers, references, and iterators associated with vector containers may fail after expansion.

It can be seen that the expansion of vector is very time-consuming. In order to reduce the cost of re-allocating memory space, vector will apply for more memory space than users need for each expansion (this is the origin of vector capacity, that is, capacity > = size) for later use.

When the vector container is expanded, the amount of more memory requested by different compilers is different. Take VS, for example, which expands 50% of the capacity of existing containers.

Use memcpy to copy questions

Reserve expansion is to open up a new space and use memcpy to copy the data from the old space to the new open space.

Suppose a copy is made using memcpy in the reserve interface in the simulated implementation of vector. What happens to the following code?

Int main () {bite::vector v.pushbacks ("1111"); v.push_back ("2222"); v.push_back ("3333"); return 0;}

Problem analysis:

Memcpy is a binary copy of memory, copying the contents of one section of memory space intact to another.

If you copy a custom type element, memcpy is efficient and error-free, but if you copy a custom type element and resource management is involved in the custom type element, an error occurs because the copy of the memcpy is actually a shallow copy.

Conclusion: if resource management is involved in objects, memcpy should not be used for copying between objects, because memcpy is a shallow copy, otherwise it may cause memory leaks or even program crashes.

3. Delete (push_back (), pop_back ()) void push_back (const T&var) {if (final_end = = finally) {size_t newcode = capacity () = 0? 4: capacity () * 2; reserve (newcode) } * final_end = var; + + final_end; void pop_back () {final_end--;}

In general, the insertion problem is to determine whether the space contains idle space, if not, it is necessary to open up the space. We final_end==finally to determine whether there is free space. If the container contains no space, open 4 bytes of space first, and then open the 2capacoity () space when it is full. Just insert data in the final_ end department. Operate on final_end.

4. Analysis on the failure of iterator when insert () is inserted Iteratot insert (Iteratot iterator,const T&var) {assert (iterator = start); size_t pos = iterator-start If (final_end = = finally) {size_t newcode = capacity () = = 0.4: capacity () * 2; reserve (newcode) } / / insert operation auto it = final_end; while (it > = start+pos) {* (it+1) = * it; it-- } * iterator = var; final_end++; return iterator;}

Suppose this is a section of vector space to insert data into pos, but it just happens that final_end and final are in the same location. The container is full, and you need to expand the container. First of all, the size of the space opened up and this space.

Then copy the old spatial data to the new space to release the old space.

Due to the release of the old space, the memory pointed to by pos is missing. The pos pointer becomes the wild pointer.

How to solve this problem is to save the pointer between the old space solutions, and then let it point back to the original location of the new space.

The insert () function returns the location iterator, which provides a way for the iterator to fail, which is to reassign the value. Let the pointer point back to the location where it should be pointed.

5. Analysis of iterator failure when deleting erase () data Iteratot erase (Iteratot iterator) {assert (iterator = start); auto it = iterator; while (it)

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.