C++ series vector class simulation implementation

Blog: Xiaoyi
Personal profile: Newbie in programming
If the blog is useful to everyone, please like, follow and save it

Constructor

vector()

//_begin represents the beginning of valid members
//_finish represents the size of the effective member
//_end represents the effective volume
vector()
:_begin(nullptr)
,_finish(nullptr)
,_end(nullptr)
{<!-- -->
}

vector(size_t n, const T & amp; value = T())

//The reason why memcpy copy is not used here is
//1. memcpy is a binary format copy of memory. It copies the contents of one memory space to another memory space intact.
//2. If you copy elements of built-in types, memcpy is efficient and error-free, but if you copy elements of custom types, and resource management is involved in custom type elements, errors will occur because memcpy The copy is actually a shallow copy.
//3. Built-in types also have copy construction
vector(int n, const T & amp; value = T())
:_begin(nullptr)
, _finish(nullptr)
, _end(nullptr)
{<!-- -->
_begin = new T[n];
_finish = _begin + n;
_end = _begin + n;
for (int i = 0; i < n; i + + )
{<!-- -->
*(_begin + i) = value;
}
\t\t\t
}

//Convenient writing method
/*vector(int n, const T & amp; value = T())
{
reserve(n);
for (int i = 0; i < n; i + + )
{
_begin[i] = value;
}
}
vector(int n, const T & amp; value = T())
{
resize(n,value);
}*/

vector(InputIterator first, InputIterator last)

//Iterator construction
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{<!-- -->
while (first!= last)
{<!-- -->
push_back(*first);//Tail insertion
first++;
}
}

vector(vector & amp; v)

//Copy construction
vector(vector<T> & amp; v)
{<!-- -->
size_t size = v._finish - v._begin;
size_t capacity = v. _end - v._begin;
_begin = new T[capacity];
for (size_t i = 0; i < size; i + + )
{<!-- -->
*(_begin + i) = *(v._begin + i);
}
_finish = _begin + size;
_end = _begin + capacity;
}
//Simple writing method
vector(vector<T> & amp; v)
{<!-- -->
vector<T> tmp(v.begin(),v.end());
swap(tmp);
}

Destructor

~vector()

~vector()
{<!-- -->
if (_begin)
{<!-- -->
delete[] _begin;
_begin = _end = _finish = nullptr;
}
}

Operator overloading

vector & amp; operator = (vector v)

//Assignment copy
vector<T> & operator = (vector<T> v)
{<!-- -->
swap(v);//What is passed here is a copy of v. Changing v does not affect the original object.
return *this;
}

T & amp; operator[](size_t pos);

T & operator[](size_t pos)
{<!-- -->
assert(pos >= 0 & amp; & amp; pos < size());//pos is in the valid range
return _begin[pos];
}
//const object call
const T & amp; operator[](size_t pos)const
{<!-- -->
assert(pos >= _begin & amp; & amp; pos < _finish);
return _begin[pos];
}

Query vector volume and size

size_t size()

size_t capacity()

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

size_t capacity() const
{<!-- -->
return _end - _begin;
}
size_t size()
{<!-- -->
return _finish - _begin;
}

size_t capacity()
{<!-- -->
return _end - _begin;
}

Adjust the volume and size of vector

void reserve(size_t n)

void resize(size_t n, const T & amp; value = T())

//After the expansion occurs here, the original _begin, _finish, _end will change, so they need to be updated after the expansion.
void reserve(size_t n)
{<!-- -->
if(n > capacity())
{<!-- -->
size_t oldsize = size();
T* tmp = new T[n];
for (size_t i = 0; i < oldsize; i + + )
{<!-- -->
tmp[i] = _begin[i];
}
delete[] _begin;
_begin = tmp;
_finish = tmp + oldsize;
_end = tmp + n;
}
}

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

Modify vector (head insertion, tail insertion, insertion, deletion, exchange)

void push_back(const T & amp; x)

void pop_back()

iterator insert(iterator pos, const T & amp; x)

iterator erase(iterator pos)

void swap(vector & amp; v)

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

