Vector introduction and underlying principle

Catalog

1. Introduce

2. Simulation Implementation

2.1. Basic framework

2.2. Simple function implementation

2.3. Implementation of capacity expansion function

2.4 Insert delete function implementation  

2.5 Constructors, etc  

2.6 The problem of iterator failure

---

1. Introduce

1. vector Is a sequence container that represents a variable size array .

2. It's like an array ,vector It also uses continuous storage space to store elements . That means subscript pairs can be used                 vecto Element to access , As efficient as arrays . But it's not like an array , Its size can be changed dynamically , and           And its size will be automatically processed by the container

Function has ：

 

give an example ：

void test_vector1()
{
	vector<int> v;
	v.push_back(7);
	v.push_back(3);
	v.push_back(5);
	v.push_back(9);
	v.push_back(2);
	for (auto& ch : v)
	{
		ch += 1;
		cout << ch << " ";
	}
	cout << endl;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		(*it) -= 1;
		cout << *it << " ";
		it++;
	}
	cout << endl;

	sort(v.begin(), v. end());
	for (auto ch : v)
	{
		cout << ch << " ";
	}
	cout << endl;
}

 result ：

8 4 6 10 3
7 3 5 9 2
2 3 5 7 9

int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);

	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.insert(it, 20);//insert The address of the next element after the newly inserted element is returned 
			it++;
		}
		it++;
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

 result ：
1 20 2 3 20 4 5 20 6

Usage and string similar , You can view the document ：vector - C++ Reference  To study .

2. Simulation Implementation

2.1. Basic framework

namespace LF
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		vector()// Parameter free constructor 
			:_start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{}


		//........ Implementation of other functions 

	private:
		iterator _start;//T Pointer to type , Point to the starting position of the memory space 
		iterator _finish;// Point to the location of valid data 
		iterator _endofstoage;// Point to the end of the memory 
	};
}

2.2. Simple function implementation

        iterator begin()// Return the address of the starting space 
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		size_t size() const// Returns the number of elements 
		{
			return _finish - _start;
		}

		size_t capacity() const// Returns the size of the capacity 
		{
			return _endofstoage - _start;
		}
        T& operator[](size_t pos)
		{
			assert(pos < size());

			return _start[pos];
		}

		const T& operator[](size_t pos) const
		{
			assert(pos < size());

			return _start[pos];
		}

        void clear()
		{
			_finish = _start;
		}

2.3. Implementation of capacity expansion function

       void reserve(size_t n)
		{
			size_t sz = size();
			if (n > capacity())
			{
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, size()*sizeof(T));

                     for (size_t i = 0; i < size(); ++i)
					{
						tmp[i] = _start[i];// if —_start[i] yes vector type , There's a pointer in it , To complete a deep copy 
					}
					delete[] _start;
				}
		
				_start = tmp;//_start The space pointed to has changed 
			}

			_finish = _start + sz;// After expansion —_start Changed the ,—_finish Should be in the new _start Back 
			_endofstoage = _start + n;
		}

		void resize(size_t n, T val = T())//T() Will call its default constructor , stay C++ in , Built in types also have default constructors 
		{
			if (n > capacity())
			{
				reserve(n);
			}

			if (n > size())
			{
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}

2.4 Insert delete function implementation  

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

			*_finish = x;
			++_finish;
		}

		void pop_back()
		{
			if (_finish > _start)
			{
				--_finish;
			}
		}

       iterator insert(iterator pos , const T&)// here pos Value passing is accepted 
		{
			assert(pos >= _start && pos <= _finish);
			size_t sz = pos - _start;
			if (_finish == _endofstoage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 4;
				reverse(newcapacity);
				pos = _start + sz;// After expansion ,pos The memory space pointed to is also invalid , To reassign 
			}
			// 2  4  6  7 
			iterator end = _finish - 1;
			while (end>=pos)
			{
			
				*(end + 1) = *end;
				end--;
			}
			*pos = x;
			++_finish;

			return pos;// Back to pos The pointer points to the new element 
		}

        iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
			return pos;
		}

2.5 Constructors, etc  

        template <class InputIterator>
		vector(InputIterator first, InputIterator last)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		vector(size_t n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (size_t i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

		vector(int n, const T& val = T())
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}

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

	
		vector(const vector<T>& v)
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstoage(nullptr)
		{
			vector<T> tmp(v.begin(), v.end());// Construct a temporary object , Open up new space , Content and v identical 
			swap(tmp);// take *this And tmp Three pointers in exchange .
		}


		vector<T>& operator=(vector<T> v)// Value passed 
		{
			swap(v);
			return *this;
		}

2.6 The problem of iterator failure

        iterator insert(iterator pos , const T&)// here pos Value passing is accepted 
		{
			assert(pos >= _start && pos <= _finish);
			size_t sz = pos - _start;
			if (_finish == _endofstoage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 4;
				reverse(newcapacity);
				pos = _start + sz;// After expansion ,pos The memory space pointed to is also invalid , To reassign 
			}
			// 2  4  6  7 
			iterator end = _finish - 1;
			while (end>=pos)
			{
			
				*(end + 1) = *end;
				end--;
			}
			*pos = x;
			++_finish;

			return pos;// Back to pos It points to new elements 
		}

The implementation in the library is similar to the above principle , Every time a new element is inserted , The address of the new element is returned .

If you do not accept the return value of this function ：

1. If there is no expansion , At this time pos The pointer points to the newly inserted data .

2. In case of capacity expansion , Because in this function pos It's worth passing on , Even if it changes inside the function pos, When the return value is not accepted , The pos The memory space pointed to has expired .

stay vs2022 Next presentation ：

int main()
{
	vector<int> v;
	v.reserve(10);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(5);
	v.push_back(6);
	auto pos = find(v.begin(), v.end(), 5);
	if (pos!=v.end())
	{
		cout << "capacity:"<<v.capacity() << "size:"<<v.size() << endl;
		v.insert(pos, 100);
		/*pos = 9999;*/
	}
	cout << *pos << endl;
	return 0;
}

Without capacity expansion ,pos The space pointed to does not change , But the data changed , stay vs2022 Access is not available on the platform （vs2014 You can visit ）;

  In the case of capacity expansion ,pos The space pointed to has expired .vextor<int> A new space has been reopened .

        iterator erase(iterator pos)
		{
			assert(pos >= _start && pos < _finish);
			iterator it = pos + 1;
			while (it != _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
			return pos;// Back to pos The data pointed to is the next element of the deleted element 
		}

because erase When the function deletes data , No reduction in capacity , There will be no wild pointer problem , but pos The meaning of the data pointed to has changed （ And insert The second case is the same ）.vs2022 Not accessible under , It can be considered invalid .

  The inspection mechanism is different under different platforms , There may be different results ,

summary ： In the use of insert,erase Function time , It's best to accept its return value .