Zero. Preface

This chapter will learn the vector class in C + +, master its use and simulation implementation

1, What is a vector

• Introduction:

Vector is a sequence container representing variable size arrays. It also uses continuous storage space to store elements (very similar to string, string stores characters, and vector can store multiple types). Subscripts can be used to access the elements of vector (the space is continuous), but the size can be changed dynamically

• Space allocation policy:

vector will allocate some additional space to accommodate possible growth, because the storage space is larger than the actual storage space. Different libraries and platforms use different strategies to balance the use and reallocation of space (that is, they occupy more storage space and grow dynamically in an effective way)

• Advantages and disadvantages:

Compared with other dynamic sequence containers, 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 not at the end, the efficiency is lower

2, Common interface description of vector

Note: the function operation of vector is basically similar to that of string

1. Common constructs for vector objects

Constructor declaration	Interface description
vector() (key)	Nonparametric structure
vector(size_type n, const value_type& val = value_type())	Construct and initialize n Vals
vector (const vector& x); (key points)	copy construction
vector (InputIterator first, InputIterator last);	Initializing constructs using iterators

• Use example:

void test_vector1()
{
	//vector is a template class. You need to specify the type when instantiating an object
	vector<int> first; //Empty vector
	vector<int> second(4, 100); //Initialization structure (4 spaces, each storing 100)
	vector<int> third(second.begin(), second.end()); // Iterator initialization construct
	vector<int> fourth(third); //copy construction 
	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//Array pointer interval construction (essentially consistent with iterators)
}

• result:

2. vector object capacity operation

Function name	Function description
size (key)	Returns the valid character length of a string
capacity	Returns the total size of the space
empty (key)	Check whether the vector is empty
reserve (key)	Reserve space for data**
resize (key)	Convert the number of valid characters into n, and fill the extra space with data

• Use example:

void test_vector2()
{
	//size/capacity/empty/operator[]
	vector<int> v1;
	cout << v1.size() << endl;
	cout << v1.capacity() << endl;
	cout << v1.empty() << endl;
	vector<int> v2(5,2);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;
	cout << v2.empty() << endl;
	cout << v2[0] << endl;
	//reserve/resize
	v2.resize(8, 6);
	cout << v2.size() << endl;
	cout << v2.capacity() << endl;

	vector<int> foo1;
	int sz1 = foo1.capacity();
	cout << "making foo1 grow:\n";
	for (int i = 0; i < 100; ++i) {
		foo1.push_back(i);
		if (sz1 != foo1.capacity()) {
			sz1 = foo1.capacity();
			cout << "capacity changed: " << sz1 << '\n';
		}
	}
	vector<int> foo2;
	foo2.reserve(100);
	int sz2 = foo2.capacity();
	cout << "making foo2 grow:\n";
	for (int i = 0; i < 100; ++i) {
		foo2.push_back(i);
		if (sz2 != foo2.capacity()) {
			sz2 = foo2.capacity();
			cout << "capacity changed: " << sz2 << '\n';
		}
	}
}

• result:
  

• be careful:

1. When the capacity code is run in VS and g + + respectively, it will be found that the capacity is increased by 1.5 times in VS and 2 times in g + + (the specific increase is defined according to the specific requirements: vs is the PJ version STL and g + + is the SGI version STL)

2. Reserve is only responsible for opening up space. If you know how much space is needed, reserve can alleviate the cost defect of vector capacity expansion (if n is greater than the current capacity, the function will reallocate its storage space to N or greater)

3. resize initializes while opening space, affecting size:

   If n is less than the size() of the current container, the elements exceeding are deleted. If n is greater than the size() of the current container, insert enough elements at the end of the container to expand the contents of the container to make the size of the container reach n (if val is specified, initialize the new element to val)

3. vector object access and traversal

Function name	Function description
operator [] (key)	Return the character of pos position. Ordinary objects and const objects have corresponding versions
begin+ end	egin gets the iterator of the first character + end gets the iterator of the next position of the last character
rbegin + rend	begin gets the iterator of the first character + end gets the iterator of the next position of the last character
Range for	C++11 support, and finally replaced with iterators

• Use example:

void PrintVector(const vector<int>& v)
{
	// Const objects use const iterators for traversal printing
	vector<int>::const_iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}
