天天看點

STL疊代器擴充卡

通過學習 C++ STL 标準庫中的容器我們知道,無論是序列式容器還是關聯式容器(包括哈希容器),要想周遊容器中存儲的資料,就隻能用使用該容器模闆類中提供的疊代器。

STL疊代器擴充卡種類

反向疊代器(reverse_iterator)

又稱“逆向疊代器”,其内部重新定義了遞增運算符(++)和遞減運算符(–),專門用來實作對容器的逆序周遊。

安插型疊代器(inserter或者insert_iterator)

通常用于在容器的任何位置添加新的元素,需要注意的是,此類疊代器不能被運用到元素個數固定的容器(比如 array)上。

流疊代器(istream_iterator / ostream_iterator)

流緩沖區疊代器(istreambuf_iterator / ostreambuf_iterator)

輸入流疊代器用于從檔案或者鍵盤讀取資料;相反,輸出流疊代器用于将資料輸出到檔案或者螢幕上。

輸入流緩沖區疊代器用于從輸入緩沖區中逐個讀取資料;輸出流緩沖區疊代器用于将資料逐個寫入輸出流緩沖區。

移動疊代器(move_iterator)

此類型疊代器是 C++ 11 标準中新添加的,可以将某個範圍的類對象移動到目标範圍,而不需要通過拷貝去移動。

示範了用反向疊代器擴充卡周遊 list 容器的實作過程:

#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> values{ 1,2,3,4,5 };
    //找到周遊的起點和終點,這裡無需糾結定義反向疊代器的文法,後續會詳細講解
    std::reverse_iterator<std::list<int>::iterator> begin = values.rbegin();
    std::reverse_iterator<std::list<int>::iterator> end = values.rend();
    while (begin != end) {
        cout << *begin << " ";
        //注意,這裡是 ++,因為反向疊代器内部互換了 ++ 和 -- 的含義
        ++begin;
    }
    return 0;
}
           

反向疊代器擴充卡(reverse_iterator)

反向疊代器擴充卡(reverse_iterator),可簡稱為反向疊代器或逆向疊代器,常用來對容器進行反向周遊,即從容器中存儲的最後一個元素開始,一直周遊到第一個元素。

值得一提的是,反向疊代器底層可以選用雙向疊代器或者随機通路疊代器作為其基礎疊代器。不僅如此,通過對 ++(遞增)和 --(遞減)運算符進行重載,使得:

  • 當反向疊代器執行 ++ 運算時,底層的基礎疊代器實則在執行 – 操作,意味着反向疊代器在反向周遊容器;
  • 當反向疊代器執行 – 運算時,底層的基礎疊代器實則在執行 ++ 操作,意味着反向疊代器在正向周遊容器。

實作反向疊代器的模闆類定義在 頭檔案,并位于 std 命名空間中。

#include <iterator>
using namespace std;
           
STL疊代器擴充卡

其中,begin 和 end 表示基礎疊代器,r(begin) 和 r(end) 分别表示有 begin 和 end 獲得的反向疊代器。

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
    //建立并初始化一個 vector 容器
    std::vector<int> myvector{ 1,2,3,4,5,6,7,8 };
    //建立并初始化一個反向疊代器
    std::reverse_iterator<std::vector<int>::iterator> my_reiter(myvector.rbegin());//指向 8
    cout << *my_reiter << endl;// 8
    cout << *(my_reiter + 3) << endl;// 5
    cout << *(++my_reiter) << endl;// 7
    cout << my_reiter[4] << endl;// 3
    return 0;
}
           

除此之外,reverse_iterator 模闆類還提供了 base() 成員方法,該方法可以傳回目前反向疊代器底層所使用的基礎疊代器

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
    //建立并初始化一個 vector 容器
    std::vector<int> myvector{ 1,2,3,4,5,6,7,8 };
    //建立并初始化反向疊代器 begin,其指向元素 1 之前的位置
    std::reverse_iterator<std::vector<int>::iterator> begin(myvector.begin());
    //建立并初始化反向疊代器 begin,其指向元素 8
    std::reverse_iterator<std::vector<int>::iterator> end(myvector.end());
    //begin底層基礎疊代器指向元素 1,end底層基礎疊代器指向元素 8 之後的位置
    for (auto iter = begin.base(); iter != end.base(); ++iter) {
        std::cout << *iter << ' ';
    }
    return 0;
}
           

STL 插入疊代器擴充卡(insert_iterator)

back_insert_iterator 疊代器定義在 頭檔案,并位于 std 命名空間中

#include <iterator>
using namespace std;
           

和反向疊代器不同,back_insert_iterator 插入疊代器的定義方式僅有一種,其文法格式如下:

