Rebirth: I am a C++ master (use and simulation of vector)

Vector usage and simulation implementation

  • Preface
  • 1. Use of vector
    • 1.1Construction of vector
    • 1.2vector iterator
    • 1.3vector spatial growth
    • 1.4vector addition, deletion, checking and modification
  • 2. Simulation implementation of vector
    • 2.1Construction of vector
    • 1.2vector iterator
    • 1.3vector spatial growth
    • 1.4 Addition, deletion, and modification of vector
  • Summarize

Foreword

After we learned about string, it was vector’s turn. The content of vector is similar to string, so we will briefly introduce a lot of knowledge, but vector also involves a more important concept, that is, iterator failure. Therefore, we will simply skip the use of vector and focus on the simulation implementation.

The use of .vector

Construction of 1.1vector

Function name Function introduction
vector() Construction without parameters
vector (size_type n, const value_type & amp; val = value_type()) Construct and initialize n vals
vector (const vector & amp; x) Copy construction
vector (InputIterator first , InputIterator last) Use iterator for initialization construction 
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main()
{<!-- -->
vector<int> v1;
for (auto ch : v1)
{<!-- -->
cout << ch << " ";
}
cout << endl;

vector<int> v2(10, 2);
for (auto ch : v2)
{<!-- -->
cout << ch << " ";
}
cout << endl;

\t
vector<int> v3(v2.begin(), v2.end());
for (auto ch : v3)
{<!-- -->
cout << ch << " ";
}
cout << endl;

vector<int> v4(v2);
for (auto ch : v4)
{<!-- -->
cout << ch << " ";
}
cout << endl;

\t
return 0;
}

1.2vector iterator

Function name Function introduction
begin + end Get the iterator/const_iterator of the first data position, get the iterator/const_iterator of the next position of the last data
rbegin + rend Get the reverse_iterator of the last data position, and get the reverse_iterator of the previous position of the first data 
void test_vector2()
{<!-- -->
vector<int> v(10, 2);
vector<int>::iterator it = v.begin();
while (it != v.end())
{<!-- -->
cout << *it << " ";
it++;
}
cout << endl;

for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}

int main()
{<!-- -->
\t
test_vector2();
return 0;
}

Space growth of 1.3vector

Function name Function introduction
size Get the number of data
capacity Get the capacity
reserve Change the capacity of the vector
resize Change the size of the vector
empty Determine whether it is empty

Notice:

  1. When the capacity code is run under vs and g++ respectively, you will find that the capacity increases by 1.5 times under vs and 2 times by g++. This issue is often investigated. Don’t rigidly believe that the vector capacity is increased by 2 times. The specific increase is defined based on specific needs. vs is the PJ version STL, g++ is the SGI version STL.
  2. Reserve is only responsible for opening up space. If you know for sure how much space is needed, reserve can alleviate the cost problem of vector expansion.
  3. Resize will also initialize while opening space, which affects size.
void test_vector3()
{<!-- -->
vector<int> v(10, 2);
cout << v.size() << endl;
cout << v.capacity() << endl;

v.reserve(100);
v.resize(20, 5);
cout << v.size() << endl;
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}

int main()
{<!-- -->
test_vector3();
return 0;
}

1.4vector addition, deletion, checking and modification

Function name Function introduction
push_back Tail insertion
pop_back Tail deletion
find Find. (Note that this is an algorithm module implementation, not a member interface of vector)
insert Insert val before position
erase Delete the data at position position
swap Exchange the data space of two vectors
operator[] Access like array 
void test_vector4()
{<!-- -->
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
cout << v[i] << " ";
}
cout << endl;

v.pop_back();
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
cout << v[i] << " ";
}
cout << endl;


vector<int>::iterator pos = find(v.begin(),v.end(),2);
v.insert(pos, 4);
vector<int>::iterator pos1 = find(v.begin(), v.end(), 3);
v.erase(pos1);
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
cout << v[i] << " ";
}
cout << endl;

}

