C++标准库类型vector和迭代器

忘了说我的运行环境是Ubuntu14.04,vim,gcc version 4.8.4,操作系统和编辑器没什么要紧,gcc如果版本低了可能不支持C++11。
编译运行方法如下:

1
2
$ g++ -std=c++11 -o test test.c
$ ./test

标准库类型vector

标准库类型vector(也常被称为容器)表示对象的集合,其中所有对象的类型都相同。集合中每个对象都有一个与之对应的索引,索引用于访问对象。想要使用vector,必须包含头文件。

1
2
#include <vector>
using std::vector;

C++语言既有类模板(class template),也有函数模板。编译器根据模板创建类或函数的过程称为实例化(instantiation)。模板名字后面跟一对尖括号,在括号内放上存放对象的类型。

1
2
3
vector<int> ivec; // ivec保存int类型的对象
vector<Sales_item> Sales_vec; // 保存Sales_item类型的对象
vector<vector<string>> file; // 该向量的元素是vector对象

定义vector对象

1
2
3
vector<int> ivec; // 默认初始化为空
vector<int> ivec2(ivec); // 把ivec的元素拷贝给ivec2
vector<int> ivec3 = ivec; // 把ivec的元素拷贝给ivec3

初始化不是赋值,初始化的含义是创建变量时赋予其一个初始值,而赋值的含义是把对象的当前值擦除,而以一个新值来替代。

列表初始化vector对象

1
2
vector<string> svec{"a", "an", "the"}; // ivec包含了三个元素
vector<int> ivec = {2, 3, 4, 5} // ivec包含了2,3,4,5四个元素

创建指定数量的元素

1
vector<int> ivec(10, -1); // ivec包含了10个-1

向vector对象中添加元素

vector的成员函数push_back可以向其中添加元素,push_back负责把一个值当成vector对象的尾元素压到vector对象的尾端。

1
2
3
4
5
6
7
8
9
vector<int> v2; // 空
for (int i = 0; i != 100; ++i)
v2.push_back(i); // 依次把i添加到v2尾端

sting word;
vector<string> text; // 空
while (cin >> word) {
text.push_back(word); // 把word添加到text后面
}

其他vector操作

操作 含义
v.empty() 如果v不含任何元素返回真;否则返回假
v.size() 返回v中元素的个数
v[n] 返回v中第n个位置上元素的引用
v1 == v2 v1和v2对应位置的元素都相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
using std::vector;
using std::cout;
using std::endl;
int main()
{

vector<int> v{1,2,3,4,5,6,7,8,9};
for (auto &i : v) // 这里i为引用
i *= i; // 求元素的平方
for (auto i : v)
cout << i << " "; // 输出容器中的元素
cout << endl;
return 0;
}

迭代器

除了下标运算符可以访问string对象或vector对象的元素,迭代器(iterator)也可以。除了vector,标准库还定义了其他几种容器,所有标准库容器都可以使用迭代器。
和指针不一样的是,获取迭代器不是使用取地址符,有迭代器的类型同时拥有返回迭代器的成员。

1
2
// b表示v的第一个元素的位置,e表示v尾元素的下一个位置
auto b = v.begin(), e = v.end();

end成员返回的迭代器常被称作尾后迭代器(off-the-end iterator)

如果容器为空,则begin和end返回的是同一个迭代器,都是尾后迭代器。

迭代器运算符

运算符 含义
*iter 返回迭代器iter所指元素的引用
iter->mem 解引用iter并获取该元素的名为mem的成员,等价于(*iter).mem
++iter 令iter指示容器中的下一个元素
–iter 令iter指示容器中的上一个元素
iter1 == iter2 判断两个迭代器是否相等
iter1 != iter2 判断两个迭代器是否不相等

和指针类似,也能通过解引用迭代器来获取他所指示的元素。

1
2
3
// 依次处理s的字符直至我们处理完全部字符或遇到空格
for (auto it = s.begin(); it != s.end() && !isspace(*it); ++it)
*it = toupper(*it);

迭代器类型

拥有迭代器的标准库类型使用iteratorconst_iterator来表示迭代器的类型:

1
2
3
4
5
6
7
8
9
10
vector<int>::iterator it; // it能读写vector<int>的元素
for (it = v.begin(); it != v.end(); ++i) {
*it *= *it; // 正确,可以读写元素
cout << *it << " ";
}
vector<int>::const_iterator cit; // cit只能读vector<int>的元素,不能写
for (cit = v.begin(); it != v.end(); ++i) {
*cit *= *cit; // 错误,只能读不能写
cout << *cit << " ";
}

如果vector对象是一个常量(const vector<int>),只能用const_iterator;如果不是常量,则iterator和const_iterator都可以用。C++11新标准引入了cbegin()cend()两个新函数,不论vector对象是否是常量,返回值都是const_vector。

迭代器运算

1
2
3
4
// 计算得到最接近vi中间元素的一个迭代器
auto mid = vi.begin + v.size()/2;
if (it < mid)
// 处理vi前半部分的元素

迭代器实现二分搜索

1
2
3
4
5
6
7
8
9
10
11
// text必须是有序的,beg和end表示我们搜索的范围
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg) / 2; // 初始状态下的中间点
// 当还有元素尚未检查并且我们还没有找到sought时执行循环
while (mid != end && *mid != sought) {
if (sought < *mid)
end = mid;
else
beg = mid + 1;
mid = beg + (end - beg) / 2; // 新的中间点
}