当前位置：首页 > article >正文

关于标准库中的vector - （涉及迭代器失效，深浅拷贝，构造函数，内置类型构造函数，匿名对象）

article 2024/11/19 2:37:31

关于vector

vector中的常见接口

vector常见接口的实现

迭代器失效

关于深浅拷贝

关于vector

关于vector的文档介绍

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

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

3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。

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

5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。

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

vector中的常见接口

vector 的定义

void test_vector1()
{
	//构造函数 - 赋值构造
	vector<int> v1(10, 1);
	for (auto e : v1)
	{
		cout << e << " ";
	}
	cout << endl;

	//构造函数 - 迭代器区间构造
	vector<int> v2(v1.begin(), v1.end());
	for (auto e : v2)
	{
		cout << e << " ";
	}
	cout << endl;

	//构造函数 - 可以传任意类型的迭代器区间，因为是模板
	string s1("hello world");
	vector<int> v3(s1.begin(), s1.end());
	for (auto e : v3)
	{
		cout << e << " ";
	}
	cout << endl;

	//可以++，或者--，类型需要匹配 - 这里char也属于int类型，因为存储的是ascii码
	vector<int> v4(++s1.begin(), --s1.end());
	for (auto e : v4)
	{
		cout << e << " ";
	}
	cout << endl;

	vector<char> v5(++s1.begin(), --s1.end());
	for (auto e : v5)
	{
		cout << e << " ";
	}
	cout << endl;
}

vector iterator 的使用

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

	//迭代器访问
	vector<int> ::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	//vector<int> ::reverse_iterator rit = v.rbegin();
	auto rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
	cout << endl;
}

vector 空间增长问题

//  vector的resize 和 reserve
// reisze(size_t n, const T& data = T())
// 将有效元素个数设置为n个，如果时增多时，增多的元素使用data进行填充
// 注意：resize在增多元素个数时可能会扩容
void Test_Vector3()
{
	vector<int> v;

	for (int i = 1; i < 10; i++)
		v.push_back(i);

	v.resize(5);
	v.resize(8, 100);
	v.resize(12);

	for (size_t i = 0; i < v.size(); i++)
		cout << ' ' << v[i];
	cout << '\n';
}

// 测试vector的默认扩容机制
// vs：按照1.5倍方式扩容
// linux：按照2倍方式扩容
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i) 
	{
		v.push_back(i);
		if (sz != v.capacity()) 
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

// 往vecotr中插入元素时，如果大概已经知道要存放多少个元素
// 可以通过reserve方法提前将容量设置好，避免边插入边扩容效率低
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100);   // 提前将容量设置好，可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i) 
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

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

2. 这个问题经常会考察，不要固化的认为， vector 增容都是 2 倍，具体增长多少是根据具体的需求定义的。vs 是 PJ 版本 STL ， g++ 是 SGI 版本 STL 。

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

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

vector 增删查改

// 尾插和尾删：push_back/pop_back
void Test_Vector4()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
    v.push_back(5);

    //vector<int>::iterator it = v.begin();
	auto it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	v.pop_back();
	v.pop_back();

	it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
}


// 任意位置插入：insert和erase，以及查找find
// 注意find不是vector自身提供的方法，是STL提供的算法
void Test_Vector5()
{
	// 使用列表方式初始化，C++11新语法
	vector<int> v{ 1, 2, 3, 4 };

	// 在指定位置前插入值为val的元素，比如：3之前插入30,如果没有则不插入
	// 1. 先使用find查找3所在位置
	// 注意：vector没有提供find方法，如果要查找只能使用STL提供的全局find
	auto pos = find(v.begin(), v.end(), 3);
	if (pos != v.end())
	{
		// 2. 在pos位置之前插入30
		v.insert(pos, 30);
	}

	vector<int>::iterator it = v.begin();
	while (it != v.end()) 
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	pos = find(v.begin(), v.end(), 3);
	// 删除pos位置的数据
	v.erase(pos);

	it = v.begin();
	while (it != v.end()) 
    {
		cout << *it << " ";
		++it;
	}
	cout << endl;
}

