[C++] STL_vector usage with mock implementation of common interfaces

1. Introduction of vector

Introduction to vector documentation

1. A vector is a sequence container representing a variable-size array.
2. Like arrays, vectors use contiguous storage to store elements. This means that the elements of a vector can be accessed using subscripts, which is just as efficient as an array. But unlike an array, its size can be changed dynamically, and its size is automatically handled by the container.
3. Essentially, a vector uses a dynamically allocated array to store its elements. When a new element is inserted, the array needs to be reallocated in order to increase storage space. This is done by allocating a new array and then moving all the elements into it. This is a relatively costly task in terms of time because the vector is not reallocated every time a new element is added to the container.
4. vector allocation space strategy: vectors allocate some extra space to accommodate possible growth because the storage space is larger than the actual storage space needed. Different libraries use different strategies to weigh space usage and reallocation. But in any case, reallocations should be logarithmically growing interval sizes such that inserting an element at the end is done in constant time complexity.
5. As a result, vectors take up more storage space, in order to gain the ability to manage storage space and grow dynamically in an efficient way.
6. Compared to other dynamic sequence containers (deque, list and forward_list), vector is more efficient at accessing elements, and relatively efficient at adding and removing elements at the end. It is less efficient for other delete and insert operations that are not at the end. Better than list and forward_list unified iterator and reference.

2. Use of vector

vector is very important in practice, in practice we are familiar with common interfaces can be.Below is a list of which interfaces to focus on and will simulate the implementation.

2.1 Definition of vector

(constructor) Constructor declarations	Interface Description
vector() (emphasis added)	nonparametric construction (math.)
vector（size_type n, const value_type& val = value_type()	Construct and initialize n val
vector (const vector& x); (emphasis added)	copy construction (math.)
vector (InputIterator first, InputIterator last);	Initialization constructs using iterators

Code Implementation:

template<class T>
    class vector
    {
    public:
    	typedef T* iterator;//typedef put in public if you want to give it to others, private if you don't want to
        typedef const T* const_iterator;

    	vector()
        {}

        vector(int n, const T& value = T())
        {
            reserve(n);
            for (size_t i = 0; i < n; i++)
            {
                push_back(value);
            }
        }

        template<class InputIterator>

        vector(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                push_back(*first);
                ++first;
            }   
        }

        vector(const vector<T>& v)
        {
            reserve(v.capacity());
            for (auto& e : v)
            {
                push_back(e);
            }
        }

    private:
    iterator _start = nullptr; // point to the start of the data block
    iterator _finish = nullptr; // point to the end of valid data
    iterator _endOfStorage = nullptr; // point to end of storage capacity
};

2.2 Use of vector iterators

Iterators in vector are also native pointers at the bottom.

Use of iterator	Interface Description
begin + end(emphasis)	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, get the reverse_iterator of the first data previous position

Analog Realization:

typedef T* iterator;//typedef put in public if you want to give it to others, private if you don't want to
typedef const T* const_iterator;

iterator begin()
{
    return _start;
}

iterator end()
{
    return _finish;
}

const_iterator begin() const
{
    return _start;
}

const_iterator end() const
{
    return _finish;
}

Use:
Iterators are generally used in traversals, so let’s take a look.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v;
	//We are using push_back here to insert the data
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);

	// Iterator way traversal
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}

	return 0;
}

2.3 Spatial growth problems for vectors

volume space	Interface Description
size	Get number of data
capacity	Get capacity size
empty	Determine if it is empty
RESIZE (emphasis added)	Changing the size of a vector
RESERVE (emphasis added)	Change the capacity of the vector

reserve interface:
reserve is only responsible for opening up space, and if you know for sure how much space you need to use, reserve can alleviate the problem of costly defects in vector augmentation.

void reserve(size_t n)//reserve only expands
{
    if (n > capacity())
    {
        T* tmp = new T[n];
        size_t sz = size();//Here you have to write down sz first, _finish will have problems if you directly +size()
                           //_start refers to the new space, call size(), size() will go wrong internally
                           //So it's best to write it down first and use it later.
        if (_start)
        {
            //memcpy is a shallow copy, which can be problematic
            //memcpy(tmp, _start, sizeof(T) * sz);
            for (size_t i = 0; i < size(); i++)
            {
                tmp[i] = _start[i];
            }
            delete[] _start;
        }

        _start = tmp;
        _finish = _start + sz;
        _endOfStorage = _start + n;
    }
}

