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

How to use STL source code to analyze vector container, in view of this problem, this article introduces the corresponding analysis and solution in detail, hoping to help more partners who want to solve this problem to find a more simple and easy way.

Vector is our most commonly used container in STL, and we are well aware of its various operations. However, we always have a false feeling when using vector, because we don't know how it is implemented inside the interface. In our eyes, it is like a black box, both dangerous and charming.

In order to overcome this concern, I will take you to the bottom of vector, thoroughly understand the internal implementation details of the vector interface, and open the black box. In this way, we will not panic when using vector, and we will really know it in our hearts.

Overview of the underlying principles of vector

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

When vector dynamically increases the size, it is not to continue the new space after the original space (because there is no guarantee that there is still space available for configuration after the original space), but to configure a larger space at twice the original size, and then copy the content, and then begin to construct new elements after the original content, and release the original space.

Key source code understanding

1. Iterator internal type

Let's take a look at how iterators are defined in STL source code.

Template

Class vector {

Public:

/ / nested type definition of vector

Typedef T value_type

The typedef value_type* iterator; / / iterator itself is an object of a template class.

Typedef value_type& reference

...

}

As shown in the code above, the iterator iterator itself is a class type, and the operator * is overloaded. The iterator iterator points to the internal element of vector, which can be understood as iterator bundled with the internal element of vector, which behaves like a pointer, but cannot be used as a pointer.

Soul torture 1: what's the difference between an iterator and a pointer?

We can understand that an iterator is essentially an object generated by a template class, and its operators * and-> are implemented by operator overloading. This object points to the internal element of the vector (the element is also the object of the iterator), so when the element pointed to by the iterator is deleted or moved, the iterator is unlinked from the element, and the iterator is useless, that is, the iterator is invalid. Iterators behave like pointers, but with differences.

In contrast to pointers, pointers are linked to memory. If the element stored in the memory address that the pointer points to is deleted or moved, the pointer does not fail, it still points to that address.

Based on the above definition, an iterator can declare:

Vector::iterator ivite

Vector::iterator svite

After looking at the source code above, we can see why the iterator declares this way.

Data structure of 2.vector

Vector uses two iterators start and finish to represent the extent of the used space and points to the end of the allocated space with the iterator end_of_storage. The code is as follows:

Template

Class vector {

...

Protected:

Iterator start; / / indicates the header of the currently used space

Iterator finish; / / represents the end of the currently used space, that is, the next element of the last element

Iterator end_of_storage; / / represents the tail of the entire space currently allocated

...

}

Using the above three iterators, we can encapsulate various member functions of vector.

Template

Class vector {

...

Public:

Iterator begin () {return start;}

Iterator end () {return finish;}

Size_type size () const {return size_type (end ()-begin ());}

Bool empty () const {return begin () = = end ();}

Reference front () {return * begin ();}

Reference back () {return * (end ()-1);}

Reference operator [] (size_type n) {return * (begin () + n);} / / operator [] overloaded and can use iterators to access elements

}

Some of the above basic operations are clear at a glance, so I won't talk about them one by one here. There are only two points mentioned here. First, you can see from the above code that operator overloads the operator [], which enables the iterator to traverse the vector like an array index.

Second, the iterator finish points to the next element of the last element of vector, as does the encapsulated end () function. This is what we often call the front-close and back-open feature of vector.

Soul torture 2: why is the container designed to be closed before and after opening?

This is done to reduce judgment conditions when traversing container elements. Because the core of STL is generic programming, the interface designed is universal. Because only some containers support > and

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.