vector使用和模拟实现

💓博主个人主页:不是笨小孩👀
⏩专栏分类:数据结构与算法👀 C++👀 刷题专栏👀 C语言👀
🚚代码仓库:笨小孩的代码库👀
⏩社区：不是笨小孩👀
🌹欢迎大家三连关注，一起学习，一起进步！！💓

STL

什么是STL？

STL(standard template libaray-标准模板库)：是C++标准库的重要组成部分，不仅是一个可复用的组件库，而且是一个包罗数据结构与算法的软件框架。

STL的六大组件

vector的使用

vector就是我们经常说的顺序表，它是库里面已经实现好的，我们可以直接使用，但是需要包一个vector的头文件。它和string有很大的相似性，所以简单的就不说了。

构造函数

从构造函数我们可以看到，我们可以用n个val来初始化，或者一段迭代器区间，或者一个vector，都是可以的。

void test()
{
	vector<int> v(10, 1);
	vector<int> v1(v);
	vector<int> v2(v1.begin(),v.end());
}
1
2
3
4
5
6

迭代器（iterator）

我们遍历vector可以用迭代器遍历。如果要倒着遍历的话，就需要用rbegin和rend，下面带c的都是const版本的，不可修改。

void test()
{
	vector<int> v;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

它也实现了[]的运算符重载，也可以用for循环像数组一样访问。

void test()
{
	vector<int> v;
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
}
1
2
3
4
5
6
7
8

resize和reserve

resize还是改变size的大小，reserve还是改变capacity的大小。

resize的n如果比size要小的话，就是充当删除的功能。

void test()
{
	vector<int> v;
	v.reserve(400);
	v.resize(10, 2);
	v.resize(5);
}
1
2
3
4
5
6
7

插入删除数据

1. push_back
   

尾插一个数据

void test()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
}
1
2
3
4
5
6
7
8
9

2. pop_back
   

尾删一个数据。

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

	v.pop_back();
	v.pop_back();
	v.pop_back();
}
1
2
3
4
5
6
7
8
9
10
11
12

3. insert

在某个位置插入一个数据，或这n个数据。

我们可以看到，insert需要我们传迭代器过去，并且返回一个迭代器，返回的这个迭代器就是你插入的那个位置的值的迭代器。

void test()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	
	v.insert(v.begin(), 10, 0);
	v.insert(v.begin(), 0);

	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4. erase

删除一个数据，或者一段迭代器区间。

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

	v.erase(v.begin());

	v.erase(v.begin(), v.end()-1);
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << " ";
	}
	cout << endl;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

swap

交换两个vector

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

	vector<int> v1;
	v1.push_back(2);
	v1.push_back(2);

	v.swap(v1);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

vector的模拟实现

结构

我们string是用的和顺序表一样的结构，没有用模板模拟实现，但是，vector我们要用模板来模拟实现，而且结构也和前面的大有不同，但是换汤不换药，还是顺序表的原理。

我们说迭代器是一种类似指针的东西，但是不一定是指针，我们将T*重命名为iterator，也就是迭代器，可以说我们vector这个结构的成员就是三个迭代器，一个指向开始位置，一个指向有效数据的最后一个的下一个位置，还有一个指向空间的最后。

我们知道指针是可以相减的，同类型的指针相减就是两个指针数据的个数，所以size=_finish-_start,同理capacity = _end-_start.

那么我们就先来把简单的接口实现一下：

//我们声明成员变量时给了缺省值，所以这里什么都不用写，都会初始化为nullptr，但是必须有这个函数。
vector()
{}
~vector()
{
	delete[] _start;
	_start = _finish = _end = nullptr;
}
iterator begin()
{
	return _start;
}

iterator end()
{
	return _start + size();
}

const_iterator cbegin() const
{
	return _start;
}

const_iterator cend() const
{
	return _start+size();
}

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

size_t capacity() const
{
	return _end - _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 swap(vector<T>& v)
{
	std::swap(_start, v._start);
	std::swap(_finish, v._finish);
	std::swap(_end, v._end);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

上面的这些接口都很简单，就不细讲了。

1. reserve和resize

reserve就是扩容逻辑，我们需要先开一个空间，然后把数据拷过去，然后在释放原来的空间，把新的空间给_start即可，然后更新_finish和_end。但是需要注意，我们需要先记录一下之前的size，因为_start修改后，就无法知道以前的_size了。

void reserve(size_t n)
{
	if (n > capacity())
	{
		int sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			for (size_t i = 0; i < size(); i++)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}

		_start = tmp;
		_finish = tmp + sz;
		_end = tmp + n;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

resize还是和string一样，如果修改的size 比之前小的话就是删除，比之前大就是看需不需要扩容，然后插数据就可以了。

void resize(size_t n, const T& val = T())
{
	if (n <= size())
	{
		_finish = _start + n;
	}
	else
	{
		reserve(n);
		while (_finish < _start + n)
		{
			*_finish = val;
			_finish++;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 插入和删除数据

push_back

和顺序表逻辑一样，直接尾插即可。

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

	*_finish = x;
	_finish++;
}
1
2
3
4
5
6
7
8
9
10

pop_back

void pop_back()
{
	assert(size() > 0);
	_finish--;
}
1
2
3
4
5

insert

insert和之前不同的是，之前传的是下标，现在传的是一个迭代器，并且插入后返回插入那个数据的迭代器，因为我们插入数据后，那个位置的迭代器的内容就别更新了，或者有可能会扩容，扩容后原本的那个迭代器就失效了。所以我们会返回插入的那个数据的迭代器。

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

	if (size() == capacity())
	{
	 	//防止迭代器失效
		int len = pos-_start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);
		//及时更新pos
		pos = _start + len;
	}

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

	return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

erase

还是传一个迭代器，删除这个迭代器位置的数据，同样，这个数据被删除了，同样会是迭代器失效，我们还是会返回一个迭代器，返回的还是这个位置的迭代器，指向被删除的数据的下一个数据。

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

	iterator begin = pos;

	while (begin < _finish - 1)
	{
		*begin = *(begin + 1);
		begin++;
	}

	_finish--;
	return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3. 构造和赋值重载

我们知道库里面有很多构造，可以用n个val来初始化，也可以用一段迭代器区间，都是一样的思路，直接尾插数据就可以了，但是n个val可以复用resize这个函数。

vector(int n, const T& value = T())
{
	resize(n, value);
}
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
	while (first < last)
	{
		push_back(*first);
		first++;
	}
}
vector(const vector<T>& v)
{
	reserve(v.capacity());

	for (auto& e : v)
	{
		push_back(e);
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

赋值重载
我们直接拷贝构造一份数据，和this交换。

vector<T>& operator= (vector<T> tmp)
{
	swap(tmp);
	return *this;
}
1
2
3
4
5

今天的分享就到这里吧，感谢大家的关注和支持。