C++ vector的使用及模拟实现

1.vector的使用

1.1默认成员函数

构造函数

（1）默认构造函数：创建一个空vector；

（2）填充构造函数：创建一个包含 n 个值为 val 元素的vector，不给第二个参数，会初始化为默认值，例如vector<int>初始化为0；

（3）范围构造函数：使用一段迭代器区间初始化，可以是vector的迭代器，也可以是其他容器的迭代器

	string str("hello world");
	vector<char> vc(str.begin() + 6, str.end());
	for (auto& e : vc)
	{
		cout << e << " ";
	}
	cout << endl;//w o r l d

（4） 复制构造函数：第一种形式通过复制另一个 vector x 来创建新的 vector；第二种形式在指定分配器的情况下复制另一个 vector x 。

	vector<int> vi{ 1,2,3 };
	vector<int> vi2(vi);
	for (auto& e : vi2)
	{
		cout << e << " ";
	}
	cout << endl;//1 2 3

（5） 移动构造函数：第一种形式通过移动另一个 vector x 来创建新的 vector，将 x 的资源（如底层数组）直接转移到新 vector ，x 变为有效但未指定状态；第二种形式在指定分配器的情况下进行移动构造。

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = std::move(v1); // 移动v1创建v2
    for (int i : v2) {
        std::cout << i << " ";
    }
    return 0;
}

（6）初始化列表构造函数：使用初始化列表 il 中的元素来初始化 vector 。

赋值重载

（1）复制赋值：将 vector 对象 x 的内容复制到当前 vector 中。它会先释放当前 vector 已有的内存空间（如果有），然后分配新的内存，再把 x 中的元素逐个复制过来。这是深拷贝操作，两个 vector 对象有各自独立的内存存储元素。

（2）移动赋值：将 vector 对象 x 的资源（如底层数组指针等）移动到当前 vector 中。x 会变为有效但未指定状态（通常其内部数据指针被置空等）。此操作是浅拷贝，不进行元素逐个复制，而是直接转移资源所有权，效率较高，适用于 x 不再需要的场景。

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2;
    v2 = std::move(v1); // 移动赋值，v2获取v1资源，v1变为有效但未指定状态
    for (int i : v2) {
        std::cout << i << " ";
    }
    return 0;
}

（3）初始化列表赋值：使用初始化列表 il 中的元素来重新初始化当前 vector 。它会先释放当前 vector 已有的内存，然后根据初始化列表中的元素个数分配内存，并将元素逐个复制（或移动，取决于元素类型）到当前 vector 中。

1.2迭代器

1.begin()/end():和string的迭代器类似，在 C++ 标准库中，std::vector 的迭代器通常是通过指针实现的，但这并不是标准强制要求的，而是一种常见的优化实现方式。

2.rbegin()/rend():反向迭代器，都包含const和非const。

3.cbegin()/cend():const类型的迭代器，只是把之前的const迭代器单拿出来而已。

4.crbegin()/crend():const类型的反向迭代器。

1.3容量函数

1.size():

返回vector容器中的数据个数。