vector常见接口的实现

这里接口的实现参考了一些stl底层源码

template<class T>
class vector
{
public:
	typedef T* iterator;

	//接口实现

private:
	iterator _start;
	iterator _finish;
	iterator _end_of_storage;
};

1.构造函数

无参构造

		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}

带参构造


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

这个地方涉及到一个知识点，那就是：匿名对象调用默认构造函数

会有人好奇，匿名对象的生命周期不是只存在于这一行吗？

例：

class A
{
public:
	A(){
		cout << "A()" << endl;
	}

	~A(){
		cout << "~A()" << endl;
	}

};

vs2013有点bug 地方在于可以支持下列写法，但是vs2019之后就修复了。

迭代器构造

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

这个地方涉及到一个知识点，那就是：允许类的成员函数再是函数模板 - 也就意味着，可以再添加函数模板参数

为什么不使用 iterator ，而使用模板？

使用模板不会显得多此一举吗？

回答是不会，如果使用 iterator 就把这里的构造函数写死了，以后使用必须要传vector的迭代器来运行，迭代器区间的构造不一定要使用vector，一个容器使用迭代器区间去初始化，只要存储的类型符合，就可以使用任意类型的迭代器。

这里可以简单优化一下，因为c++11支持给缺省值，所以就可以省略掉初始化列表

        vector()
		{}

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

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

上述代码运行会有一个隐形的小问题，运行后发现：

test_vector()
{
    vector<int> (10, 5);

    return 0;
}

原因是因为：

这里有两种解决办法：

2.iterator

		typedef const T* const_iterator;


		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

3.size()

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

4.capacity()

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

5.operator[ ]

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

6.reserve()

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];

				if (_start)
				{
					memcpy(tmp, _start, sizeof(T) * size());
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + size(); 
				_end_of_storage = _start + n;
			}
		}

这段代码存在一个问题，那就是size() 已经被修改，所以赋值给 _finish失败。

修改后：

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];

				size_t sz = size();
				if (_start)
				{
					memcpy(tmp, _start, sizeof(T) * size());
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz; 
				_end_of_storage = _start + n;
			}
		}

7.push_back()

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

8.empty()

		bool empty()
		{
			return _start == _finish;
		}

9.pop_back

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

10.resize()

		void resize(size_t n , T val = T())
		{
			if (n < size())
			{
				//删除数据
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}

				while (_finish != _start + n)
				{
					//注：这里如果实现逻辑是使用内存池，需要使用定位new来对已有空间进行初始化
					*_finish = val;
					++_finish;
				}

			}
		}

初始化的值是val，但是val缺省值为什么没给0？而是 T val = T()

因为写的是泛型编程给0 ，char double都可以使用，但是像string一类就不行

这里是匿名对象调用默认构造，由此产生一个新问题，如果 T 是int类型，有没有默认构造？

template<class T>
	void f()
	{
		T x = T();
		cout << x << endl;
	}

	void test2()
	{
		f<int>();
		f<int*>();
		f<double>();
	}

	void test()
	{
		int i = int(); //支持
		int j = int(); //支持

		//int* pi = int* (); //这里也支出构造函数，但是不支持这样玩
	}

//内置类型有没有构造函数？

//默认是没有构造函数的这个说法的

//默认构造函数是针对自定义类型的

//我们不写，编译器会自动生成，我们写了，编译器就不会默认生成

//默认生成的构造函数，内置类型不会处理，自定义类型会去调用它的构造函数

//但是有了模板之后，内置类型需要有构造函数

11.insert() / 需要优化，优化后代码在下面

		void insert(iterator pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			*pos = val;
			_finish++;
		}

12.erase() / 需要优化，优化后代码在下面

		void erase(iterator pos)
		{
			assert(pos >= _start && pos <= _finish);

			iterator remove = pos + 1;
			while (remove != _finish)
			{
				*(remove - 1) = remove;
				remove++;
			}

			--_finish;
		}

迭代器失效

迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装

比如：vector的迭代器就是原生态指针T* 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。

对于 vector 可能会导致其迭代器失效的操作有：

1. 会引起其底层空间改变的操作，都有可能是迭代器失效，比如：resize、reserve、insert、assign、push_back、erase等。

	void test_vector1()
	{
		vector<int> v;

		vector<int>::iterator it = v.begin();

		// 将有效元素个数增加到100个，多出的位置使用0填充，操作期间底层会扩容
			v.resize(100, 0);

		// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
		// v.reserve(100);

		// 插入元素期间，可能会引起扩容，而导致原空间被释放
		// v.insert(v.begin(), 0);
		// v.push_back(8);

		/*
		出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
		而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
		空间，而引起代码运行时崩溃。
		解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
		赋值即可。
		*/
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}

指定位置元素的插入操作 - insert()

测试：

因为这里进行了扩容，_start , _finish , _end_of_storage 都发生了改变，但是pos指向的地址没有改变

解决办法：更新 pos 确定在新开空间里的相对位置 - 计算pos与_start的位置

但是运行后依旧发现问题没有解决，程序依旧报错，原因是什么呢？

因为形参的改变不影响实参，虽然函数内修改了pos指向的位置，但是出了函数作用域pos依旧指向之前的位置，所以迭代器依旧会失效

那如果使用引用传参，是否可以解决？

那么就会出现下列问题：

当我们去查看文档时，会发现，其实 insert() 是有返回值的，返回的是

所以具体实现如下：当然我们认为 insert 以后，pos位置就失效了，不能继续使用，所以并不建议继续使用

insert()

		iterator insert(iterator& pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);

				//扩容后 更新pos
				pos = pos + len;
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			*pos = val;
			_finish++;

			return pos;
		}

指定位置元素的删除操作 - erase()

同理：erase() 我们认为也具有 insert() 的特性，所以 erase() 之后，也认为指针失效了，并且vs下，对此有严格的检查

例1：

vs怎么进行的检查？

因为（*pos）++；这里不是指针解引用，而是是函数调用，vs重载了运算符 *

erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。

例2：要求删除所有的偶数

    void Test_vector()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);
		v1.push_back(5);
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		//要求删除所有的偶数
		vector<int>::iterator it = v1.begin();
		while (it != v1.end())
		{
			if (*it % 2 == 0)
			{
		
			     v1.erase(it);
			}
		
			++it;
			
		}

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

	}

上述代码运行后会崩溃，原因就在于迭代器失效，所以需要有返回值进行接收

所以， erase() 具体实现也会有返回值

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos <= _finish);

			iterator remove = pos + 1;
			while (remove != _finish)
			{
				*(remove - 1) = remove;
				remove++;
			}

			--_finish;

			return pos;
		}

注意：Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs下极端。

例1：

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);

 for(size_t i = 0; i < v.size(); ++i)
 {
     cout << v[i] << " ";
 }

 cout << endl;

 auto it = v.begin();

 cout << "扩容之前，vector的容量为: " << v.capacity() << endl;

 // 通过reserve将底层空间设置为100，目的是为了让vector的迭代器失效 
 v.reserve(100);

 cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
 
 // 经过上述reserve之后，it迭代器肯定会失效，在vs下程序就直接崩溃了，但是linux下不会
 // 虽然可能运行，但是输出的结果是不对的

 while(it != v.end())
 {
     cout << *it << " ";
     ++it;
 }

 cout << endl;

 return 0;
}

程序输出：
1 2 3 4 5
扩容之前，vector的容量为: 5
扩容之后，vector的容量为: 100
0 2 3 4 5 409 1 2 3 4 5

例2：