void test_vector3()
{
	// Using push_back insert 4 data
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	// Traversal printing using iterators
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	// Modify using iterators
	it = v.begin();
	while (it != v.end())
	{
		*it *= 2;
		++it;
	}
	// Use the reverse iterator to traverse and then print
	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
	//const iterator print
	PrintVector(v);
	//Range for traversal
	for (const auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	//size+[]
	for (size_t i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}

• result:

4. vector object modification

vector addition, deletion, query and modification	Interface description
push_back (key)	Tail insertion
pop_back (key)	Tail deletion
find	Search (algorithm module implementation, not vector member interface)
insert	Insert val before position
erase	Delete data at position
swap	Exchange the data space of two vector s
operator [] (key)	Access like an array

• Use example:

void test_vector4()
{
	int a1[] = { 1, 2, 3, 4 };
	vector<int> v1(a1, a1 + sizeof(a1) / sizeof(int));
	vector<int>::iterator it1 = v1.begin();
	while (it1 != v1.end()) {
		cout << *it1 << " ";
		++it1;
	}
	cout << endl;
	v1.pop_back();
	v1.pop_back();
	it1 = v1.begin();
	while (it1 != v1.end()) {
		cout << *it1 << " ";
		++it1;
	}
	cout << endl;

	int a2[] = { 1, 2, 3, 4 };
	vector<int> v2(a2, a2 + sizeof(a2) / sizeof(int));
	// Use find to find the iterator where 3 is located
	vector<int>::iterator pos = find(v2.begin(), v2.end(), 3);
	// Insert 30 before pos position
	v2.insert(pos, 30);
	vector<int>::iterator it2 = v2.begin();
	while (it2 != v2.end()) {
		cout << *it2 << " ";
		++it2;
	}
	cout << endl;
	pos = find(v2.begin(), v2.end(), 3);
	// Delete pos location data
	v2.erase(pos);
	it2 = v2.begin();
	while (it2 != v2.end()) {
		cout << *it2 << " ";
		++it2;
	}
	cout << endl;

	int a3[] = { 1, 2, 3, 4 };
	vector<int> v3(a3, a3 + sizeof(a3) / sizeof(int));
	// Read and write position 0 through []
	v3[0] = 10;
	cout << v3[0] << endl;
	// Traverse the vector by [i]
	for (size_t i = 0; i < v3.size(); ++i)
		cout << v3[i] << " ";
		cout << endl;
	vector<int> swapv;
	swapv.swap(v3);
	cout << "v data:";
	for (size_t i = 0; i < v3.size(); ++i)
		cout << v3[i] << " ";
	cout << endl;
	cout << "swapv data:";
	for (size_t i = 0; i < swapv.size(); ++i)
		cout << swapv[i] << " ";
	cout << endl;
	// New range traversal supported by C++11
	for (auto x : v3)
		cout << x << " ";
	cout << endl;
}

• result:

5. vector iterator failure

• Concept:

1. The main function of the iterator is to enable the algorithm not to care about the underlying data structure. Its underlying layer is actually a pointer or encapsulates the pointer (for example, vector and string iterators are the original ecological pointer T *)

2. Therefore, the failure of the vector iterator actually means that the space pointed to by the corresponding pointer at the bottom of the iterator is destroyed, and a space that has been released is used, or the meaning pointed to by the iterator itself is changed, which is not what we think

• vector iterator failure operation:

1. 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

In essence: when the vector is expanded, the original dynamically opened space is released, but the iterator is not updated after the expansion. If it is used again, an error will be reported

• Example:

#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 run time.
	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 sufficient.
	*/
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}

• result:

1. Delete or insert the specified location element -- erase/insert

In essence: after deletion or insertion, the meaning of the original iterator is changed

• Example:

void testdemo1()
{
	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 position will cause the pos iterator to fail and the meaning of the point will change (the content of the pos position is 4, not 3)
	v.erase(pos);
	cout << *pos << endl; // This is an illegal access
	//Solution: pos = v.erase(pos)// Receive the return value, and pos points to the next element after deleting the element
}
void testdemo2()
{
	int a[] = { 1, 2, 3, 4 };
	vector<int> v(a, a + sizeof(a) / sizeof(int));
	vector<int>::iterator pos = find(v.begin(), v.end(), 3);
	v.insert(pos, 6);//After insertion, the pos iterator fails and the meaning of the point changes (the content of the pos position is 6, not 3)
	//Solution: pos=v.insert(pos, 6)// Receive the return value, and pos points to the inserted new element
	cout << *pos << endl;
}

• result:
  

• After resolution:
  

• Explanation:

1. After erase deletes the pos position element, the element after the pos position will move forward without changing the underlying space. However, if the meaning of the iterator is changed, vs considers the position iterator invalid (the same is true for the insert operation)

2. Solution to iterator failure: update the iterator before use

3, vector analysis and simulation

1. vector framework and common interface display

• Basic framework:

• Display of common interfaces:

template<class T>
class vector
{
public:
    // The iterator for Vector is a native pointer
    typedef T* iterator;
    typedef const T* const_iterator;
    //Ordinary iterators and const iterators
    iterator begin();
    iterator end();
    const_iterator begin()const;
    const_iterator end()const;
    //non-parameter constructor 
    vector();
    //n value constructors
    vector(int n, const T& value = T());
    //Iterator construction
    template<class InputIterator>
    vector(InputIterator first, InputIterator last);
    //copy construction 
    vector(const vector<T>& v);
    //Assignment overload
    vector<T>& operator= (vector<T> v);
    //Deconstruction
    ~vector();

    // capacity
    size_t size() const;
    size_t capacity() const;
    bool empty() const;
    //Open space
    void reserve(size_t n);
    //Open space + initialization
    void resize(size_t n, const T& value = T());
    //Subscript overload
    T& operator[](size_t pos);
    const T& operator[](size_t pos)const;
    //Tail insertion
    void push_back(const T& x);
    //Tail deletion
    void pop_back();
    //exchange
    void swap(vector<T>& v);
    //Insert and delete
    iterator insert(iterator pos, const T& x);
    iterator erase(iterator pos);

private:
    iterator _start; // Point to the beginning of the data block
    iterator _finish; // Tail pointing to valid data
    iterator _endOfStorage; // Tail pointing to storage capacity
};

2. Specific details of common interfaces for vector simulation

Note: in order to avoid naming conflicts with the vector provided by C + +, we choose to implement it in the namespace

• Implementation code:

namespace cole
{
    template<class T>
    class vector
    {
    public:
        //The bottom layer is a continuous space, and the native pointer is enough to complete the iterator operation
        typedef T* iterator;
        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;
        }
        //Empty vector
        vector()
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {}

        vector(int n, const T& value = T())
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            //Be sure to initialize (if it is not initialized, the member variable is a random value, and there will be problems in calling the relevant interface, resulting in problems in reserve)
            reserve(n);
            for (int i = 0; i < n; i++)
            {
                //Assign a value to a built-in type, and call its copy overloaded function (such as string) for a custom type
                _start[i] = value;
            }
            _finish = _start + n;
        }
        //Template functions can exist in template classes
        template<class InputIterator>
        vector(InputIterator first, InputIterator last)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            //Multiplex interface
            reserve(last - first);
            while (first != last)
            {
                push_back(*first);
                first++;
            }
        }
        vector(const vector<T>& v)
            :_start(nullptr)
            , _finish(nullptr)
            , _endOfStorage(nullptr)
        {
            reserve(v.capacity());
            for (size_t i = 0; i < v.size(); i++)
            {
                //Assign a value to a built-in type, and call its copy overloaded function (such as string) for a custom type
                _start[i] = v._start[i];
            }
            _finish = _start + v.size();
        }
        //Modern writing
        vector<T>& operator= (vector<T> v)
        {
            swap(v);
            return *this;
        }
        ~vector()
        {
            //Free up space and empty
            if (_start)
            {
                delete[] _start;
            }
            _start = _finish = _endOfStorage = nullptr;
        }
        // capacity
        size_t size() const
        {
            return _finish - _start;
        }
        size_t capacity() const
        {
            return _endOfStorage - _start;
        }
        bool empty() const
        {
            return _start == _finish;
        }
        void reserve(size_t n)
        {
            if (n > capacity())
            {
                //The expansion will reopen the space, causing the member variable to be nullptr. The necessary data will be recorded here
                size_t sz = size();
                iterator tmp = new T[n];
                if (_start)
                {
                    for (size_t i = 0; i < sz; i++)
                    {
                        //Assign a value to a built-in type, and call its copy overloaded function (such as string) for a custom type
                        tmp[i] = _start[i];
                    }
                    delete[] _start;
                }
                _start = tmp;
                _finish = _start + sz;
                _endOfStorage = _start + n;
            }
        }
        void resize(size_t n, const T& value = T())
        {
            //Case by case operation
            if (n < size())
            {
                _finish = _start + n;
            }
            else
            {
                if (n > capacity())
                {
                    reserve(n);
                }
                while (_finish != _start + n)
                {
                    *_finish = value;
                    ++_finish;
                }
            }
        }
        T& operator[](size_t pos)
        {
            //Rationality of pos
            assert(pos < size());
            return _start[pos];
        }
        const T& operator[](size_t pos)const
        {
            //Rationality of pos
            assert(pos < size());
            return _start[pos];
        }

        void push_back(const T& x)
        {
            //When the vector is full
            if (_finish == _endOfStorage)
            {
                reserve(capacity() == 0 ? 4 : capacity() * 2);
            }
            *_finish = x;
            _finish++;
        }
        void pop_back()
        {
            //Rationality of pos
            assert(size() > 0);
            _finish--;
        }
        //The swap provided in the algorithm involves multiple deep copies. It is implemented here, and the efficiency of variable exchange is high
        void swap(vector<T>& v)
        {
            ::swap(_start, v._start);
            ::swap(_finish, v._finish);
            ::swap(_endOfStorage, v._endOfStorage);
        }
        iterator insert(iterator pos, const T& x)
        {
            if (_finish == _endOfStorage)
            {
                //The expansion will reopen the space, and the necessary data will be recorded here
                size_t len = pos - _start;
                reserve(capacity() == 0 ? 4 : capacity() * 2);
                //After capacity expansion, the pos will fail. Update the pos location
                pos = _start + len;
            }
            iterator end = _finish;
            while (end != pos)
            {
                *end = *(end - 1);
                end--;
            }
            *pos = x;
            _finish++;
            return pos - 1;
        }
        iterator erase(iterator pos)
        {
            iterator cur = pos + 1;
            while (cur != _finish)
            {
                *(cur - 1) = *cur;
                ++cur;
            }
            --_finish;
            return pos;
        }
    private:
        iterator _start; // Point to the beginning of the data block
        iterator _finish; // Tail pointing to valid data
        iterator _endOfStorage; // Tail pointing to storage capacity
    };
}

