vector and string Although the bottom layer is realized through the sequence table , But they do it differently ,string Yes, the type is specified , By using sequence table to store and manipulate data , and vector It's the use of C++ Generic templates in , Any type of data can be stored , And in vector in , There is no valid character or capacity , The bottom layer is operated by iterators , The underlying implementation of iterator is pointer , So ,vector Pointer is used to operate on any order table .
<>vector attribute
* _start Used to point to the first valid element
* _finish Used to point to the next position of the last valid element
* _endOfStorage It is used to point to the next position of the last position in the opened space
* vector The iterator of is the original ecology T* iterator template<class T> class Vector { public: typedef T*
iterator; typedef const T* const_iterator; private: iterator _start; iterator
_finish; iterator _endOfStorage; };
<> Constructors
* Parameterless default constructor , Leave all properties empty
* with n individual val Initializing constructor , Open up first n A space , Then set the values of these spaces to val, And update _finish and _endOfStorage The location of
* Constructors initialized by passing parameters through iterators , Using a new iterator , Insert data into a new space by tailing
The reason for using the new iterator is that the incoming iterator can be of any type , If used Vector Iterator of , Then the type of the iterator passed in can only be the same as Vector It's the same type , Take it here string give an example , Create a char Type Vector,Vector, But the incoming iterator is not char Type , It can be an iterator of a character array or a string Iterator of . As long as the dereference is char Type is OK
// Nonparametric default construction Vector() :_start(nullptr) ,_finish(nullptr) ,_endOfStorage(nullptr) {}
//n individual val Constructor for Vector(int n, const T& val = T()) :_start(new T[n]) ,_finish(_start
+n) ,_endOfStorage(_finish) { for (int i = 0; i < n; ++i) { _start[i] = val; } }
// Constructors generated by iterators template<class InputIterator> Vector(InputIterator first,
InputIterator last) :_start(nullptr) , _finish(nullptr) , _endOfStorage(nullptr)
{ while (first != last) { pushBack(*first); ++first; } }
The running results are in begin() and end() In implementation
<>size() and capacity()
The value of pointer subtraction is the number of elements between the two pointers
size_t size() const { return _finish - _start; } size_t capacity() const {
return _endOfStorage - _start; }
<>pushBack()
* Check the capacity , If _finish and _endOfStorage The pointer is equal , It means the capacity is full , More space needs to be opened up
* stay _finish Position insert new data
* to update _finish void pushBack(const T& val) { // Check the capacity if (_finish == _endOfStorage)
{ size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity(); reserve(newC); }
// insert data *_finish = val; // to update finish ++_finish }
The running results are in begin() and end() In implementation
<>reserve
* inspect n The rationality of ,reserve We can only expand, not shrink the space
* Save the number of valid elements , For later updates _finish use
* Apply for space and copy data to new space , Release the old emptiness
*
to update 3 Member variables , be careful _finish Cannot update to _finish+size(), as a result of size() It's calculated by two pointers , At this time _fiinsh Has pointed to the space of release , You'll make a mistake if you use it again , So that's why there's a second step
The following code has a shallow copy problem , The correct deep copy code and detailed explanation will be given at the end of the article
void reserve(size_t n) { //reserve We can only expand space, not shrink it if (n > capacity()) { // Save valid elements
size_t sz= size(); // Application space T* tmp = new T[n]; // Copy data to a new space if (_start != nullptr)
{ // Copy valid elements memcpy(tmp, _start, sizeof(T) * size()); delete[] _start; } // to update
_start= tmp; _finish = _start + sz; _endOfStorage = _start + n; } }
The running results are in begin() and end() In implementation
<>begin() and end()
iterator begin() { return _start; } iterator end() { return _finish; }
const_iteratorbegin() const { return _start; } const_iterator end() const {
return _finish; }
Yes begin() and end Can be used in the range for
template<class T> void printVectorFor(Vector<T>& vec) { for (auto& e : vec) {
cout<< e; } cout << endl; }
<>[] Operator overloading
T& operator[](size_t pos) { assert(pos < size()); return _start[pos]; } const
T& operator[](size_t pos) const { assert(pos < size()); return _start[pos]; }
<>resize()
* n <= size Direct update _finish It's just the right place
* size < n <= capacity, from _finish Start adding elements , Added _start+n The location of , Then perform the first step
* n > capacity increase capacity , Perform the second and first steps void resize(size_t n, const T& val = T()) { //3.n
>= capacity if (n > capacity()) { reserve(n); } //2.size < n <= capacity if (n >
size()) { while (_finish != _start + n) { *_finish = val; ++_finish; } }
//1.n<=size _finish = _start + n; }
<>insert()
* Check the validity of the inserted position [_start, _finish)
* Check the capacity , Due to the capacity increase will lead to pos Iterator failure , So we can save it first pos about _start Offset of offset, After capacity increase , And then pos Reassignment
pos=_start+offset
* Moving elements , Move from the back to the front , In the end pos The element of position is set to val
* to update _finish void insert(iterator pos, const T& val) { // Check location validity assert(pos >=
_start|| pos < _finish); // Check the capacity if (_finish == _endOfStorage) { // Compatibilization can cause iterator failure
// preservation pos and _start Offset of size_t offset = pos - _start; size_t newC = _endOfStorage ==
nullptr? 1 : 2 * capacity(); reserve(newC); // to update pos pos = _start + offset; }
// Moving elements iterator end = _finish; while (end != pos) { *end = *(end - 1); --end; }
// insert *pos = val; // to update ++_finish; }
<>erase()
* Check location validity
* Moving elements , Move from front to back
* to update _finish iterator erase(iterator pos) { // Check location validity assert(pos >= _start ||
pos< _finish); // Moving elements , Before and after iterator start = pos + 1; while (start != _finish) {
*(start - 1) = *start; ++start; } // to update --_finish; }
<>void popBack()
utilize erase Interface is deleted
void popBack() { if (size() > 0) erase(end() - 1); }
<> Destructor
~Vector() { if (_start) { delete[] _start; _start = _finish = _endOfStorage =
nullptr; } }
<> In the algorithm library find
Header file <algorithm>
template <class InputIterator, class T> InputIterator find (InputIterator first
, InputIterator last, const T& val)
Parameter content ( From iterator begin lead to end in , find val value , Find the iterator that returns the value , Return not found end)
<>reserve The problem of deep and shallow copy in computer
When we use custom type , Using shallow copy is the most efficient , But when we use custom types , And there is the use of memory resources , We must always pay attention to the problem of deep and shallow copy . Take a look at the following code test
void test() { Vector<string> v; string str1 = "123"; string str2 = "456";
string str3= "789"; v.pushBack(str1); v.pushBack(str2); v.pushBack(str3); }
Debugging results ：
When we insert the third string , There is a memory exception problem , Let's see what the problem is .
First insertion str1, no problem
Second insertion str2, We will expand the capacity before inserting , Will create 2 Twice the space tmp, And then through memcpy Memory Copy ( Shallow copy ) Copy content to tmp in , There are two points to one resource (123), After copying delete[] To delete the original space , take 123 After release , In fact, the first element of the new space points to a space that has been released , But the problem is not exposed , The insertion of the second element is also OK
third time str3 Insertion of , This insertion will also be expanded , We'll start with one 2 Twice the space tmp, And then through memcpy Memory Copy ( Shallow copy ) Copy content to tmp in , There are two pointers to the released resource （123）, There are two pointers to the resource （456）, When the copy is complete, the old space is released , When releasing the （456） No error will be reported in case of accident , The reason is the same as the second insertion . But when you release the first null pointer , Memory error exception will occur , The reason is resources （123） Has been released , If it is released again, it is a second release , It's not safe . Memory error will report exception .
Therefore, when we expand the capacity, we should not just make a shallow copy , That is to use memcpy To copy the content , We should use deep copy . take memcpy Change to for (size_t i = 0;
i < sz; ++i){tmp[i] = _start[i];}
The overall code is as follows ：
void reserve(size_t n) { //reserve We can only expand space, not shrink it if (n > capacity()) { // Save valid elements
size_t sz= size(); // Application space T* tmp = new T[n]; // Copy data to a new space if (_start != nullptr)
{ // Copy valid elements //memcpy(tmp, _start, sizeof(T) * size()); // Deep copy for (size_t i = 0; i
< sz; ++i) { // Calling a custom type assignment operator overloaded function , Deep copy complete // The premise is that the overloaded function is also a deep copy ,string yes STL In the library , It's a deep copy tmp
[i] = _start[i]; } delete[] _start; } // to update _start = tmp; _finish = _start + sz;
_endOfStorage= _start + n; } }
Technology