void pop_back()
{<!-- -->
assert(_begin != _finish);
_finish--;
}
//The iterator failure problem will occur here,
//Reason 1: If an expansion occurs, the original pos in the function will become a wild pointer and needs to be updated in time. The pos outside the function will not change, so the new pointer of pos must be returned.
//Reason 2. Because the data is inserted, the original meaning of pos changes, so it must be updated in time so that pos points to the newly inserted element.
//The correct approach is to return the pointer inserted by the iterator
iterator insert(iterator pos, const T & amp; x)
{<!-- -->
assert(pos >= _begin & amp; & amp; pos <= _finish);
if (_finish == _end)
{<!-- -->
size_t size = pos - _begin;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _begin + size;
}
iterator end = _finish - 1;
while (end >= pos)
{<!-- -->
*(end + 1) = *(end);
end--;
}
*pos = x;
_finish + + ;
return pos;
}
//Reason for iterator failure 1. After erase deletes the element at pos position, the elements after pos position will be moved forward, without causing changes in the underlying space. Theoretically, the iterator should not fail, but: if pos happens to be the last one Element, after deletion, pos happens to be the position of end, and there is no element at the end position, so pos becomes invalid. Therefore, when deleting an element at any position in the vector, vs considers the iterator at that position to be invalid.
// Reason 2 for iterator failure: the meaning of pos position changes after erase, so the iterator needs to be updated
//The correct approach is to return the next pointer of the iterator
iterator erase(iterator pos)
{<!-- -->
assert(pos >= _begin & amp; & amp; pos <_finish );
iterator end = pos + 1;
while (end < _finish)
{<!-- -->
*(end - 1) = *(end);
end + + ;
}
_finish--;
return pos;
}
void swap(vector<T> & amp; v)
{<!-- -->
std::swap(_begin,v._begin);
std::swap(_finish,v._finish);
std::swap(_end,v._end);
}

Iterator of vector

typedef T* iterator;
typedef const T* const_iterator;

Complete code

namespace zjy
{
template
class vector
{
public:
\t\t        
typedef T* iterator;
typedef const T* const_iterator;

iterator begin()
{
return _begin;
}

iterator end()
{
return _finish;
}

const_iterator cbegin()
{
return _begin();
}

const_iterator cend() const
{
return _finish;
}



vector()
:_begin(nullptr)
,_finish(nullptr)
,_end(nullptr)
{

}

vector(int n, const T & amp; value = T())
:_begin(nullptr)
, _finish(nullptr)
, _end(nullptr)
{
_begin = new T[n];
_finish = _begin + n;
_end = _begin + n;
for (int i = 0; i < n; i + + )
{
*(_begin + i) = value;
}
}

//vector(int n, const T & amp; value = T())
//{
// reserve(n);
// for (int i = 0; i < n; i + + )
// {
// _begin[i] = value;
// }
//}
//vector(int n, const T & amp; value = T())
//{
// resize(n,value);
//}

template
vector(InputIterator first, InputIterator last)
{

while (first!= last)
{
push_back(*first);
first++;
\t\t\t\t
}
}

vector(vector & amp; v)
{
size_t size = v._finish - v._begin;
size_t capacity = v. _end - v._begin;
_begin = new T[capacity];
for (size_t i = 0; i < size; i + + )
{
*(_begin + i) = *(v._begin + i);
}
_finish = _begin + size;
_end = _begin + capacity;
}
//vector(vector & amp; v)
//{
// vector tmp(v.begin(),v.end());
// swap(tmp);
//}

vector & operator = (vector v)
{
swap(v);
return *this;
}

~vector()
{<!-- -->
if (_begin)
{<!-- -->
delete[] _begin;
_begin = _end = _finish = nullptr;
}
}


size_t size() const
{
return _finish - _begin;
}

size_t capacity() const
{
return _end - _begin;
}

void reserve(size_t n)
{
if(n > capacity())
{
size_t oldsize = size();
T* tmp = new T[n];
for (size_t i = 0; i < oldsize; i + + )
{
tmp[i] = _begin[i];
}
delete[] _begin;

_begin = tmp;
_finish = tmp + oldsize;
_end = tmp + n;
}
}

void resize(size_t n, const T & amp; value = T())
{
if (n < size())
{
_finish = _begin + n;
}
else
{
if (n > capacity())
{
reserve(n);
}

while(_finish < _begin + n)
{
*(_finish + + ) = value;

}
}
}

T & operator[](size_t pos)
{
assert(pos >= 0 & amp; & amp; pos < size());
return _begin[pos];
}

const T & amp; operator[](size_t pos)const
{
assert(pos >= _begin & amp; & amp; pos < _finish);
return _begin[pos];
}
void push_back(const T & x)
{
if (_finish == _end)
{
reserve(capacity() == 0? 4: capacity()*2);
}
*_finish = x;
_finish + + ;
}

void pop_back()
{
assert(_begin != _finish);
_finish--;
}

void swap(vector & amp; v)
{
std::swap(_begin,v._begin);
std::swap(_finish,v._finish);
std::swap(_end,v._end);
}

iterator insert(iterator pos, const T & amp; x)
{
assert(pos >= _begin & amp; & amp; pos <= _finish);
if (_finish == _end)
{
size_t size = pos - _begin;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _begin + size;
}
\t\t\t
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *(end);
end--;
}

*pos = x;
\t\t
_finish + + ;
return pos;

}

iterator erase(iterator pos)
{
assert(pos >= _begin & amp; & amp; pos <_finish );
iterator end = pos + 1;
while (end < _finish)
{
*(end - 1) = *(end);
end + + ;

}
_finish--;
return pos;

}
private:
T* _begin = nullptr;
T* _finish = nullptr;
T* _end = nullptr;
};
}