iterator

是除了下标运算外的另一种访问 string 对象和 vector 对象指定元素的方式。以上两种在内的所有标准库容器都可以使用迭代器而未必可以使用下标。这也是C++中使用迭代器较多的原因。

迭代器类似指针提供了对对象的间接访问，其对象就是容器内的元素。迭代器也分为有效和无效，有效的指向某个元素或尾元素的下一个位置，其余情况属于无效。

使用迭代器

有迭代器的类型同时拥有返回迭代器的成员，如 begin 和 end 。

auto b = v.begin(), e = v.end(); //分别是起始和尾后位置

前者返回指向的第一个元素的迭代器，后者返回指向容器 尾元素的下一位置 one past the end 的迭代器，即指向一个不存在的 尾后 off the end 元素，表示处理完成。end 返回的迭代器称为尾后迭代器 off-the-end iterator 或后迭代器 end iterator。在cppreference中被称为past-the-end iterator。若容器为空，二者均返回尾后迭代器。

严格的使用迭代器的容器要求为：
https://en.cppreference.com/w/cpp/named_req/Iterator

• The type It satisfies CopyConstructible, and
• The type It satisfies CopyAssignable, and
• The type It satisfies Destructible, and
• lvalues of type It satisfy Swappable, and
• std::iterator_traits<It> has member typedefs value_type, difference_type, reference, pointer, and iterator_category , and
• Given r, an lvalue of type It, the following expressions must be valid and have their specified effects:

  Expression	Return Type	Precondition
  *r	unspecified	r is dereferenceable (see below)
  ++r	It&	r is incrementable (the behavior of the expression ++r is defined)

另，对可解引用 deferenceable 的解释参见上述链接。

迭代器运算符

int main(){
    string s("this is a string"); 
    auto b = s.begin(), e = s.end();
    if(b != e) {           //保证s不为空
        for (auto it = s.begin(); it!=s.end(); ++it) //常见迭代器遍历写法
            *it = toupper(*it);
    }
    cout<<s;
}

迭代器for语句的处理过程：检查是否到达string尾部，如果尚未到达则将it解引用的结果传入isspace检查是否遇到空白。每次迭代最后执行++it访问s的下一个字符。

迭代器类型

vector<int>::iterator it;           //可读写vector<int>元素
vector<int>::const_iterator it2;    //只读
string::iterator it3;               //可读写string元素
string::const_iterator it4;         //只读

对不同类型容器的auto会返回不同的迭代器类型：

vector<int> v;
const vector<int> cv;
auto it1 = v.begin();    //vector<int>::iterator
auto it2 = cv.begin();   //vector<int>::const_iterator

C++11中引入了 cbegin 和 cend 两个函数用于返回常量只读迭代器：

auto it3 = v.cbegin();   //vector<int>::const_iterator

解引用和箭头运算

例如，需要使用vector对象的迭代器it检查元素是否为空，需要的操作：
(*it).empty(); 或 it->empty();，其中箭头运算符a->b就是解引用并取成员(*a).b的作用。

示例，访问vector<string>中string的成员函数empty()判断当前iter的内容是否为空：

int main(){
    vector<string> v = {"hello", "world"};
    for(vector<string>::iterator it=v.begin();
        it!=v.end() && !it->empty() ; it++) 
        //一定要将it!=v.end()写在前，否则会报越界错误！！
        cout<<*it<<endl;
}

注意

• 若使用了迭代器的循环体，不能向迭代器所属容器添加元素！！！
• 更改容器容量的操作会使当前迭代器失效！！！

迭代器运算

例如返回容器中最接近中间位置的一个迭代器，让另一个迭代器只处理前半位置，常用于二分搜索：

vector<int> vi(10, 5);
vector<int>::iterator it_mid = vi.begin() + vi.size()/2;
vector<int>::iterator it = vi.begin();
if (it < it_mid){
    //do something
}

迭代器之间的位置有自己的数据类型：difference_type，是带符号类型

使用Vector迭代器创建二分查找：

vector<char> v_alpha(){
    vector<char> a;
    char end = 'Z'+1;
    for (char i='A'; i!=end; ++i){
        a.push_back(i);
    }
    return a;
}

int main(){
    auto a = v_alpha();
    char target = 'F';
    int cnt = 0;
    auto b = a.begin(), e = a.end();
    auto mid = a.begin() + (e-b)/2;
    while(mid != e && *mid != target){
        cout<<"current value: "<<*mid <<endl;
        if(target < *mid) e = mid;
        else b = mid;
        mid = b+(e-b)/2;
        ++cnt;
    }
    cout<<"current value: "<<*mid <<", hit!"<<endl;
    cout<<"count: "<<cnt;
}