C++ implements a simple vector container

Table of contents

overview

vector class definition

constructor and destructor

Tail plug push_back()

Insert an element at a certain position insert()

other member functions

Test code test.cpp

Summarize

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.

Tags: C++ data structure

Posted by maxx99 on Thu, 16 Mar 2023 09:48:42 +0530