// 2. erase删除任意位置代码后，linux下迭代器并没有失效
// 因为空间还是原来的空间，后序元素往前搬移了，it的位置还是有效的

#include <vector>
#include <algorithm>

int main()
{
 vector<int> v{1,2,3,4,5};

 vector<int>::iterator it = find(v.begin(), v.end(), 3);
 v.erase(it);

 cout << *it << endl;

 while(it != v.end())
 {
     cout << *it << " ";
     ++it;
 }

 cout << endl;

 return 0;
}

程序可以正常运行，并打印：
4
4 5

例3：

// 3: erase删除的迭代器如果是最后一个元素，删除之后it已经超过end
// 此时迭代器是无效的，++it导致程序崩溃

int main()
{
 vector<int> v{1,2,3,4,5};

 // vector<int> v{1,2,3,4,5,6};

 auto it = v.begin();

 while(it != v.end())
 {
     if(*it % 2 == 0)
     v.erase(it);
     ++it;
 }

 for(auto e : v)
     cout << e << " ";

 cout << endl;

 return 0;
}

// 使用第一组数据时，程序可以运行

[ @VM - 0 - 3 - centos ] $ g ++ testVector . cpp - std = c ++ 11

[ @VM - 0 - 3 - centos ] $ . / a . out

1 3 5

=========================================================

// 使用第二组数据时，程序最终会崩溃

[ @VM - 0 - 3 - centos ] $ vim testVector . cpp

[ @VM - 0 - 3 - centos ] $ g ++ testVector . cpp - std = c ++ 11

[ @VM - 0 - 3 - centos ] $ . / a . out

Segmentation fault

从上述三个例子中可以看到： SGI STL 中，迭代器失效后，代码并不一定会崩溃，但是运行结果肯定不对，如果it 不在 begin 和 end 范围内，肯定会崩溃的。

与vector类似，string在插入+扩容操作+erase之后，

#include <string>

void TestString()
{
 string s("hello");

 auto it = s.begin();

 // 放开之后代码会崩溃，因为resize到20会string会进行扩容
 // 扩容之后，it指向之前旧空间已经被释放了，该迭代器就失效了
 // 后序打印时，再访问it指向的空间程序就会崩溃

 //s.resize(20, '!');

 while (it != s.end())
 {
     cout << *it;
     ++it;
 }
 cout << endl;

 it = s.begin();

 while (it != s.end())
 {
     it = s.erase(it);
     // 按照下面方式写，运行时程序会崩溃，因为erase(it)之后
     // it位置的迭代器就失效了
     // s.erase(it); 

     ++it;
 }
}

迭代器失效解决办法：在使用前，对迭代器重新赋值即可。

关于深浅拷贝

上面差不多就是 vector 的所有常用接口，当然也还差几个。比如，当运行下面这个测试用例，程会报错

	void test_vector1()
	{
		vector<int> v1(10, 2);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2(v1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

	}

究其原因是在于这里我们并没有实现拷贝构造，我们没有实现，编译器会自己实现，但是编译器实现的拷贝构造是值拷贝，也就是浅拷贝，会造成内存的重复释放，也就导致程序报错

所以 vector实现这里我们还需实现一个拷贝构造

此时会发现上面的测试用例已经跑过了，那么我们多测几个：

	void test_vector1()
	{
		vector<std::string> v3(3, "********************");
		for (auto e : v3)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<std::string> v4(v3);
		for (auto e : v4)
		{
			cout << e << " ";
		}
		cout << endl;
	}

这个时候程序就挂掉了，why？因为我们实现的拷贝构造是使用 memcpy函数

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

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

这里也会造成二次析构，导致程序崩溃。可以参考下图：

具体可以了解一下string类以及 memcpy函数里面都有些底层的实现：

以上所述都表明这里的拷贝构造需要修改，但是怎么去修改呢？这里引用了模板，所以我们不能自己去实现深拷贝。

不过，我们可以调用一个深拷贝函数，也就是赋值。这里不仅仅是拷贝构造需要修改，所有涉及memcpy的都需要修改，也就是说 reserve() 也需要修改

拷贝构造

		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T) * v.size());
			for (size_t i = 0; i < v.size(); ++i)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}

reserve()

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];

				size_t sz = size();
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * size());
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz; 
				_end_of_storage = _start + n;
			}
		}

是不是感觉到这vector接口总算没问题了？不，仍旧有问题，请看测试用例：以杨辉三角为例：

	class Solution 
	{
	public:
		vector<vector<int>> generate(int numRows) 
		{
			vector<vector<int>> vv;

			vv.resize(numRows, vector<int>());

			for (size_t i = 0; i < vv.size(); ++i)
			{
				vv[i].resize(i + 1, 0);
				vv[i][0] = vv[i][vv[i].size() - 1] = 1;
			}

			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					if (vv[i][j] == 0)
					{
						vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
					}
				}
			}

			return vv;
		}
	};

	void test_vector1()
	{
		vector<vector<int>> ret = Solution().generate(5);

		for (size_t i = 0; i < ret.size(); ++i)
		{
			for (size_t j = 0; j < ret[i].size(); ++j)
			{
				cout << ret[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;

	}

通过调试我们可以看到，这两层 vector<vector<int>> ,外面的 vector 实现的是深拷贝，而里面的vector 实现的是依旧浅拷贝，为什么？我们不是明明已经完善了拷贝构造嘛？

说明什么，说明拷贝构造还不够完善呗，原因其实出在赋值上面，因为 vector 我们并没有写赋值，所以使用的是编译器默认生成的赋值，默认生成的赋值来进行拷贝，也就是浅拷贝。

		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<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

此时，程序正常运行

另外，拷贝构造其实也可以有多种写法：

比如利用类模板



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

或者范围for+push_back

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

值得吐槽的是，现在的vs做了很多的优化

第一点是代码出错了也不一定挂掉，依旧拿上面的杨辉三角代码举例，如果不写赋值

vs2019代码会直接挂掉

vs2022代码正常运行

你说这扯不扯，由此也就牵扯了下面这个吐槽

第二点是就算是正常，它也表现的不是很正常，此时已经写了赋值

vs2022运行正常，但是，看调试

这里不应该是深拷贝吗？不是已经重载了赋值了吗？为什么看起来还是浅拷贝？

在vs19上我们其实可以看到，地址是不同的

但是由于vs22的优化，导致我们看起来好像还是浅拷贝，其实不是，怎么样，看起来不正常，实际上是正常。

这里有个猜测是，return vv 返回的时候，并没有把 vv 给析构掉，而是直接把 vv 的地址赋给了ret，并且程序结束的时候并没有析构两次。当然，这只是猜测，具体可以自己下去尝试以下。

最后，附上所有模拟底层接口实现代码以及测试用例：

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#include "vector.h"

int main()
{
	dw::test_vector1();

	return 0;
}

vector.h

#pragma once
#include <assert.h>

namespace dw
{
	template <class T>
	class vector
	{
	public:
		typedef T* iterator;

		typedef const T* const_iterator;


		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		vector()
		{}

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

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

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

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];

				size_t sz = size();
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * size());
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}

				_start = tmp;
				_finish = _start + sz; 
				_end_of_storage = _start + n;
			}
		}

		void resize(size_t n , T val = T())
		{
			if (n < size())
			{
				//删除数据
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}

				while (_finish != _start + n)
				{
					//注：这里如果实现逻辑是使用内存池，需要使用定位new来对已有空间进行初始化
					*_finish = val;
					++_finish;
				}

			}
		}

		iterator insert(iterator& pos, const T& val)
		{
			assert(pos >= _start && pos <= _finish);

			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : capacity() * 2);

				//扩容后 更新pos
				pos = pos + len;
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}

			*pos = val;
			_finish++;

			return pos;
		}

		iterator erase(iterator pos)
		{
			assert(pos >= _start && pos <= _finish);

			iterator remove = pos + 1;
			while (remove != _finish)
			{
				*(remove - 1) = remove;
				remove++;
			}

			--_finish;

			return pos;
		}

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

		void pop_back()
		{
			assert(!empty());
			--_finish;
		}

		bool empty()
		{
			return _start == _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];
		}

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

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

		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<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

		vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			//memcpy(_start, v._start, sizeof(T) * v.size());
			for (size_t i = 0; i < v.size(); ++i)
			{
				_start[i] = v._start[i];
			}
			_finish = _start + v.size();
			_end_of_storage = _start + v.capacity();
		}

		//vector(const vector<T>& v)
		//{
		//	reserve(v.size());
		//	for (auto e : v)
		//	{
		//		push_back(e);
		//	}
		//}

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

		~vector()
		{
			//cout << _start << endl;
			delete[] _start;
			_start = _finish = _end_of_storage;
		}

	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end_of_storage = nullptr;
	};
class Solution 
	{
	public:
		vector<vector<int>> generate(int numRows) 
		{
			vector<vector<int>> vv;

			vv.resize(numRows, vector<int>());

			for (size_t i = 0; i < vv.size(); ++i)
			{
				vv[i].resize(i + 1, 0);
				vv[i][0] = vv[i][vv[i].size() - 1] = 1;
			}

			for (size_t i = 0; i < vv.size(); ++i)
			{
				for (size_t j = 0; j < vv[i].size(); ++j)
				{
					if (vv[i][j] == 0)
					{
						vv[i][j] = vv[i - 1][j] + vv[i - 1][j - 1];
					}
				}
			}

			return vv;
		}
	};

	void test_vector1()
	{
		vector<vector<int>> ret = Solution().generate(5);

		for (size_t i = 0; i < ret.size(); ++i)
		{
			for (size_t j = 0; j < ret[i].size(); ++j)
			{
				cout << ret[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;

	}


	void test_vector5()
	{
		vector<std::string> v1(3, "*********************");
		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<std::string> v2(v1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector4()
	{
		vector<int> v1(10, 2);

		for (auto e : v1)
		{
			cout << e << " ";
		}
		cout << endl;

		vector<int> v2(v1);
		for (auto e : v2)
		{
			cout << e << " ";
		}
		cout << endl;

	}


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

		vector<int>::iterator pos = find(v.begin(), v.end(), 3);
		if (pos != v.end())
		{
			v.insert(pos, 30);

		}

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		(*pos)++;

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	void test_vector()
	{
		vector<int> v;

		vector<int>::iterator it = v.begin();

		// 将有效元素个数增加到100个，多出的位置使用0填充，操作期间底层会扩容
			v.resize(100, 0);

		// reserve的作用就是改变扩容大小但不改变有效元素个数，操作期间可能会引起底层容量改变
		// v.reserve(100);

		// 插入元素期间，可能会引起扩容，而导致原空间被释放
		// v.insert(v.begin(), 0);
		// v.push_back(8);

		/*
		出错原因：以上操作，都有可能会导致vector扩容，也就是说vector底层原理旧空间被释放掉，
		而在打印时，it还使用的是释放之间的旧空间，在对it迭代器操作时，实际操作的是一块已经被释放的
		空间，而引起代码运行时崩溃。
		解决方式：在以上操作完成之后，如果想要继续通过迭代器操作vector中的元素，只需给it重新
		赋值即可。
		*/
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}


	void test_vector2()
	{
		vector<int> v;

		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

		for (size_t i = 0; i < v.size(); ++i)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it <<" ";
			++it;
		}
		cout << endl;

		v.pop_back();
		v.pop_back();
		v.pop_back();
		v.pop_back();

		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;

	}

}

以上仅代表个人看法，欢迎讨论交流。

查看全文

http://www.kler.cn/a/154287.html