C++ vector基本操作

一、介绍

二、定义

三、迭代器

四、容量操作

1、size

2、capacity

3、empty

4、resize

5、reserve

总结（扩容机制）

五、增删查改

1、push_back & pop_back

2、find

3、insert

4、erase

5、swap

6、operator[]

一、介绍

vector的文档介绍

vector是表示可变大小数组的序列容器。
就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

vector的使用

vector学习时一定要学会查看文档：vector的文档介绍，vector在实际中非常的重要，在实际中我们熟悉常见的接口就可以。

二、定义

这些是C++标准库中`vector`类的构造函数的不同重载形式。下面是对每个构造函数的解释：

1. 无参构造函数：`vector()`

vector<int> v;

创建一个空的`vector`对象，不包含任何元素。

2. 构造并初始化n个val：`vector(size_type n, const value_type& val = value_type())`

vector<int> v1(10, 1);

创建一个包含`n`个元素的`vector`对象，每个元素都初始化为`val`。
可以选择提供一个初始值`val`，如果未提供，则使用默认值类型的默认构造函数进行初始化。

3. 使用迭代器进行初始化构造：`vector(InputIterator first, InputIterator last)`

string s1("hello");
vector<char> v3(s1.begin(), s1.end());

创建一个`vector`对象，并使用范围 `[first, last)` 内的元素进行初始化。
`first` 和 `last` 是迭代器，指定了要复制的元素范围。
这个构造函数允许使用迭代器来指定要复制的元素范围，可以是数组、容器或其他可迭代对象。

4. 拷贝构造函数：`vector(const vector& x)` 重点

vector<int>v1(v);

创建一个新的`vector`对象，其元素与另一个`vector`对象`x`相同。
拷贝构造函数用于创建一个副本，新的`vector`对象将独立于原始对象，对其中一个对象的修改不会影响另一个对象。

举例演示一下，其中输出和string类一样，有三种方式：范围for [ ] 迭代器。

void test1()
{
	//无参构造
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);

	//三种输出方式 范围for [] 迭代器
	for (auto a : v)
	{
		cout << a << " ";
	}
	cout << endl;

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

	//vector<int>::iterator it = v.begin();
	auto it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	
	//拷贝构造
	vector<int> copy(v);
	for (auto a : copy) 
	{
		cout << a << " ";
	}
	cout << endl;
}
void test2()
{
	//构造并初始化
	vector<int> v1(6, 6);
	for (auto a : v1)
	{
		cout << a << " ";
	}
	cout << endl;

	//迭代器
	vector<int> v2(v1.begin(), v1.end());
	for (auto b : v2)
	{
		cout << b << " ";
	}
	cout << endl;

	string s1("hello");
	vector<char> v3(s1.begin(), s1.end());
	for (auto b : v3)
	{
		cout << b << " ";
	}

}
int main()
{
	test1();
    cout << endl;
    test2();
	return 0;
}

三、迭代器

begin()/end()：获取第一个数据位置的iterator / const_iterator，获取最后一个数据的下一个位置的iterator / const_iterator

rbegin()/rend()：获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator

通过使用这些接口，可以在vector中进行迭代操作。

例如，使用begin()和end()可以遍历vector中的元素，而使用rbegin()和rend()可以反向遍历vector中的元素。
请注意，对于只读的vector，应使用const_iterator和const_reverse_iterator来确保不修改vector的元素。

void test3()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
    //正向迭代器
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
    //反向迭代器
	vector<int>::reverse_iterator rit = v.rbegin();
	while (rit != v.rend())
	{
		cout << *rit << " ";
		++rit;
	}
}
int main()
{
    test3();
    return 0;
}

四、容量操作

1、size

获取数据个数。

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    std::cout << "Size of vector: " << v.size() << std::endl;
    return 0;
}

2、capacity

capacity获取容量大小。

int main() {
    std::vector<int> v;
    std::cout << "Initial capacity: " << v.capacity() << std::endl;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        std::cout << "Capacity after pushing " << i << ": " << v.capacity() << std::endl;
    }
    return 0;
}

3、empty

判断是否为空。

int main() {
    std::vector<int> v;
    std::cout << "Is vector empty? " << (v.empty() ? "Yes" : "No") << std::endl;
    v.push_back(1);
    std::cout << "Is vector empty? " << (v.empty() ? "Yes" : "No") << std::endl;
    return 0;
}

4、resize

改变vector的size。

void resize (size_type n, value_type val = value_type());

调整容器的大小，使其包含 n 个元素。
如果 n 小于当前容器大小，则内容将减少到其前 n 个元素，删除超出的元素（并销毁它们）。
如果 n 大于当前容器大小，则通过在末尾插入任意数量的元素来扩展内容，以达到 n 的大小。如果指定了 val，则新元素将初始化为 val 的副本，否则，它们将初始化值。
如果 n 也大于当前容器容量，则会自动重新分配分配的存储空间。
请注意，此函数通过插入或擦除容器中的元素来更改容器的实际内容。

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    v.resize(7, 100);
    for (int i : v) {
        std::cout << i << " ";
    }
    std::cout << std::endl;
    v.resize(3);
    for (int i : v) {
        std::cout << i << " ";
    }
    return 0;
}

5、reserve

改变vector的capacity。

reserve(): 这个方法更改vector的capacity。如果新的capacity大于当前的capacity，那么vector的内存将被重新分配以适应更多的元素。如果新的capacity小于当前的capacity，那么这个方法不会有任何效果。

int main() {
    std::vector<int> v;
    std::cout << "Initial capacity: " << v.capacity() << std::endl;
    v.reserve(10);
    std::cout << "Capacity after reserving: " << v.capacity() << std::endl;
    return 0;
}

总结（扩容机制）

capacity的代码在vs和g++下分别运行会发现，vs下capacity是按1.5倍增长的，g++是按2倍增长的。
这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL。
reserve只负责开辟空间，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
resize在开空间的同时还会进行初始化，影响size。

通过下面代码可以观察到vector的默认扩容机制。

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';
		}
	}
}

如果已经确定vector中要存储元素大概个数，可以提前将空间设置足够就可以避免边插入边扩容导致效率低下的问题了。

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';
		}
	}
}