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

This article mainly introduces "the underlying implementation analysis of C++ vector". In daily operation, I believe many people have doubts about the underlying implementation analysis of C++ vector. 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 "the underlying implementation analysis of C++ vector". Next, please follow the editor to study!

Define the initial structure

In C++, vector is also a template, and its underlying implementation uses three pointers, and then use the three pointers to add and subtract each other to achieve storage effect.

Vector is similar to string in that it is essentially a sequence table.

Template class vector {public: ~ vector () {delete _ start; _ start = _ finish = _ end_of_storage = nullptr;} private: T* _ start; / / sequence table header T* _ finish; / / sequence table effective length position T* _ end_of_storage; / / sequence table end}; declare the constructor

As explained in the previous chapter, there are many constructors, which are just for simple implementation, so the blogger implements the simplest constructor, that is, no-parameter construction.

Vector (): _ start (nullptr), _ finish (nullptr), _ end_of_storage (nullptr) {} capacity related operations to get valid data size size ()

Want to get size, how to achieve it? When we define the initial structure, we already know that the underlying structure uses three pointers, so size equals _ finish-_ start.

Size_t size () const / / add const to ensure that const objects can also use {return _ finish-_ start;} to obtain data capacity capacity ()

By the same token, capacity should be _ end_of_storage-_ start

Size_t capacity () / / adding const ensures that const objects can also use {return _ end_of_storage-_ start;} to increase capacity reserve ()

We will implement an interface later, called push_back (), which is used to put data into vector, but what if there is not enough space? This requires our compatibilization function reserve.

Its parameter is unsigned integer n, which means to open n spaces.

Void reserve (size_t n) {if (n > capacity ()) {T * tmp = new T [n]; / / first open up a space size_t sz = size () / / keep the original valid data size, and be sure to save if (_ start) / / be sure to judge this, because at the beginning _ start is empty, then only the open space {memcpy (tmp, _ start, sizeof (T) * n) is needed; / / copy the original data into the new space delete _ start / / release the original space} _ start = tmp; / / transfer space _ finish = _ start + sz; / / update _ finish _ end_of_storage = _ start + n; / / update _ end_of_storage}} reset size resize ()

You must be used to this by now, right? He has two parameters, which will be assigned according to the situation whether it is greater than size ().

Void resize (size_t NJ Const T & val = T ()) {if (n > capacity ()) reserve (n); for (size_t I = size (); i0); _ finish--;} insert insert () somewhere

By the same token, it is common to check whether the capacity is sufficient first. If not, you need to be aware of the iterator failure, then move the location and all subsequent data, and finally insert the data.

The official document defines the location where the return value is the newly inserted data

Iterator insert (iterator pos,const T & val) {assert (pos > = _ start & & pos pos) {* cur = * (cur-1); cur--;} * pos = val; _ finish++; return pos;} delete erase ()

The operation of this interface usually starts from the position after pos, and all data is moved one unit in front of it. But before moving, you need to check to see if the data still exists.

The official document defines its return value as the next location where the data is deleted

Iterator erase (iterator pos) {assert (pos > = _ start & & pos)

< _finish); iterator it = pos + 1; while (it != _finish) { *(it-1) = *it; ++it; } --_finish; return pos;}拷贝构造vector(const vector& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr){ reserve(v.capacity()); for (const auto& e : v) { push_back(e); }}[]访问操作 上面我们实现了迭代器,但是vector还支持[]索引取值,博主这里便实现两个[]重载吧 T& operator[](size_t i){ assert(i < size()); return _start[i];}const T& operator[](size_t i) const{ assert(i < size()); return _start[i];}=赋值操作vector& operator=(vector v) //注意哦~,我这里故意写的传值参数,而不是引用,是为了下面进行交换{ swap(*this,v); return *this;}特别注意!!! 在实现了上面的一系列操作以后,有没有觉得我们已经大功告成了?其实这里还隐藏着一个小小bug!.为什么呢?看下面' int main(){ //我们假设最开始创建的vector的容量是4 vector vc; vc.push_back("123"); //创建vc,并给其赋值 vc.push_back("234"); vc.push_back("345"); vc.push_back("456"); vc.push_back("567"); return 0;} 初一看,好像并没有什么错误哎?但是一运行就会发现,当插入第5个元素的时候,就报错了.这是什么原因呢? 调试发现,问题出在了reserve上面,因为push_back之前,会检查容量,那么我们现在重新瞅瞅 reserve存在什么问题呢? void reserve(size_t n){ if (n >

Capacity () {T * tmp = new T [n]; / / first open up a space size_t sz = size () / / keep the original valid data size, and be sure to save if (_ start) / / be sure to judge this, because at the beginning _ start is empty, then only the open space {memcpy (tmp, _ start, sizeof (T) * n) is needed; / / copy the original data into the new space delete _ start / / release the original space} _ start = tmp; / / transfer space _ finish = _ start + sz; / / update _ finish _ end_of_storage = _ start + n; / / update _ end_of_storage}}

Did you find anything wrong?

Yes, there is a problem with memcpy. When there is not enough capacity, reserve will increase the capacity and then copy the content value of the original space to the new space.

But the content of the original space only has three pointers. After copying it, the new space and the source space both point to the same space, and we will release the original space.

So, when we continue to insert the fifth element, an error is reported, because the space no longer exists!!, has been released.

Then how to solve it? Here we can only use a loop to assign the string value to the new space.

Void reserve (size_t n) {if (n > capacity ()) {size_t sz = size (); T * tmp = new T [n]; if (_ start) {for (size_t I = 0; I < sz; + + I) {tmp [I] = _ start [I] } delete [] _ start;} _ start = tmp; _ finish = _ start + sz; _ endofstorage = _ start + n;} at this point, the study on "the underlying implementation analysis of C++ vector" is over. I hope I can 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.