C++: vector

目录

1.vector的介绍

2.vector常用的接口?

1.vector构造

2.迭代器iterator的使用

3.vector空间增长

?4.vector的增删改查

3.vector模拟实现

如果在reverse时使用memcpy会怎么样？

1.vector的介绍

C++中的vector是一个动态数组容器，可以存储任意类型的数据。它提供了动态大小的数组功能，可以在运行时动态地增加或减少其大小。vector是C++标准模板库（STL）中的一部分，因此可以使用标准库中提供的许多函数和算法来操作它。

1. vector 是表示可变大小数组的序列容器。

2. 就像数组一样， vector 也采用的连续存储空间来存储元素。也就是意味着可以采用下标对 vector 的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。

3. vector 分配空间策略： vector 会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存 储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是 对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。

4. 与其它动态序列容器相比（ deque, list and forward_list ）， vector 在访问元素的时候更加高效，在末 尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率比较低。

2.vector常用的接口?

1.vector构造

1.vector();无参构造函数

2.vector(size_type n,const value_type&val=value_type());

构造一个包含 n 个元素的容器。每个元素都是 val?

3.vector(const vector&x); 拷贝构造。

4.vector(InputIterator first,InputIterator last);

用迭代器进行初始化构造? ? ? ? ? ??

2.迭代器iterator的使用

1.iterator begin();

返回指向vector中第一个元素的迭代器。

2.iterator end();

返回指向vector中最后一个元素下一个位置的迭代器。

3.reverse_iterator rbegin()

返回指向vector中最后一个元素位置的reverse_iterator

4.reverse_iterator end()

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?返回指向vector中第一个元素的前一个位置位置的reverse_iterator

3.vector空间增长

1.size_type size();

返回数据个数

2.size_type capacity();?

返回容量大小

3.bool empty();

判断是否为空

4.resize函数

如果 n 小于当前容器大小，则内容将减少到其前 n 个元素，删除超出的元素（并销毁它们）。

如果 n 大于当前容器大小，则通过在末尾插入任意数量的元素来扩展内容，以达到 n 的大小。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将初始化值。

如果 n 也大于当前容器容量，则会自动重新分配分配的存储空间。

5.reverse函数

请求vector容量至少足以包含 n 个元素。

如果 n 大于当前向量容量，则该函数会导致容器重新分配其存储，从而将其容量增加到 n（或更大）。

在所有其他情况下，函数调用不会导致vector容量不受影响。

capacity 的代码在 vs 和 g++ 下分别运行会发现， vs 下 capacity 是按 1.5 倍增长的， g++ 是按 2 倍增长的 。

reserve 只负责开辟空间，如果确定知道需要用多少空间， reserve 可以缓解 vector增容的代价缺陷问题。

resize 在开空间的同时还会进行初始化，影响 size。

?4.vector的增删改查

?1.push_back();尾插

2.pop_back();尾删

3.find();查找

find是算法模块实现，不是vector的成员接口

template<class InputIterator, class T>
  InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

4.insert();插入

通过在指定位置的元素之前插入新元素来扩展vector，从而有效地通过插入的元素数增加容器大小。

当且仅当新的vector大小超过当前vector容量时，这会导致自动重新分配分配的存储空间。

由于vector使用数组作为其基础存储，因此在vector以外的位置插入元素会导致容器将位置之后的所有元素重新定位到其新位置。与其他类型的序列容器（如列表或forward_list）对相同操作执行的操作相比，这通常是一种低效的操作。

5.erase();删除

从向量中删除单个元素?或一系列元素

由于vector使用数组作为其基础存储，因此擦除vector以外的位置的元素会导致容器在擦除段后将所有元素重新定位到其新位置。与其他类型的序列容器对相同操作执行的操作相比，这通常是一种低效的操作?

6.swap();交换

通过 x 的内容交换容器的内容，x 是另一个相同类型的vector对象。尺寸可能有所不同。

调用此成员函数后，此容器中的元素是调用之前位于 x 中的元素，x 的元素是位于 this 中的元素。所有迭代器、引用和指针对交换的对象仍然有效。

3.vector模拟实现

#pragma once
#include<assert.h>


namespace wjc
{
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;


		vector()
			: _start(nullptr)
			, _finish(nullptr)
			, _endofstorage(nullptr)
		{
		}
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			for (const auto& e : v)
			{
				push_back(e);
			}
		}
		iterator begin()
		{
			return _start;
		}


		iterator end()
		{
			return _finish;
		}
		const_iterator begin() const
		{
			return _start;
		}


		const_iterator end() const
		{
			return _finish;
		}
		size_t capacity()const
		{
			return _endofstorage - _start;
		}
		size_t size()const
		{
			return  _finish - _start;
		}


		void push_back(const T& a)
		{
			if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 4 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = a;
			_finish++;
		}


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


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


		~vector()
		{
			if (_start)
			{
				delete[] _start;
				_start = _finish = _endofstorage = nullptr;
			}


		}
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];
				if (_start)
				{
					/*memcpy(tmp, _start, sizeof(T) * oldsize);*/
					for (size_t i = 0; i < oldsize; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}
		void resize(size_t n, T val = T())
		{
			if (n > size())
			{
				reserve(n);
				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
			else
			{
				_finish = _start + n;
			}
		}




		void pop_back()
		{
			assert(size() > 0);
			--_finish;
		}
		void insert(iterator pos, T x)
		{
			assert(pos <= _finish);
			assert(pos >= _start);
			size_t len = pos - _start;
			if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);//pos ?Ч
				//posλ
				pos = _start + len;
			}
			memmove(pos + 1, pos, (_finish - pos) * sizeof(T));
			*pos = x;
			++_finish;
		}


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


		T& operator[](size_t pos)
		{
			assert(pos, size());
			return _start[pos];
		}
		const T& operator[](size_t pos)const
		{
			assert(pos, size());
			return _start[pos];
		}
		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
	private:


		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};


}

如果在reverse时使用memcpy会怎么样？

1. memcpy 是内存的二进制格式拷贝，将一段内存空间中内容原封不动的拷贝到另外一段内存空间中

2. 如果拷贝的是自定义类型的元素， memcpy 既高效又不会出错，但如果拷贝的是自定义类型元素，并且自定义类型元素中涉及到资源管理时，就会出错，因为memcpy 的拷贝实际是浅拷贝。

#include"vector.h"
int main()
{
	wjc::vector<string> v;
 	v.push_back("1111");
	v.push_back("2222");
	v.push_back("3333");
	v.push_back("4444");
	v.push_back("5555");
 	return 0;
}

运行这段代码会出现问题，因为插入4个元素后需要扩容，但是memcpy只是将一段内存空间中内容原封不动的拷贝到另外一段内存空间中，_start指向的空间已经释放了，也就是野指针，但是直到插入第5个元素_start依旧指向原来的空间，vector释放空间会导致同一片空间释放两次。

所以如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。最好开辟新空间来拷贝，如下面的方法：

void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t oldsize = size();
				T* tmp = new T[n];
				if (_start)
				{
					/*memcpy(tmp, _start, sizeof(T) * oldsize);*/
					for (size_t i = 0; i < oldsize; i++)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = _start + oldsize;
				_endofstorage = _start + n;
			}
		}