3. Copy problems using memcpy

Assuming that memcpy is used for copying in the reserve interface in the vector implemented by the simulation, what will happen to the following code?

int main()
{
	cole::vector<cole::string> v;
	v.push_back("1111");
	v.push_back("2222");
	v.push_back("3333");
	return 0;
}

• Problem analysis:

  1. memcpy is a binary format copy of memory, which copies the contents of one memory space to another memory space intact

  2. If you copy a user-defined element, memcpy is efficient and will not make an error. However, if you copy a user-defined element and resource management is involved in the user-defined element, an error will occur, because the copy of memcpy is actually a shallow copy

Conclusion: if resource management is involved in objects, memcpy must not be used for copying between objects, because memcpy is a shallow copy, otherwise it may cause memory leakage and even program crash

4. Dynamic two-dimensional array understanding

• Example:

// Take the first n behavior of Yang Hui triangle as an example: suppose n is 5
void test5(size_t n)
{
	// Use vector to define the two-dimensional array vv. Each element in VV is vector < int >
	cole::vector<cole::vector<int>> vv(n);
	// Set all the elements in vecotr < int > in each row of the two-dimensional array to 1
	for (size_t i = 0; i < n; ++i)
		vv[i].resize(i + 1, 1);
	// Assign values to all elements of the first column and diagonal of Yang Hui's triangle
	for (int i = 2; i < n; ++i)
	{
		for (int j = 1; j < i; ++j)
		{
			vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
		}
	}
}

cole::vector<cole::vector<int>> vv(n); 

• Construct a VV dynamic two-dimensional array. There are a total of n elements in vv. Each element is of vector type, and each line does not contain any elements. If n is 5, it is as follows:

• After the element filling in vv is completed, as shown in the following figure: