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对象的尾端。

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对应位置的元素都相同

#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);

迭代器类型

拥有迭代器的标准库类型使用iterator和const_iterator来表示迭代器的类型：

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。

迭代器运算

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

迭代器实现二分搜索

// 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; // 新的中间点
}