2.resize()

	vector<int> v{ 1,2,3 };
	v.resize(5);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.resize(10, 2);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	v.resize(2, 1);
	for (auto& e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "容量" << endl;
	cout << v.capacity() << endl;

、

• 扩容：当n大于当前容量时编译器会扩容到所需大小，当n小于当前容量时只会把size变小，而不会缩容。
• 补充：当传入一个val，并且发生扩容时多出来的容量会存入val，如果没有显示传入就会使用默认值补充。

3.capacity():

返回容器的容量大小

4.empty():

判断容器是否为空

5.reserve():

	vector<int> v;
	cout << "初始容量：" << v.capacity() << endl;
	cout << "容器空间大小：" << sizeof(v) << endl;
	size_t n = v.capacity();
	for (size_t i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (n != v.capacity())
		{
			n = v.capacity();
			cout << "扩容到：" << n << endl;
		}
	}
	cout << "缩容到10，是否成功" << endl;
	v.reserve(10);
	cout << "结果：" << v.capacity() << endl;
	v.clear();
	v.reserve(10);
	cout << "清理后缩容到10的结果：" << v.capacity() << endl;

• 扩容：初始容器没有数据时容量为0；随着容器插入数据，扩容趋向于1.5倍扩容
• 缩容：可以看到reserve不支持缩容。

6.shrink_to_fit

把reserve的测试代码中的reserve换成shrink_to_fit结果怎样

	vector<int> v;
	cout << "初始容量：" << v.capacity() << endl;
	cout << "容器空间大小：" << sizeof(v) << endl;
	size_t n = v.capacity();
	for (size_t i = 0; i < 100; i++)
	{
		v.push_back(i);
		if (n != v.capacity())
		{
			n = v.capacity();
			cout << "扩容到：" << n << endl;
		}
	}
	cout << "缩容是否成功" << endl;
	v.shrink_to_fit();
	cout << "结果：" << v.capacity() << endl;
	v.clear();
	v.shrink_to_fit();
	cout << "清理后缩容的结果：" << v.capacity() << endl;

• 缩容：当容器中有数据且容量大于数据个数时，才会缩容，并且只能缩容到数据个数。
• 当容器中没有数据时，则会缩容到0；

1.4元素访问函数

1.operator[]

• vector类似顺序表，数据存储在连续的内存空间，所以可以通过下标+[]的形式访问
• 有了函数重载其实就算像链表这样空间不连续的容器，也可自己写一个重载[]，但是代价比较大，不建议使用

2.at

• vector的at和string一样，传入一个下标，返回下标位置的数据。

3.front/back

• front返回容器的第一个数据
• back返回容器的最后一个数据

4.data

• 返回vector容器第一个元素地址的指针

1.5容器编辑函数

1.assign

（1）使用迭代器范围 [first, last) 内的元素替换当前 vector 的所有元素。如果当前 vector 容量不足，会进行扩容以容纳新元素；如果容量足够，会直接覆盖原有元素。

（2）将当前 vector 的所有元素替换为 n 个值为 val 的元素。同样，若容量不足会扩容。

（3）使用初始化列表 il 中的元素替换当前 vector 的所有元素。

2.push_back尾插

3.pop_back尾删

4.insert

（1）插入单个元素（single element (1)）：在 position 所指向的元素之前插入一个值为 val 的新元素。vector 会自动管理内存，若当前容量不足会进行扩容。函数返回指向新插入元素的迭代器。

（2）插入多个相同元素（fill (2)）：在 position 所指向的元素之前插入 n 个值为 val 的元素。同样会处理内存管理和扩容问题，返回指向第一个新插入元素的迭代器。

（3）插入迭代器范围内元素（range (3)）：将迭代器范围 [first, last) 内的元素插入到 position 所指向的元素之前。vector 会按需扩容，返回指向第一个新插入元素的迭代器。

（4）移动插入单个元素（move (4)）：在 position 所指向的元素之前插入一个值为 val 的新元素，这里采用移动语义，将 val 的资源移动到 vector 中，原 val 进入有效但未指定状态。适用于避免不必要的拷贝，提高效率。函数返回指向新插入元素的迭代器。

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3};
    int x = 10;
    auto it = v.insert(v.begin() + 1, std::move(x));
    for (int i : v) {
        std::cout << i << " ";
    }
    return 0;
}

输出：1 10 2 3

（5） 插入初始化列表元素（initializer list (5)）：将初始化列表 il 中的元素插入到 position 所指向的元素之前。vector 会进行内存管理和扩容，返回指向第一个新插入元素的迭代器。

5.erase

删除迭代器位置的元素，或者删除一段迭代器区间

6.emplace

emplace 函数用于在 vector 的指定位置 position 处直接构造一个新元素 。与 insert 函数不同，insert 是先创建一个临时对象，然后将其插入到指定位置（涉及对象拷贝或移动），而 emplace 是利用给定的参数 Args 在容器内部直接构造对象，避免了不必要的对象构造和拷贝 / 移动操作，能提高效率，尤其是当元素类型构造开销较大时（vector中每个数据是一个类）。

7.emplace_back

emplace_back 用于在 std::vector 的尾部直接构造并添加一个新元素。与 push_back 相比，push_back 是先创建一个临时对象，再将其移动（或拷贝）到 vector 尾部；而 emplace_back 利用可变参数模板 Args&&... args ，直接在 vector 尾部的内存位置，使用传入参数原位构造元素，避免了不必要的对象构造、拷贝或移动开销，提升效率，尤其适用于构造开销大的自定义类型对象。

vector<A> v2;
A aa1(1, 1);
v2.push_back(aa1);
v2.push_back(A(2,2));
v2.push_back({3,3});

cout << "**************************" << endl;

v2.emplace_back(aa1);
v2.emplace_back(A(2, 2));
//v2.emplace_back({ 3,3 });

// 传构造A的参数，效率较高
v2.emplace_back(3,3);

1.6重载比较

vector的比较函数，是依次比较vector中的每一个数据

1.7迭代器失效

在 C++ 中，std::vector 迭代器失效是指迭代器所指向的内存位置不再有效或者指向的内容发生了变化，导致使用该迭代器进行操作时出现未定义行为。

