Use and implementation of standard library vector

The problem of overrun and overflow will occur in ordinary arrays. It will be more convenient to use vector provided by C + + standard library. In addition, vector can be used to store graph in adjacency table. This method is suitable for the situation that there are too many nodes and it is not suitable for adjacency matrix, but it is difficult to use pointer to realize adjacency table.
Before using vector, you need to add the vector header file, that is, include < vector >. At the same time, you can add the vector namespace using std::vector or directly add the entire namespace to using namespace std, avoiding adding the std:: prefix every time.

#include <vector>
using namespace std;	// using std::vector

Define and initialize vector objects

vector<typename> type;		// Define vector object

vector<int> v;				// Default initialization
vector<int> v = {1,2,3};	// List initialization, equivalent to int v[3]={1,2,3}
vector<int> v(10´╝înum)		// Initialize to 10 num, num=0 by default
vector<int> v1(v);			// Copy initialization, which requires the same element type of v1 and v

vector element access

1. Access elements

When you access the vector element, you can use subscripts like v[index] or v.at(index) when you access an array. The subscripts range from 0 to v.size(). In addition, you can use the library functions v.front() and v.back() to access the head and tail elements of the vector.

2. Iterator access

Although subscripts can be used to access elements, not all containers define subscripts, which can be accessed using STL defined iterators.

// Iterator type and its acquisition       
vector<int>::const_iterator it; 	// Read only iterator
it = c.cbegin()/c.cend()-1 			// const_iterator gets the first and last elements

vector<int>::iterator it;           // Read write iterator
it = c.begin()/c.end()-1    		// iterator gets the first and last elements

vector operation

1. Object assignment
vector<int> v1, v2(10,1);	
vector<char> v3 = {'a'};

v1 = v2;								// Assignment should be of the same type
swap(v1,v2);       				  		// Swap assignment should be of the same type, equivalent to v1.swap(v2)
v1.assign(v3.cbegin(), v3.cend());		// assign assignment. The two types of assignment can be different by using iterator
2. Insert element

Vector allows you to append the element push back (T) at the end or append the element replace back (T) without calling the copy constructor. In addition, vector implements the insert() function of the sequence table structure, which can be called directly.

c.push_back(t)              // Tail inserts an element with a value of t
c.emplace_back(t)			// Insert an element with a value of t at the end (high efficiency)
c.insert(p,t)               // The iterator p points to the element and inserts the element with the value t before it
3. Delete element

Corresponding to the insertion, vector can delete the individual elements at the tail with pop back(). To delete the specified element or the specified range available erase(), clear() can be used to further clear all elements.

c.pop_back(t)               // Delete tail element in c
c.erase(p)                  // Delete the element referred to by iterator p
c.erase(b,e)                // Delete elements in the scope of iterators b and e
c.clear()                   // Delete all elements in c

vector implementation

#ifndef VECTOR_H
#define VECTOR_H

template <typename T>
class Vector {
	private:
		int theSize;				// Vector current length 
		int theCapactiy;			// Vector maximum length 
		Object *objects;			// Vector instance 
	
	public:
		Vector( int initSize = 0);												// Constructor 
		: theSize( initSize ), theCapacity( initSize + SPARE_CAPACITY ) {
			objects = new Object[theCapacity];
		}
		
		Vector( const Vector & rhs ) : objects( NULL ) {						// copy constructor  
			operator=( rhs );
		}
		
		~Vector( ) {															// Destructor 
			delete [] objects;
		}
	
	public:	
		const Vector & operator= ( const Vector & rhs ) {						// Object Assignment 
			if ( this != &rhs ) {
				delete [] objects;
				theSize = rhs.size();
				theCapacity = rhs.theCapacity;
				
				objects = new Object[capacity()];
				for (int k = 0; k < size(); k++)
					objects[k] = rhs.objects[k];
			}
			return *this;
		}
		
		Object & operator[] (int index) {										//  Get objects 
			return objects[index];
		}		
		const Object & operaotr[] (int index) const {							//	Get constant object 
			return objects[index];
		}
		
		void resize(int newSize);												// Change vector size 
		void reserve(int newCapacity);											// Keep the original vector content 
		bool empty() const;														// Empty vector 
		int size() const;														// The actual size of the vector 
		int capacity() const;													// Maximum capacity of vector 
		void push_back(const Object & x);										// Append element to tail of vector 
		void pop_back();														// Delete vector tail element 
		const Object & back() const;											// Member function reads tail element of vector 
		
		typedef Object * iterator;							// iterator 
		typedef const Object & const_iterator;				// Constant iterator 
		
		iterator begin();									// Iterator gets the first element 
		const_iterator begin() const;						// Iterator reads first element 
		iterator end();										// Iterator getting tail element 
		const_iterator end() const;							// Iterator reads tail element 
		enum { SPARE_CAPACITY = 16 };
};

template <class Object>
void Vector<Object>::resize(int newSize) {
	if (newSize > theCapacit)
		reserve(newSize * 2 + 1);
	theSize = newSize;
}

template <class Object>
void Vector<Object>::reserve(int newCapacity) {		// Keep the original vector content 
	if (newCapacity < theSize)
		return;
	
	Object *oldArray = objects;				 
	objects = new Object[newCapacity];
	for (int k = 0; k < theSize; k++)
		objects[k] = oldArray[k];
	theCapacity = newCapacity;
	
	delete [] oldArray;
}

template <class Object>
bool Vector<Object>::empty() const {
	return size() == 0;
}

template <class Object>
int Vector<Object>::size() const {
	return theSize;
}

template <class Object>
int Vector<Object>::capacity() const {
	return theCapacity;
} 

template <class Object>
void Vector<Object>::push_back(const Object & x) {
	if (theSize == theCapacity)
		reserve(2 * theCapacity + 1);
	objects[theSize++] = x; 
}

template <class Object>
void Vector<Object>::pop_back() {
	theSize--;
}

template <class Object>
const Object& Vector<Object>::back() const {
	return objects[theSize - 1];
}

template <class Object>
iterator Vector<Object>::begin() {
	return &objects[0];
} 

template <class Object>
const_iterator Vector<Object>::begin() {
	return &objects[0];
} 

template <class Object>
iterator Vector<Object>::end() {
	return &objects[size()];
}

template <class Object>
const_iterator Vector<Object>::end() {
	return &objects[size()];
}

#endif
6 original articles published, 3 praised, 226 visited
Private letter follow

Added by Neomech on Sat, 08 Feb 2020 14:24:02 +0200