preface
C + + introduces the idea of object-oriented. Compared with C language, a class can better manage and operate some data structures.
In C language, we use fixed length array and dynamic array from malloc to maintain a continuous set of data of the same type
In C + +, based on the idea of object-oriented, the class used to manage spatially continuous data sets of the same type came into being. In essence, the vector class is a sequence container of encapsulated variable size arrays
catalogue
-
2. Common interface and Simulation Implementation of vector
2.1 common constructions of vector class objects
2.2 capacity operation of vector class object
2.3 vector class object obtains the interface between element and iterator
2.4 modifying element interface of vector class object
1. Introduction to vector
When we learn STL, documents are our sharp weapon. Learning to check documents will get twice the result with half the effort. Here are two C + + document websites:- Official website: www.cppreference.com
- Common websites (updated to C++11): www.cplusplus.com
Document introduction of vector:
- vector is a sequence container that represents a variable size array.
- Like arrays, vectors use continuous storage space to store elements. This means that the elements of vector can be accessed by subscript, which is as efficient as array. But unlike an array, its size can be changed dynamically, and its size will be automatically processed by the container.
- Essentially, vector uses dynamically allocated arrays to store its elements. When new elements are inserted, the array needs to be resized to increase storage space. This is done by allocating a new array and then moving all the elements to this array. In terms of time, this is a relatively expensive task, because the vector does not reallocate the size every time a new element is added to the container.
- Vector space allocation strategy: vector will allocate some additional space to accommodate possible growth, because the storage space is larger than the actual storage space. Different libraries use different strategies to balance the use and reallocation of space. But in any case, the redistribution should be logarithmically increasing interval size, so that when inserting an element at the end, it is completed in constant time complexity.
- Therefore, vector takes up more storage space. In order to obtain the ability to manage storage space and grow dynamically in an effective way.
- Compared with other dynamic sequence containers (deques, lists and forward_lists), vector is more efficient when accessing elements, and it is relatively efficient to add and delete elements at the end. For other deletion and insertion operations that are not at the end, the efficiency is lower.
STL as a model of generic programming, our vector class is naturally a class template
template <class T>
class vector{
//......
};
The template parameter T is obviously the type of the element we want to insert into this dynamic array. It can be built-in type data such as int and char, or user-defined type data such as string and vector
vector<int> v1; vector<char> v2; vector<vector<int>> v3; vector<string> v4;
Let's take another look at the member variables of the vector class. We know that string uses:
size_t _size; ------>Number of valid characters size_t _capacity; ------>Total space size T* _str; ------>String pointer
To maintain the dynamic space and string properties
Of course, vector can completely apply the above three variables. However, we can achieve the same purpose by using three pointers to maintain vector this time:
T* _start; ------>Point to data block header T* _finish; ------>Point to the tail of valid data (i.e. the address of the next position of the last valid element) T* _endOfStorage; ------>Point to the end of the storage space
So by analogy:
_size == _finish - _start _capacity == _endOfStorage - _start _str = _start
2. Common interface and Simulation Implementation of vector
2.1 common constructions of string class objects
| Function name | function |
|---|---|
| vector() | Nonparametric structure |
| vector(int n, const T& x = T()) | Construct and initialize n x (the default value of X is 0) |
| template <class InputInerator> vector(InputInerator first, InputInerator last) | Initializing constructs using iterators |
| vector(const vector&v) | copy constructor |
| ~vector() | Destructor |
| operator= | Assignment overload: assign a vector object to another vector object |
Use of multiple constructors:
void Teststring()
{
std::vector<int> first; // Nonparametric structure
std::vector<int> second (4,100); //Construct and initialize 4 100
std::vector<int> third (second.begin(),second.end()); // Using iterator interval construction of second
std::vector<int> fourth (third); // copy construction
}
It is worth mentioning that since the iterator of vector is the pointer of T, the pointer is the natural iterator of vector, so we can use the front and back pointers of the array as the left and right intervals of the iterator to initialize vector
int arr[] = {1,2,3,4,5,56,1};
vector<int> a(arr,arr + 2);
Analog implementation of interface:
- Constructor
//non-parameter constructor
basic_string(const T* s = "")
:_size(strlen(s))
,_capacity(strlen(s))
{
_str = new T[_size + 1];
strcpy(_str, s);
}
//Construct and initialize n x
vector(int n, const T& x = T())
:_start(new T[n])
, _finish(_start + n)
, _endOfStorage(_start + n)
{
for (size_t i = 0; i < n; i++) {
_start[i] = x;
}
}
//Using iterator interval construction
template <class InputInerator>
vector(InputInerator first, InputInerator last)
: _start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
while (first != last) {
push_back(*first);
first++;
}
}
- copy construction
vector(const vector& v)
:_start(nullptr)
, _finish(nullptr)
, _endOfStorage(nullptr)
{
vector tmp(v.cbegin(), v.cend());
swap(tmp);
}
- Destructor
//Destructor
~vector() {
delete[] _start;
_start = nullptr;
_finish = nullptr;
_endOfStorage = nullptr;
}
- Assignment overload
//Assignment overload
vector& operator=(vector v) {
swap(v);
return *this;
}
2.2 capacity operation of vector class object
| Interface name | Interface function |
|---|---|
| size() | Returns the number of elements in the array |
| capacity() | Returns the amount of space currently allocated to the array |
| empty() | Determine whether the array is empty |
| reserve(n) | Reset the size of the space allocated to the array and reserve space for the array |
| resize(n, x) | Reset the array elements, change the number of array elements to n, and fill the extra space with x |
be careful:
- For the increase of array capacity, the capacity under vs is increased by 1.5 times, and that of g + + is increased by 2 times. Vs is the PJ version STL, and g + + is the SGI version STL.
- Reserve is only responsible for opening up space. If you know how much space you need, reserve can alleviate the cost defect of vector capacity expansion.
- resize initializes while opening space, affecting size.
Analog implementation of interface:
- size()
//size() interface
size_t size() const {
return _finish - _start;
}
- capacity()
//capacity() interface
size_t capacity() const {
return _endOfStorage - _start;
}
- empty()
// Air judgment
bool empty() {
return size() == 0;
}
- reserve(n)
void reserve(size_t n) {
size_t sz = size();
T* tmp = new T[n];
memcpy(tmp, _start, size()*sizeof(T));
delete[] _start;
_start = tmp;
_finish = _start + sz;
_endOfStorage = _start + n;
}
- resize(n, x)
void resize(size_t n, const T& x = T()) {
if (n <= size()) {
_finish = _start + n;
}
else {
if (n > capacity()) {
reserve(n);
}
for (size_t i = size(); i < n; i++) {
_start[i] = x;
_finish++;
}
}
}
2.3 vector class object obtains the interface between element and iterator
| Interface name | Interface function |
|---|---|
| operator[ ] | Position of pos element returned |
| begin() | Returns the iterator of the first valid element |
| end() | Returns the iterator at the next position of the last element |
Analog implementation of interface:
- operator[]
//Overload []
T& operator[](size_t pos) {
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const {
assert(pos < size());
return _start[pos];
}
- begin() and end()
typedef T* iterator;
typedef const T* const_iterator;
iterator begin() {
return _start;
}
iterator end() {
return _finish;
}
const_iterator cbegin() const {
return _start;
}
const_iterator cend() const {
return _finish;
}
2.4 modifying element interface of string class object
| Interface name | Interface function |
|---|---|
| iterator insert(iterator pos, const T& x | Insert an element at the pos address |
| push_back() | Insert 1 element at the end |
| erase() | Delete element |
| pop_back() | Delete an element at the end |
| clear() | Clear all elements and set size to 0 |
| swap() | Swap two class objects |
Analog implementation of interface:
- insert()
//Insert element
iterator insert(iterator pos, const T& x) {
assert(pos >= _start && pos <= _finish);
if (_finish == _endOfStorage) {
size_t len = pos - _start;
size_t new_capacity = (_start == _finish) ? 4 : 2 * (_endOfStorage - _start);
reserve(new_capacity);
pos = _start + len;
}
for (iterator i = _finish; i >= pos + 1; i--) {
*i = *(i - 1);
}
*pos = x;
_finish++;
return pos;
}
- push_back()
//push_ Insert an element at the end of back
void push_back(const T& x) {
insert(_finish, x);
}
- erase()
iterator erase(iterator pos) {
assert(!empty());
for (vector::iterator i = pos; i < end() - 1; i++) {
*i = *(i + 1);
}
_finish--;
return pos;
}
- pop_back()
void pop_back() {
erase(end());
}
- clear()
void clear() {
erase(begin(), end());
}
- swap()
void swap(vector& v2) {
::swap(_start, v2._start);
::swap(_finish, v2._finish);
::swap(_endOfStorage, v2._endOfStorage);
}
3. How to get familiar with the interface - brush questions
Brushing questions must be the best way for beginners to master STL. Replace learning with questions and get twice the result with half the effort. Here are some vector exercisesNiuke.com:
- Numbers that appear more than half in the array (3 approaches)
- Maximum sum of continuous subarrays (dp dynamic programming)
leetcode:
- A number that appears only once
- Yanghui triangle
- Delete duplicates of ordered array
- The number II that appears only once
- Number III that appears only once
- Combination of phone numbers (depth first search)
4. Iterator failure of vector
The main function of iterator is to make the algorithm do not care about the underlying data structure. Its underlying layer is actually a pointer or encapsulates the pointer. For example, the iterator of vector is the original ecological pointer T*Therefore, the failure of the iterator is actually the destruction of the space pointed to by the corresponding pointer at the bottom of the iterator and the use of a space that has been released. The consequence is that if you continue to use the failed iterator, the program may crash
Iterators fail in two ways:
- Illegal access to freed memory
- The meaning of iterators has changed
For vector, the operations that may cause its iterator to fail are:
- The operation that will cause the change of its underlying space may be the failure of the iterator, such as resize, reserve, insert, assign and push_back et al
#include <iostream>
using namespace std;
#include <vector>
int main()
{
vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
// Increase the number of effective elements to 100, fill the extra positions with 8, and the bottom layer will expand during the operation
// v.resize(100, 8);
// The function of reserve is to change the expansion size without changing the number of effective elements. The underlying capacity may change during operation
// v.reserve(100);
// During element insertion, the original space may be released due to capacity expansion
// v.insert(v.begin(), 0);
// v.push_back(8);
// Assigning a new value to the vector may cause the underlying capacity to change
v.assign(100, 8);
/*
Error reason: the above operations may lead to the expansion of the vector, that is, the old space of the underlying principle of the vector is released,
When printing, it also uses to release the old space between them. When operating on the IT iterator, the actual operation is a piece of space that has been released
Space, causing the code to crash at runtime.
Solution: after the above operations are completed, if you want to continue to operate the elements in the vector through the iterator, you just need to re-enter it
Assignment is enough.
*/
while(it != v.end())
{
cout<< *it << " " ;
++it;
}
cout<<endl;
return 0;
}
- Delete the specified location element – erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// Use find to find the iterator where 3 is located
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// Deleting the data at the pos location will invalidate the pos iterator.
v.erase(pos);
cout << *pos << endl; // This will result in illegal access
return 0;
}
After erase deletes the pos position element, the element after the pos position will move forward without changing the underlying space. Theoretically, the iterator should not fail
However, if pos happens to be the last element, after deletion, pos happens to be the end position, and the end position has no element, then pos will become invalid. Therefore, when you delete an element at any position in the vector, vs considers the position iterator invalid.
The function of the following code is to delete even numbers in the array. Code 1 has the problem of iterator failure, and code 2 is correct
❗❗❗❗❗ Solution to iterator failure: reassign the iterator before use ❗❗❗❗❗
Code one
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
return 0;
}
Code 2
int main()
{
vector<int> v{ 1, 2, 3, 4 };
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
it = v.erase(it); //Reassign to iterators
else
++it;
}
return 0;
5. Two dimensional dynamic array
To build a two-dimensional dynamic array, the idea is the same as that of the two-dimensional array learned before:Just treat each row as a one-dimensional array
vector<vector<int>> vv;
Suppose we construct a 5 × 5 and assign all elements to 1
- From the perspective of two-dimensional array, create five rows, that is, five one-dimensional arrays
vv.resize(5);
- From the perspective of one-dimensional array, each row is given 5 1s
for(int i = 0; i < vv.size(); i++)
{
vv[i].resize(5, 1);
}
