Table of contents
Insert an element at a certain position insert()
overview
The underlying principle of the vector container is actually a sequence table, which encapsulates a pointer (pointing to the open array) and two (array related parameters, the number of array elements and the size of the open space) into a class as attributes of the class. Then realize the function of the vector container by defining various interface functions as member functions.
Note: The article draws on the following blog, thank you for sharing, let me learn more knowledge, hold hands together https://blog.csdn.net/weixin_50941083/article/details/122354948
vector class definition
The vector container is actually a class template, which allows the container to store various types of elements. The definition of the vector class is as follows, including attributes, member functions, and operator overloading. MyVector.h file.
#pragma once #include<iostream> #include<algorithm> #include<numeric> using namespace std; #define InitCapacity 8 //Create vector class template template<typename T> class vector { public: typedef T dataType;//rename the type typedef T* iterator;//The meaning of iterator in vector public: dataType* _data;//The vector attribute stores data space int _size;//Amount of stored data int _capacity;//The size of the allocated space public: vector();//no-argument constructor initialization vector(const vector& vec);//copy constructor vector& operator=(const vector& vec)//assignment operator overloading { //Release original space Deep copy delete[] this->_data; //copy over this->_capacity = vec._capacity; this->_data = new dataType[this->_capacity]; for (int i = 0; i < vec._size; i++) { this->_data[i] = vec._data[i]; } this->_size = vec._size; return *this; } bool operator==(const vector& vec)//Equals relational operator overloading { if (this->_size != vec._size) return false; for (int i = 0; i < vec._size; i++) { if (this->_data[i] != vec._data[i]) return false; } return true; } dataType& operator[](size_t i)//[] operator overloading { return this->_data[i]; } void check_capacity();//check capacity void push_back(dataType val);//Insert an element val at the end void insert(iterator pos, dataType val);//Insert element val at a certain position void pop_back();//tail delete void erase(iterator pos);//delete a positional element dataType front();//Get the header element dataType back();//Get the tail element iterator begin();//head pointer iterator end();//tail pointer int size();//number of elements int capacity();//Capacity bool empty();//Is it empty ~vector();//destructor release };
constructor and destructor
The constructor and destructor are the first thing to be defined when creating a class. The constructor is mainly used to initialize member variables when creating an object; the destructor is mainly used to release the space allocated for the instantiated object. When an object leaves itself The destructor will be called automatically when the scope of the object is set to release the space.
template<typename T>//The out-of-class implementation of a class template member function must be marked with a template vector<T>::vector() { this->_data = NULL; this->_size = 0; this->_capacity = 0; } template<typename T> //copy constructor vector<T>::vector(const vector& vec) { this->_capacity = vec._capacity; this->_data = new dataType[this->_capacity]; for (int i = 0; i < vec._size; i++) { this->_data[i] = vec._data[i]; } this->_size = vec._size; } template<typename T>//And each member function must be marked with a template, and the .cpp file must be included when using it vector<T>::~vector() { delete[] this->_data; this->_data = NULL; this->_capacity = 0; this->_size = 0; }
Tail plug push_back()
When inserting elements, it is necessary to judge whether the size of the opened space is sufficient, thus creating the check_capacity() function:
template<typename T> void vector<T>::check_capacity() {//check capacity if (0 == this->_capacity) {//initial this->_capacity = InitCapacity; this->_data = new dataType[this->_capacity]; return; } if (this->_size == this->_capacity) {//already filled this->_capacity *= 2; dataType* tmp = new dataType[this->_capacity];//Create a temporary space to store previous data for (int i = 0; i < this->_size; i++) { tmp[i] = this->_data[i]; } delete[] this->_data;//free up the original space this->_data = tmp;//Now point to the newly created space } } template<typename T> void vector<T>::push_back(dataType val)//Inserting an element val at the end needs to judge the capacity { this->check_capacity();//Judgment capacity this->_data[this->_size] = val; this->_size++; }
Insert an element at a certain position insert()
To insert an element at a certain position, the principle is as follows:
template<typename T> void vector<T>::insert(iterator pos, dataType val)//Insert element val at a certain position { this->check_capacity();//Judgment capacity int index = pos - this->_data; for (int i = this->_size - 1; i >= index; i--) { this->_data[i + 1] = this->_data[i]; } this->_data[index] = val; this->_size++; }
other member functions
template<typename T> void vector<T>::pop_back()//tail delete { this->_size--; } template<typename T> void vector<T>::erase(iterator pos)//delete a positional element { int index = pos - this->_data; for (int i = index; i < this->_size - 1; i++) { this->_data[i] = this->_data[i + 1]; } this->_size--; } template<typename T> T vector<T>::front()//Get the header element { return this->_data[0]; } template<typename T> T vector<T>::back()//Get the tail element { return this->_data[this->_size - 1]; } template<typename T> T* vector<T>::begin()//head pointer { return this->_data; } template<typename T> T* vector<T>::end()//tail pointer { return this->_data + this->_size; } template<typename T> int vector<T>::size()//number of elements { return this->_size; } template<typename T> int vector<T>::capacity()//Capacity { return this->_capacity; } template<typename T> bool vector<T>::empty()//Is it empty { return this->_size == 0; }
Test code test.cpp
#include"MyVector.h" #include"MyVector.cpp" int main() { vector<string> vec;//No parameter construction vec.push_back(string("xiaoming"));//tail plug vec.push_back(string("xiojun")); vec.push_back(string("xiaomei")); vec.push_back(string("xiaoxin")); vector<string> vec1(vec);//copy construction if (vec == vec1) {//Overloading the == operator cout << "vec vec1 two sequence tables are equal" << endl; } vector<string> vec2 = vec;//overloaded = operator if (vec1 == vec2) { cout << "vec1 vec2 two sequence tables are equal" << endl; } cout << "element is vec[1] = " << vec[1] << endl;//Overloading the [] operator vec.insert(vec._data, string("xiaofang"));//Insert at a certain position, iterator pass parameter vec.pop_back();//tail delete vec.pop_back(); vec.erase(vec._data);//delete element cout << "The first element is:" << vec.front() << endl; vec.push_back(string("xiaocao")); vec.push_back(string("xiaotang")); cout << "The last element is:" << vec.back() << endl; cout << "The number of elements is:" << vec.size() << endl; cout << "The space capacity is:" << vec.capacity() << endl; cout << "Is it empty:" << vec.empty() << endl; cout << "traverse the entire sequence table************************" << endl; for (vector<string>::iterator it = vec.begin(); it != vec.end(); it++) { cout << *it << " "; } cout << endl; return 0; }
Summarize
The article describes the process of implementing vector containers through C++. During this process, the understanding of C++ classes and object characteristics has been deepened; the realization principle of standard class templates has been understood; knowledge of related data structures, memory allocation and release, etc. has also been used. A simple and meaningful experiment.