resize interface:
resize will also be initialized while opening space, affecting size.

void resize(size_t n, const T& value = T())//anonymous objects/temporary objects have constancy and need const modifier
{
    if (n <= size())// Shrink
    {
        _finish = _start + n;
    }
    else
    {
        reserve(n);// here you can not judge whether to expand the capacity, reserve inside will judge the

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

Several other interfaces are simpler and straightforward to implement:

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

size_t capacity() const
{
    return _endOfStorage - _start;
}

bool empty()
{
	return _finish - _start == 0;
}

Caution:

There’s a difference when it comes to expandingThe capacity is increased by 1.5x in vs, and by 2x in g++.. Don’t solidify that vector capacity increases are all 2x, how much is defined by specific requirements. vs is the PJ version of STL, g++ is the SGI version of STL.
Let’s test it:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	vector<int> v;
	size_t sz = v.capacity();

	for (size_t i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed：" << sz << endl;
		}
	}

	return 0;
}

3, vector add, delete, check and change

vector add, delete, check and change	Interface Description
push_back (emphasis added)	tail plug
pop_back (emphasis added)	padded, sleeveless undergarment worn by men
find	find
insert	Insert val before position
erase	Delete data at position
swap	Swap the data space of two vectors
operator[] (emphasis added)	Access like an array

3.1 push_back (emphasis added)

Let’s sort out the idea of tail plugs:
1, first determine whether the capacity is full, if full first expansion. Here note that the tail plug is empty, here use the Miki operator to judge, if empty first expand 4 space, otherwise 2 times the expansion method.
2, tail plug, then ++_finish.

void push_back(const T& x)
{
    if (_finish == _endOfStorage)
    {
        reserve(capacity() == 0 ? 4 : 2 * capacity());
    }

    *_finish = x;
    ++_finish;
}

3.2 pop_back (emphasis added)

In the case of tail deletion we are still judging first
This time we need to judge the null, assert(_finish – _start ! = 0), and then de-tail delete, so that _finish- is just fine, and the next time we tail insert it, we just overwrite it.

void pop_back()
{
    assert(_finish-_start != 0);

    --_finish;
    //erase(end() - 1);
}

3.3 operator[] (emphasis added)

The overloading of [] is to return the data on the pos position can be, relatively simple and direct seconds.
We give two interfaces here, one read-only and one modifiable.

T& operator[](size_t pos)// Write
{
    assert(pos < size());// determine if the position is legal or not
    return _start[pos];
}

const T& operator[](size_t pos)const// Read
{
    assert(pos < size());
    return _start[pos];
}

3.4 insert

insert is to insert a piece of data at position pos.
Thoughts:
1, first determine whether the pos position is legal;
2, judgment full, if full need to expand capacity, in the expansion of the need to pay attention to the problem of iterator failure;
3, because the insertion of data on the existence of moving data, so you need to move the data first, wefrom back to front Move the data back one position in sequence to the pos position;
4, and then go to the pos position to insert data, and finally return to the pos position.

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);

    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;//first note down the distance from _start to pos position, since the iterator pos will fail after expansion
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;//new space needed to update iterator pos
    }

    iterator end = _finish - 1;
    //Mobile data
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }

    *pos = x;
    ++_finish;

    return pos;
}

3.5 erase

erase is to delete the data at position pos.
Thoughts:
1. Determine if the pos location is legal;
2. Move the data fromPos position to end Move the data forward sequentially, and simply overwrite the data at pos with the data at pos+1;
3. -_finish, just return to the pos position.

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);

    iterator it = pos + 1;
    //Mobile data
    while (it < _endOfStorage)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;

    return pos;
}

3.6 swap

Our vector’s swap is just straightforward to implement by applying the library function’s swap.

void swap(vector<T>& v)
{
    std::swap(_start, v._start);
    std::swap(_finish, v._finish);
    std::swap(_endOfStorage, v._endOfStorage);
}

*** Conclusion of the present article ***