int main()
{<!-- -->
test_vector4();
return 0;
}

Simulation implementation of 2.vector

Construction of 2.1vector

#include <iostream>
#include <vector>
#include <string>
using namespace std;
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_shorage(nullptr)
{<!-- -->}
~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}
private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};

int main()
{<!-- -->
test_vector4();
return 0;
}

1.2vector iterator

#include <iostream>
#include <vector>
#include <string>
using namespace std;
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
,_finish(nullptr)
,_end_of_shorage(nullptr)
{<!-- -->}
~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}
iterator begin()const
{<!-- -->
return _start;
}
iterator end()const
{<!-- -->
return _finish;
}

private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};

Space growth of 1.3vector

#include <iostream>
#include <vector>
#include <string>
using namespace std;
namespace Std
{<!-- -->
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_shorage(nullptr)
{<!-- -->}

~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}

Vector(const Vector & amp; v)
{<!-- -->
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
_start[i] = v._start[i];
}
}

void Swap(Vector & tmp)
{<!-- -->
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_shorage, tmp._end_of_shorage);
}

Vector & amp; operator[](Vector & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}

iterator begin()const
{<!-- -->
return _start;
}

iterator end()const
{<!-- -->
return _finish;
}

size_t size()
{<!-- -->
return _finish - _start;
}

size_t capacity()
{<!-- -->
return _end_of_shorage - _start;
}

void reserve(size_t n)
{<!-- -->
size_t sz = size();
if (n > capacity())
{<!-- -->
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * sz);
//If we use memecpy to copy values,
//It can be used perfectly when faced with built-in types or classes that do not require additional space, such as the Date class.
//But for classes such as string, memcpy only performs a shallow copy, which will cause the problem of wild pointers.
//So we have to use the overloaded assignment operator to perform deep copy
for (size_t i = 0; i < size(); i + + )
{<!-- -->
tmp[i] = _start[i];//Overloaded assignment operator
}

delete[] _start;
_start = tmp;
_finish = _start + sz;
_end_of_shorage = _start + n;
}
}

void resize(size_t n, const T & amp; c = T())
{<!-- -->
if (n < size())
{<!-- -->
_finish = _start + n;
}
else
{<!-- -->
reserve(n);
while (_finish < _start + n)
{<!-- -->
*_finish = c;
_finish + + ;
}

}
}
private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};
void test_vector5()
{<!-- -->
Vector<int> v;
cout << v.size() << endl;

v.resize(10, 2);
v.reserve(100);
cout << v.size() << endl;
cout << v.capacity() << endl;
}
}

using namespace Std;
int main()
{<!-- -->
Std::test_vector5();
return 0;
}

1.4vector addition, deletion and modification

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <assert.h>
namespace Std
{<!-- -->
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_shorage(nullptr)
{<!-- -->}

~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}

Vector(const Vector & amp; v)
{<!-- -->
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
_start[i] = v._start[i];
}
}

void Swap(Vector & tmp)
{<!-- -->
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_shorage, tmp._end_of_shorage);
}

Vector & amp; operator=(Vector & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}

iterator begin()const
{<!-- -->
return _start;
}

iterator end()const
{<!-- -->
return _finish;
}

size_t size()
{<!-- -->
return _finish - _start;
}

size_t capacity()
{<!-- -->
return _end_of_shorage - _start;
}

void reserve(size_t n)
{<!-- -->
size_t sz = size();
if (n > capacity())
{<!-- -->
T* tmp = new T[n];
//memcpy(tmp, _start, sizeof(T) * sz);
//The iterator fails
for (size_t i = 0; i < size(); i + + )
{<!-- -->
tmp[i] = _start[i];//Overloaded assignment operation
}

delete[] _start;
_start = tmp;
_finish = _start + sz;
_end_of_shorage = _start + n;
}
}

