【C++修炼之路 第六章】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 统一的迭代器和引用更好

使用STL的三个三个境界: 能用，明理， 能拓展，下面讲详细介绍STL – vector

---

1、vector的使用

先看一下 vector 的官方文档，实际使用中，只需记住常见的接口，其他的需要时再自己查文档

成员函数

非成员函数

---

1.1 构造函数

1.2 迭代器

这里方便理解，可以将迭代器理解成指向头或尾的指针（但 指针 不等于 迭代器，只是为了理解）

---

迭代器遍历

int main()
{
	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 << '\n';
 		it++;
	}
	return 0;
}

一般不使用迭代器遍历

别人好歹是类似数组的顺序表，一般都是直接使用方括号遍历

1.3 vector 空间增长问题

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

1.4 vector 增删查改

2、思考题（重点：深刻探讨 vector )

2.1 vector< char > 和 string 的区别

string 是一个字符串类，可以插入一个字符 或 一条字符串

而 vector< char > 是一个元素类型为 char 的顺序表，一次只能插入一个 字符

本质区别

第一：

string 可以实现 += 一个字符串，是因为字符串本身的性质，char* 引导

而 vector< char > 是一个顺序表，再怎么变化，一次也就只能插入一个数据

第二：

vector< char > 插入 “hello” 没有 ‘\0’

string 插入 “hello\0” 需要加 ‘\0’

string 和 vector< char > 存储结构上区别不大，在 增删查改方面有区别，因此各自的作用不同

小结：string 是针对字符数组的需求设计的，而 vector 是为所有类型设计的

关于两者底层结构：是相当相似的

// vector< char > 
// 这里 T = char 
template<class T>
class vector
{
private:
	T* _a;
	size_t _size;
	size_t _capacity;
};
 
 
// string
class string
{
private:
	char* _str;
	size_t _size;
	size_t _capacity;
};

---

2.2 关于模板类 vector<T> 的 类型

vector 是 类名

vector<T> 是类型

某些操作要分清 类名 和 类型

如 使用迭代器时，写的类型是 vector< int > ，而不是 vector

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

2.3 若要用 vector 存储字符串：使用 vector<char*> 还是 vector<string> ?

不建议使用 vector< char* > ：这个还要自己 new 空间（即每一个元素都要 new 一下空间）

建议使用 vector<string> ：即一个 string 为元素类型 数组，类似结构体数组

2.4 创建 vector<vector< int >> v 的 编译器的底层表现如何？

编译器先根据 vector 模板 实例化一个 int 类型的 vector类

再 根据 vector 模板 实例化一个 vector< int > 类型的 vector类

相当于在底层，编译器通过模板开了两个类

像二维数组一样访问：底层的表现如下

vector<vector<int>>v;
v[i][j];
// 相当于
(v.operator[](i)).operator[](j);
// v[i] 先调用  vector< int > 类型的模板类 的 operator[] 函数，返回  vector<int> 类型
// (vector<int>)[j]  再调用 int 类型的的模板类 的 operator[] 函数，返回 int

2.5 vector 的 push_back 的三种传值方式

• 传对象
• 传匿名对象
• 传值（隐式类型转换成对象）

void Push_back(const string& s)
{}
 
void Test() {
	
	vector<string>v;
    
	string s1("张三");
	v.push_back(s1); // 传对象
    
	v.push_back(string("李四")); // 匿名对象   
    // 匿名对象 传参的对象也具有常性，接收参数也要 使用 const
    
	v.push_back("王五"); // 隐式类型转换
 
}

---

3、vector 的性质总结

• vector 就像一个 可以动态变化大小的 数组
• 通过下标访问 vector 的 效率和数组相同，vector 的大小与扩展空间的规则由编译器和类本身控制
• 扩容时，会额外增加一些空间，提高添加元素的效率（减少了扩容次数）
• 调用 reserve 可以提前分配空间，减少频繁扩容的性能损失。