vector与list的简单介绍

1. 标准库中的vector类的介绍：

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

就像数组一样，vector对其元素使用连续的存储位置，这意味着也可以使用指向其元素的常规指针上的偏移量来访问其元素，并且与数组中的元素一样高效。但与数组不同的是，它们的大小可以动态变化，它们的存储由容器自动处理。

在内部，vector使用动态分配的数组来存储其元素。当插入新元素时，可能需要重新分配此数组才能增大大小，这意味着分配一个新数组并将所有元素移动到该数组。就处理时间而言，这是一项相对昂贵的任务，因此，每次将元素添加到容器时，vector都不会重新分配。

相反，vector容器可能会分配一些额外的存储来适应可能的增长，因此容器的实际容量可能大于包含其元素（即其大小）严格需要的存储。库可以实施不同的增长策略，以平衡内存使用和重新分配之间的平衡，但无论如何，重新分配应该只在大小的对数增长间隔下发生，以便在vector末尾插入单个元素时可以提供摊销的恒定时间复杂度（参见push_back）。

因此，与数组相比，vector消耗更多的内存，以换取以有效的方式管理存储和动态增长的能力。

与其他动态序列容器（deques、lists 和 forward_lists）相比，vector非常有效地访问其元素（就像数组一样），并且相对有效地从其末端添加或删除元素。对于涉及在末尾以外的位置插入或删除元素的操作，它们的性能比其他操作差，并且迭代器和引用的一致性低于列表和forward_lists。

这么多话，简单的来说vector帮我们构建了c语言中的数组，但与c语言数组相比较而言，他的效率与使用起来远远大于数组。

本篇文章就不再详细向上篇文章string的介绍了，这里只给几个经常用到的几个功能的使用案例与其简单的实现；

构造函数

我们知道数组有分很多种

比如如下我们构建整形数组与字符数组：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;//整形数组
	vector<char> v;//字符数组
	vector<double> v;//小数数组
	return 0;
}

对于vector有多种构造

我们挨个展示使用案例：

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> first;                                // 空
	vector<int> second(4, 100);                       // 4个100
	vector<int> third(second.begin(), second.end());  // 用second创建，里面存的值与second相同
	vector<int> fourth(third);                       // a copy of third

	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//利用数组构造

	//挨个打印
	cout << "first:";
	for (auto e : first)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "second:";
	for (auto e : second)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "third:";
	for (auto e : third)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "fourth:";
	for (auto e : fourth)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << "The contents of fifth are:";
	for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
		cout << ' ' << *it;
	cout << '\n';

	return 0;
}

迭代器：

vector的迭代器与string的迭代器完全相关，不太清楚的，可以去看我写的string那一篇，那一篇从原理详细讲解了迭代器；

就比如我们使用迭代器打印上面的second

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> second(4, 100);                       // 4个100
	vector<int>::iterator it = second.begin();
	while (it != second.end())
	{
		cout << *it << " ";
		it++;
	}
	return 0;
}

同样也有反向的，这里便于观察，我们将second换一组值

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	int myints[] = { 16,2,77,29 };
	vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));//利用数组构造
	vector<int>::reverse_iterator it = fifth.rbegin();
	while (it != fifth.rend())
	{
		cout << *it << " ";
		it++;
	}
	return 0;
}

最常用的几个：push_back，pop_back，size，empty,clear

#include<iostream>
#include<vector>
using namespace std;
int main()
{
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	cout << "添加完后vector：";
	for (auto& e : v)
	{
		cout << e << " ";
		e++;
	}
	cout << endl;
	cout << "vector的大小：";
	cout << v.size() << endl;
	v.pop_back();
	cout << "后删完后vector：";
	for (auto& e : v)
	{
		cout << e << " ";
		e++;
	}
	cout << endl;
	cout << "vector是否为空：";
	cout << v.empty() << endl;//为空返回true，反之false
	cout << "clear后：";
	v.clear();//清空
	for (auto& e : v)
	{
		cout << e << " ";
		e++;
	}
	cout << endl;
	return 0;
}

查找与修改

vector同样与string一样支持这些功能

就比如查找我们可以通过find查找特定的值，也可以通过直接下标operator[]任意访问

find

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    t.pop_back();
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    cout << *pos << endl;
}

运行结果：

insert

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    t.insert(pos,10);
    for (auto& e : t)
    {
        cout << e << " ";
        e++;
    }
}

运行结果：

erase

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    t.erase(pos);
    for (auto& e : t)
    {
        cout << e << " ";
        e++;
    }
}

运行结果：

swap

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    vector<int> v(5, 7);//5个7
    swap(t, v);
    cout << "换后的t:" << "  ";
    for (auto& e : t)
    {
        cout << e << " ";
        e++;
    }
    cout << endl;
    cout << "换后的v:" << "  ";
    for (auto& e : v)
    {
        cout << e << " ";
        e++;
    }
    cout << endl;
}

运行结果：

operator[]

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    vector<int> t;
    t.push_back(1);
    t.push_back(2);
    t.push_back(3);
    vector<int> ::iterator pos = find(t.begin(), t.end(), 2);
    cout << t[2];
}

运行代码：