void resize(size_t n, const T & amp; c = T())
{<!-- -->
if (n < size())
{<!-- -->
_finish = _start + n;
}
else
{<!-- -->
reserve(n);
while (_finish < _start + n)
{<!-- -->
*_finish = c;
_finish + + ;
}

}
}

T & operator[](const size_t n)
{<!-- -->
assert(n <= _finish);
assert(n >= _start);
return _start[n];
}

void push_back(const T & val)
{<!-- -->
if (_finish == _end_of_shorage)
{<!-- -->
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = val;
_finish + + ;
}

void pop_back()
{<!-- -->
_finish--;
}

void insert(iterator pos, const T & val)
{<!-- -->
assert(pos <= _finish);
assert(pos >= _start);
if (_finish == _end_of_shorage)
{<!-- -->
//The iterator fails
//If the capacity is expanded, pos points to the space before expansion.
//It's like when you come home for the holidays and your parents forget to tell you that they've moved.
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{<!-- -->
*(end + 1) = *end;
end--;
}
*pos = val;
_finish + + ;
}
//The iterator fails
/*void erase(iterator pos)
{
assert(pos < _finish);
assert(pos >= _start);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
it++;
}
_finish--;
}*/
iterator erase(iterator pos)
{<!-- -->
assert(pos < _finish);
assert(pos >= _start);
iterator it = pos + 1;
while (it < _finish)
{<!-- -->
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}

private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};
}

Iterator invalid:
The main function of an iterator is to allow the algorithm to not care about the underlying data structure. The underlying layer is actually a pointer, or a pointer encapsulation, such as: vector iterator It is the original ecological pointer T*. Therefore, when the iterator fails, it actually means that the space pointed to by the corresponding pointer at the bottom of the iterator is destroyed, and using a space that has been released will cause the program to crash (that is, if you continue to use the expired space) iterator, the program may crash).
Operations on vector that may cause its iterator to become invalid include:

  1. Operations that will cause its underlying space to change may cause the iterator to fail, such as: resize, reserve, insert, assign, push_back, etc.

Cause of error: The above operations may lead to vector expansion, which means that the old space of the underlying principle of vector is released, and when printing, it still uses The old space between releases When operating on the it iterator, a piece of space that has been released is actually operated, causing the code to crash during runtime.
Solution: After the above operation is completed, if you want to continue to operate the elements in the vector through the iterator, just reassign the value to it.

void insert(iterator pos, const T & amp; ch = T())
{<!-- -->
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _end_of_storage)
{<!-- -->
//The iterator fails
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() *2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{<!-- -->
*(end + 1) = *end;
end--;
}
*pos = ch;
_finish + + ;
}
void test_vector6()
{<!-- -->
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;

//If we don't update pos, the operation here will crash
v.insert(v.begin(), 0);

v.insert(v.end(), 5);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}
  1. Deletion operation of the element at the specified position –erase
#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <assert.h>
namespace Std
{<!-- -->
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_shorage(nullptr)
{<!-- -->}

~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}

Vector(const Vector & amp; v)
{<!-- -->
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
_start[i] = v._start[i];
}
}

void Swap(Vector & tmp)
{<!-- -->
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_shorage, tmp._end_of_shorage);
}

Vector & amp; operator=(Vector & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}

//The iterator fails
void erase(iterator pos)
{<!-- -->
assert(pos < _finish);
assert(pos >= _start);
iterator it = pos + 1;
while (it < _finish)
{<!-- -->
*(it - 1) = *it;
it++;
}
_finish--;
}
\t\t
private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};
void test_vector7()
{<!-- -->
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;

//If we want to delete even numbers
Vector<int>::iterator it = v.begin();
while (it != v.end())
{<!-- -->
if (*it % 2 == 0)
{<!-- -->
v.erase(it);
}
+ + it;
}
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}
void test_vector8()
{<!-- -->
Vector<int> v;
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;

//If we want to delete even numbers
Vector<int>::iterator it = v.begin();
while (it != v.end())
{<!-- -->
if (*it % 2 == 0)
{<!-- -->
v.erase(it);
}
+ + it;
}
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}
void test_vector9()
{<!-- -->
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;

//If we want to delete even numbers
Vector<int>::iterator it = v.begin();
while (it != v.end())
{<!-- -->
if (*it % 2 == 0)
{<!-- -->
v.erase(it);
}
+ + it;
}
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}

}

