owned this note   changed 3 years ago  
Linked with GitHub

進階C++：

iterator

2021/12/17 電算社第十一堂社課

迭代器 iterator

一種類似指標的東東，和指標一樣存的是記憶體位置，使用方法和指標也差不多，通常使用vector時會跟著iterator一起使用，而非pointer

指標 v.s Iterator

種類

  • bidirectional iterator：可以前後移
    • 只能往前後移一格
    • 大部分不能隨機存取的資料結構(set)
  • random access iterator：可以亂跳
    • 可以往前後跳任意格
    • 可以相減算距離
    • 可以隨機存取的資料結構(vector deque)

函式庫

基本上可以使用iterator的資料結構，該資料型態的函式庫就有iterator
ex.




#include <vector>
#include <deque>
#include <set>

宣告



資料結構<type>::iterator i;
auto i = v.begin(); // 一定要賦值

用法

vector



















#include <iostream>
#include <vector>
using namespace std;
int main(){
    vector<int> v = {4,8,7,6,3};
    vector<int>::iterator i; // random access iterator
    // 或 auto i = v.begin();
    for(i = v.begin(); i != v.end(); i++){
        cout << *i << ' ';
    }
    cout << v.end() - v.begin(); // 5，即v.size()
    //輸出：4 8 7 6 3
    cout << endl << *(i - 1); //3
    cout << endl << *(i - 2); //6
    cout << endl << *(i - 3); //7
    return 0;
    
}

deque
















#include <iostream>
#include <deque>
using namespace std;
int main(){
    deque<int> dq = {4,8,7,6,3};
    deque<int>::iterator i = dq.begin(); 
    // random access iterator
    // auto i = dq.begin();
    
    cout << *i << '\n'; // 4
    cout << *(i + 1) << '\n'; // 8
    i++;
    cout << *(i + 2) << '\n'; // 6
    return 0;
}

set





















#include <iostream>
#include <set>
using namespace std;
int main(){
    set<int> s;
    for(int j = 0; j < 5; j++){
        s.insert(j);
    }
    set<int>::iterator i; //bidirectional iterator
    // auto i = s.begin();
    for(i = s.begin(); i != s.end(); i++){
        cout << *i << ' '; // 0 1 2 3 4
    }
    set<int>::iterator i2 = s.begin();
    cout << *i2 << '\n'; // 0
    //i2 += 2(會爆掉)
    i2++;
    cout << *i2 << '\n'; // 1
    return 0;
}

會用到iterator的function

  • sort
  • lower_bound
  • upper_bound











vector<int> a = {4, 8, 7, 6, 3};
sort(a.begin(), a.end()); // {3, 4, 6, 7, 8}

vector<int> b = {4, 8, 7, 6, 3};
sort(b.begin() + 2, b.end()); // {4, 8, 3, 6, 7}

vector<int> c = {4, 8, 7, 6, 3};
sort(c.begin() + 1, c.end() - 2); // {4, 7, 8, 6, 3}

vector<int> d = {4, 8, 7, 6, 3};
sort(d.begin() + 1, d.begin() + 3); // {4, 7, 8, 6, 3}
Select a repo