Failure of vector insertion element iterator in STL

Catalog

One 、capaticy() When the capacity is insufficient , Tail-insert element

Conclusion 1 ：

Two 、capaticy() When the capacity is sufficient , Tail-insert element

Conclusion two ：

3、 ... and 、capacity() When the capacity is sufficient , Insert the element in the middle

Conclusion three ：

---

STL in vector Memory is managed by three pointers ：_M_start,_M_finish,_M_end_of_storage, All about address , These three pointers are required for operations such as capacity size .

STL The use of these three pointers in the source code is as follows ：

iterator begin() _GLIBCXX_NOEXCEPT
    { return iterator(this->_M_impl._M_start); }
iterator end() _GLIBCXX_NOEXCEPT
    { return iterator(this->_M_impl._M_finish); }
reverse_iterator  rbegin() noexcept
    { return reverse_iterator(end()); }
reverse_iterator rend() noexcept
    { return reverse_iterator(begin()); }
size_type size() const _GLIBCXX_NOEXCEPT
    { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }
size_type capacity() const _GLIBCXX_NOEXCEPT
    { return size_type(this->_M_impl._M_end_of_storage - this->_M_impl._M_start); }
bool empty() const _GLIBCXX_NOEXCEPT
    { return begin() == end(); }

vector In addition to supporting ordinary iterators , Reverse iterators are also supported , The relationship between the iterator and the three pointers is shown in the following figure ：

 

Take the ordinary forward iterator as an example ,vector Iterators have many things to pay attention to .

One 、capaticy() When the capacity is insufficient , Tail-insert element

The code is as follows ：

#include <iostream>
#include <vector>
using namespace std;
void Print(vector<int>& vec) {
    cout << "size: " << vec.size() << endl;
    cout << "capacity: " << vec.capacity() << endl;
    auto it = vec.begin();
    cout << "iterator: ";
    while(it != vec.end()) {
        cout << *it << "(" << &(*it) << ")"
         << "\t";
        ++it;
    }
    cout << *it << "("  << &(*it)  << ")" << endl;
}
int main() {
    vector<int> vec{1,2};
    Print(vec);
    vec.push_back(3); 
    Print(vec);
    return 0;
}

The print before and after inserting the element is as follows ：

Conclusion 1 ：

capacity() When it's not enough , Capacity expansion will be carried out , All previous iterators will fail .

Two 、capaticy() When the capacity is sufficient , Tail-insert element

#include <iostream>
#include <vector>
using namespace std;
void Print(vector<int>& vec) {
    cout << "size: " << vec.size() << endl;
    cout << "capacity: " << vec.capacity() << endl;
    auto it = vec.begin();
    cout << "iterator: ";
    while(it != vec.end()) {
        cout << *it << "(" << &(*it) << ")"
         << "\t";
        ++it;
    }
    cout << *it << "("  << &(*it)  << ")" << endl;
}
int main() {
    vector<int> vec{1,2};
    Print(vec);
    vec.push_back(3); 
    Print(vec);
    vec.push_back(4);
    Print(vec);
    return 0;
}

The print before and after inserting the element is as follows ：

Conclusion two ：

capacity() Insert elements at the tail when the capacity is sufficient , Before vector None of the iterators have failed .

3、 ... and 、capacity() When the capacity is sufficient , Insert the element in the middle

  The code is as follows ：

#include <iostream>
#include <vector>
using namespace std;
void Print(vector<int>& vec) {
    cout << "size: " << vec.size() << endl;
    cout << "capacity: " << vec.capacity() << endl;
    auto it = vec.begin();
    cout << "iterator: ";
    while(it != vec.end()) {
        cout << *it << "(" << &(*it) << ")"
         << "\t";
        ++it;
    }
    cout << *it << "("  << &(*it)  << ")" << endl;
}
int main() {
    vector<int> vec{1,2};
    Print(vec);
    vec.push_back(3); 
    Print(vec);
    auto it1 = vec.begin();
    ++it1;
    vec.insert(it1, 4);
    Print(vec);
    return 0;
}

The information printed before and after insertion is as follows ：

Conclusion three ：

 capacity() When the capacity is sufficient , Insert the element in the middle , Iterators before the insertion position are not affected , Later iterators will fail .