1插入导致迭代器失效

• 尾部插入且未扩容：当 vector 容量足够，在尾部使用 push_back 或 emplace_back 插入元素时，指向 vector 中原有元素的迭代器不会失效，但是指向 vector 尾部之后位置（end() 返回的迭代器）的迭代器会失效。

• std::vector<int> vec = {1, 2, 3};
  auto it = vec.end();  // 指向尾部之后的迭代器
  vec.push_back(4);
  // 此时it失效，对it的解引用等操作是未定义行为

• 任意位置插入且扩容：在 vector 的任意位置使用 insert 或 emplace 插入元素，并且插入操作导致 vector 扩容（即重新分配内存）时，所有指向 vector 的迭代器都会失效。这是因为扩容会重新分配一块新的内存空间，将原有的元素复制到新空间，原迭代器指向的内存位置不再属于该 vector。

• std::vector<int> vec = {1, 2, 3};
  auto it = vec.begin();
  vec.insert(vec.begin(), 0);  // 插入操作可能导致扩容
  // 此时it失效，对it的解引用等操作是未定义行为

• 任意位置插入且未扩容：当在 vector 的任意位置插入元素且没有导致扩容时，从插入位置开始到 vector 末尾的迭代器都会失效，因为插入元素后，这些位置的元素发生了移动。

2.删除元素导致迭代器失效

• 删除单个元素：使用 erase 删除 vector 中的单个元素时，指向被删除元素的迭代器以及其后的所有迭代器都会失效。
• 删除一段元素：使用 erase 删除一段连续元素时，指向被删除区间以及其后的所有迭代器都会失效。

3. 改变 vector 大小导致迭代器失效

• 使用 resize 缩小 vector 大小：如果 resize 操作缩小了 vector 的大小，那么超出新大小范围的迭代器会失效。
• 使用 resize 扩大 vector 大小：当 resize 操作扩大 vector 大小时，如果导致了内存重新分配（扩容），所有迭代器都会失效；如果没有扩容，那么指向原有元素的迭代器不会失效，新插入元素位置及之后的迭代器是新的。

4. 使用 assign 函数导致迭代器失效

assign 函数会用新的元素替换 vector 中现有的所有元素。无论是否发生内存重新分配，原有的所有迭代器都会失效。

为了避免迭代器失效带来的问题，在插入或删除元素后，如果还需要使用迭代器，通常需要重新获取迭代器。 例如在插入操作后，可以使用 insert 函数的返回值来更新迭代器，erase的返回值也是迭代器，接收这个返回值更新迭代器；在删除操作后，可以在循环中正确处理迭代器的移动。

2.vector的模拟实现

#pragma once
#include <initializer_list>
#include <utility>
#include <cassert>
#include <algorithm>

using namespace std;

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

		vector(){}

		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto& e : il)
			{
				push_back(e);
			}
		}

		template<class inputiterator>
		vector(inputiterator first, inputiterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

		vector(const vector<T>& v)
		{
			vector<T> tem(v.begin(), v.end());
			swap(tem);
		}

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

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

		vector(size_t n, T x = T())
		{
			resize(n, x);
		}

		vector(int n, T x = T())
		{
			resize(n, x);
		}

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

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

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

		size_t capacity() const
		{
			return _end_of_storage - _start;
		}

		size_t size() const
		{
			return _finish - _start;
		}

		T& operator[](size_t n)
		{
			assert(n < size());
			return _start[n];
		}

		void clear()
		{
			_finish = _start;
		}

		void pop_back()
		{
			assert(size() > 0);
			_finish--;
		}

		iterator insert(iterator pos const T& val)
		{
			assert(_start <= pos && pos <= _finish);
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity;
				reserve(newcapacity);
				pos = _start + len;
			}
			iterator end = _finish;
			while (end > pos)
			{
				*end = *(end - 1);
				end--;
			}
			*pos = val;
			_finish++;
			return pos;
		}

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

		const T& operator[](size_t n) const
		{
			assert(n < size());
			return _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 reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t len = size();
				T* newv = new T[n];
				if (_start)
				{
					for (size_t i = 0; i < size(); i++)
					{
						newv[i] = _start[i];
					}
					delete[] _start;
				}
				_start = newv;
				newv = nullptr;
				_finish = _start + len;
				_end_of_storage = _start + n;
			}
		}

		iterator find(const T& val)
		{
			for (size_t i = 0; i < size(); i++)
			{
				if (_start[i] == val)
				{
					return _start + i;
				}
			}
			return _finish;
		}

		bool empty() const
		{
			return _start == _finish;
		}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
}