using namespace Std;
int main()
{<!-- -->
Std::test_vector7();
//Previous:12345
//After:135
Std::test_vector8();
//Previous:22345
//After:235
Std::test_vector9();
//Previous:123456
//After: crash
return 0;
}

In the above three test samples, we can find that the first 12345 result is correct, the second 22345 result is wrong, and the third 123456 program crashes directly.
Now let’s debug three examples:

  1. Although the result of the first example is correct, during our debugging process we can find that the two data 3 and 5 have not been judged at all. This is because when we judged 2, we deleted 2 after the judgment was successful. At this time, 3 was moved to the original position of 2, but pos was moved again + +, so 3 was not judged at all and the same is true for 5.
  2. After we analyzed the first example, the result of the second example can be imagined. When two even numbers are put together, when we delete the first even number, the second even number is skipped directly.
  3. The third example is because when it reaches the 6 position, the judgment is successful, so we need to run the erase program, and _finish will be – so the value of end() will change. At this time, it is + + causing it to never be equal to end() and also violates the assertion of it<_finish, causing a crash.

To solve this problem, we need to let the program perform erase(). It will not + + point to the next data of the deleted data, but when erase() is not performed, + + it.
After studying the document of erase in vector, we can find that the erase in the document does not return a value but returns an iterator, that is, T*.

So we can set the return value of erase to pos and change the operation after judging the condition.

#include <iostream>
#include <vector>
#include <string>
using namespace std;
#include <assert.h>
namespace Std
{<!-- -->
template <class T>
class Vector
{<!-- -->
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_shorage(nullptr)
{<!-- -->}

~Vector()
{<!-- -->
delete[] _start;
_start = _finish = _end_of_shorage = nullptr;
}

Vector(const Vector & amp; v)
{<!-- -->
reserve(v.capacity());
for (size_t i = 0; i < v.size(); i + + )
{<!-- -->
_start[i] = v._start[i];
}
}

void Swap(Vector & tmp)
{<!-- -->
std::swap(_start, tmp._start);
std::swap(_finish, tmp._finish);
std::swap(_end_of_shorage, tmp._end_of_shorage);
}

Vector & amp; operator=(Vector & amp; tmp)
{<!-- -->
Swap(tmp);
return *this;
}
\t\t
iterator erase(iterator pos)
{<!-- -->
assert(pos < _finish);
assert(pos >= _start);
iterator it = pos + 1;
while (it < _finish)
{<!-- -->
*(it - 1) = *it;
it++;
}
_finish--;
return pos;
}

private:
iterator_start;
iterator_finish;
iterator _end_of_shorage;
};
void test_vector10()
{<!-- -->
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;

//If we want to delete even numbers
Vector<int>::iterator it = v.begin();
while (it != v.end())
{<!-- -->
if (*it % 2 == 0)
{<!-- -->
it = v.erase(it);
}
else
{<!-- -->
+ + it;
}
\t\t\t
}
for (auto ch : v)
{<!-- -->
cout << ch << " ";
}
cout << endl;
}
}

using namespace Std;
int main()
{<!-- -->
Std::test_vector10();
return 0;
}

Summary

In the study of vector, we have the previous foundation of string, so there is no problem in writing most functions, but we also need to pay attention to the issues related to deep copy. The most fruitful thing for us in vector is the failure of iterators, so we still need to study whether there are also iterator failures in string. At the same time, we must also be more vigilant about iterator failures in subsequent studies. After vector, we will learn about the linked list in the data structure, so stay tuned!