其中,Container 用于指定插入的目标容器的類型;container 用于指定具體的目标容器。

舉個例子:

//建立一個 vector 容器
std::vector<int> foo;
//建立一個可向 foo 容器尾部添加新元素的疊代器
std::back_insert_iterator< std::vector<int> > back_it(foo);
           

在此基礎上,back_insert_iterator 疊代器模闆類中還對指派運算符(=)進行了重載,借助此運算符,我們可以直接将新元素插入到目标容器的尾部。

#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main() {
    //建立一個 vector 容器
    std::vector<int> foo;
    //建立一個可向 foo 容器尾部添加新元素的疊代器
    std::back_insert_iterator< std::vector<int> > back_it(foo);
    //将 5 插入到 foo 的末尾
    back_it = 5;
    //将 4 插入到目前 foo 的末尾
    back_it = 4;
    //将 3 插入到目前 foo 的末尾
    back_it = 3;
    //将 6 插入到目前 foo 的末尾
    back_it = 6;
    //輸出 foo 容器中的元素
    for (std::vector<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}
           

程式執行結果為:

5 4 3 6

STL front_insert_iterator疊代器

和 back_insert_iterator 正好相反,front_insert_iterator 疊代器的功能是向目标容器的頭部插入新元素。

并且,由于此類型疊代器的底層實作需要借助目标容器的 push_front() 成員方法,這意味着,隻有包含 push_front() 成員方法的容器才能使用該類型疊代器。

C++ STL 标準庫中,提供有 push_front() 成員方法的容器,僅有 deque、list 和 forward_list。

front_insert_iterator 疊代器定義在 頭檔案,并位于 std 命名空間中

#include <iterator>
using namespace std;
           
#include <iostream>
#include <iterator>
#include <forward_list>
using namespace std;
int main() {`在這裡插入代碼片`
    //建立一個 forward_list 容器
    std::forward_list<int> foo;
    //建立一個前插入疊代器
    //std::front_insert_iterator< std::forward_list<int> > front_it(foo);
    std::front_insert_iterator< std::forward_list<int> > front_it = front_inserter(foo);
    //向 foo 容器的頭部插入元素
    front_it = 5;
    front_it = 4;
    front_it = 3;
    front_it = 6;
    for (std::forward_list<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}
           

程式執行結果為:

6 3 4 5

STL insert_iterator疊代器

需要調用目标容器的 insert() 成員方法。但幸運的是,STL 标準庫中所有容器都提供有 insert() 成員方法,是以 insert_iterator 是唯一可用于關聯式容器的插入疊代器。

insert_iterator 疊代器也定義在 頭檔案,并位于 std 命名空間中

#include <iterator>
using namespace std;
           

不同之處在于,定義 insert_iterator 類型疊代器的文法格式如下:

#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int main() {
    //初始化為 {5,5}
    std::list<int> foo(2,5);
    //定義一個基礎疊代器,用于指定要插入新元素的位置
    std::list<int>::iterator it = ++foo.begin();
    //建立一個 insert_iterator 疊代器
    //std::insert_iterator< std::list<int> > insert_it(foo, it);
    std::insert_iterator< std::list<int> > insert_it = inserter(foo, it);
    //向 foo 容器中插入元素
    insert_it = 1;
    insert_it = 2;
    insert_it = 3;
    insert_it = 4;
    //輸出 foo 容器存儲的元素
    for (std::list<int>::iterator it = foo.begin(); it != foo.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}
           

程式執行結果為:

5 1 2 3 4 5

疊代器并不是都可以進行加減

疊代器實質上是一個指針,但是,并不是所有的容器的疊代器可以支援加減操作。

能進行算術運算的疊代器隻有随機通路疊代器,要求容器元素存儲在連續記憶體空間内,

即vector、string、deque的疊代器是有加減法的;

而map、set、multimap、multiset、list的疊代器是沒有加減法的。他們僅支援++itr、–itr這些操作。

std::vector<int>::iterator my_reiter1(myvector.begin());
std::vector<int>::iterator my_reiter2(myvector.end());
int size = my_reiter2 - my_reiter1;
cout << size << " ";//5
           

it++與++it的差別

在STL中的容器使用疊代器進行周遊時,可以有it++與++it的效果是相同的,周遊的次數也是相同的,但是在STL中效率卻不同:

++it(或–it)傳回的是引用。

it++(或it–)傳回的是臨時對象。

因為iterator是類模闆,使用it++這種形式要傳回一個無用的臨時對象,而it++是函數重載,是以編譯器無法對其進行優化,是以每周遊一個元素,你就建立并銷毀了一個無用的臨時對象。