C++STL概述

一、STL基本概念

(1)泛型程式設計

• C++中有兩個方面體現重用：

  • 1.面向物件的思想：繼承和多型，標準類別庫
  • 2.泛型程式設計(generic programming) 的思想： 模板機制，以及標準模板庫 STL

• 泛型程式設計

  簡單地說就是使用模板的程式設計法，
  將一些常用的資料結構（比如鏈表，陣列，二叉樹）和演算法（比如排序，查找）寫成模板，以后則不論資料結構里放的是什么物件，演算法針對什么樣的物件，則都不必重新實作資料結構，重新撰寫演算法，

  • 標準模板庫 (Standard Template Library):
    一些常用資料結構和演算法的模板的集合，有了STL，不必再寫大多的標準資料結構和演算法，并且可獲得非常高的性能，

(2)STL中的基本的概念

• 容器：可容納各種資料型別的通用資料結構,是類模板
• 迭代器：可用于依次存取容器中元素，類似于指標
• 演算法：用來操作容器中的元素的函式模板

二、容器概述

物件被插入容器中時，被插入的是物件的一個復制品，許多演算法，比如排序，查找，要求對容器中的元素進行比較，有的容器本身就是排序的，所以，放入容器的物件所屬的類，往往還應該多載 == 和 < 運算子，

(1)順序容器

容器并非排序的，元素的插入位置同元素的值無關，有vector,deque,list 三種

• vector
  • vector 頭檔案 <vector>
  • 動態陣列，元素在記憶體連續存放，隨機存取任何元素都能在常數時間完成，在尾端增刪元素具有較佳的性能(大部分情況下是常數時間），
• deque
  • deque 頭檔案 <deque>
  • 雙向佇列，元素在記憶體連續存放，隨機存取任何元素都能在常數時間完成(但次于vector)，在兩端增刪元素具有較佳的性能(大部分情況下是常數時間），
• list
  • list 頭檔案 <list>
  • 雙向鏈表，元素在記憶體不連續存放，在任何位置增刪元素都能在常數時間完成，不支持隨機存取，

(2)關聯容器

1. 元素是排序的 .
2. 插入任何元素，都按相應的排序規則來確定其位置 .
3. 在查找時具有非常好的性能 .
4. 通常以平衡二叉樹方式實作，插入和檢索的時間都是 O(log(N)).

• set/multiset
  • set/multiset 頭檔案 <set>
  • set 即集合，set中不允許相同元素，multiset中允許存在相同的元素，
• map/multimap
  • map/multimap 頭檔案 <map>
  • map與set的不同在于map中存放的元素有且僅有兩個成員變數，一個名為first,另一個名為second, map根據first值對元素進行從小到大排序，并可快速地根據first來檢索元素，
  • map同multimap的不同在于是否允許相同first值的元素，

(3)容器配接器

• stack
  • stack :頭檔案 <stack>
  • 堆疊，是項的有限序列，并滿足序列中被洗掉、檢索和修改的項只能是最近插入序列的項（堆疊頂的項），后進先出，
• queue
  • queue 頭檔案 <queue>
  • 佇列，插入只可以在尾部進行，洗掉、檢索和修改只允許從頭部進行，先進先出，
• priority_queue
  • priority_queue 頭檔案 <queue>
  • 優先級佇列，最高優先級元素總是第一個出列

(4)順序容器和關聯容器中都有的成員函式

• begin 回傳指向容器中第一個元素的迭代器
• end 回傳指向容器中最后一個元素后面的位置的迭代器
• rbegin 回傳指向容器中最后一個元素的迭代器
• rend 回傳指向容器中第一個元素前面的位置的迭代器
• erase 從容器中洗掉一個或幾個元素
• clear 從容器中洗掉所有元素

(5)順序容器的常用成員函式

• front :回傳容器中第一個元素的參考
• back : 回傳容器中最后一個元素的參考
• push_back : 在容器末尾增加新元素
• pop_back : 洗掉容器末尾的元素
• erase :洗掉迭代器指向的元素(可能會使該迭代器失效），或洗掉一個區間，回傳被洗掉元素后面的那個元素的迭代器

三、迭代器

(1)迭代器基本概念

1. 用于指向順序容器和關聯容器中的元素
2. 迭代器用法和指標類似
3. 有const 和非 const兩種
4. 通過迭代器可以讀取它指向的元素
5. 通過非const迭代器還能修改其指向的元素

• 迭代器定義

  容器類名::iterator 變數名;
  

  容器類名::const_iterator 變數名;
  

• 迭代器訪問

  * 迭代器變數名
  

• 迭代器上可以執行 ++ 操作, 以使其指向容器中的下一個元素，如果迭代器到達了容器中的最后一個元素的后面，此時再使用它，就會出錯，類似于使用NULL或未初始化的指標一樣，

(2)迭代器示例

#include <vector>
#include <iostream>
using namespace std;
int main()
{
    vector<int> v; //一個存放int元素的陣列，一開始里面沒有元素
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::const_iterator i; //常量迭代器
    for (i = v.begin(); i != v.end(); ++i)
        cout << *i << ",";
    cout << endl;
    vector<int>::reverse_iterator r; //反向迭代器
    for (r = v.rbegin(); r != v.rend(); r++)
        cout << *r << ",";
    cout << endl;
    vector<int>::iterator j; //非常量迭代器
    for (j = v.begin(); j != v.end(); j++)
        *j = 100;
    for (i = v.begin(); i != v.end(); i++)
        cout << *i << ",";
}

這輸出結果：
1,2,3,4,
4,3,2,1,
100,100,100,1
00,

(3)迭代器分類

• 雙向迭代器
  若p和p1都是雙向迭代器，則可對p、p1可進行以下操作：

  代碼	意義
  ++p, p++	使p指向容器中下一個元素
  --p, p--	使p指向容器中上一個元素
  * p	取p指向的元素
  p = p1	賦值
  p == p1 , p!= p1	判斷是否相等、不等

• 隨機訪問迭代器
  若p和p1都是隨機訪問迭代器，則可對p、p1可進行以下操作：
  雙向迭代器的所有操作

  代碼	意義
  p += i	將p向后移動i個元素
  p -= i	將p向向前移動i個元素
  p + i	指向 p 后面的第i個元素的迭代器
  p - i	指向 p 前面的第i個元素的迭代器
  p[i]	p后面的第i個元素的參考
  p < p1, p <= p1, p > p1, p>= p1	相對位置
  p – p1	:p1和p之間的元素個數

(4)容器上的迭代器類別

四、演算法

(1)演算法簡介

1. 演算法就是一個個函式模板, 大多數在 中定義
2. STL中提供能在各種容器中通用的演算法，比如查找，排序等
3. 演算法通過迭代器來操縱容器中的元素，許多演算法可以對容器中的一個區域區間進行操作，因此需要兩個引數，一個是起始元素的迭代器，一個是終止元素的后面一個元素的迭代器，比如，排序和查找
4. 有的演算法回傳一個迭代器，比如 find() 演算法，在容器中查找一個元素，并回傳一個指向該元素的迭代器
5. 演算法可以處理容器，也可以處理普通陣列

(2)STL中“大”“小” 的概念

• 關聯容器內部的元素是從小到大排序的

• 有些演算法要求其操作的區間是從小到大排序的，稱為“有序區間演算法”

  例：binary_search

• 有些演算法會對區間進行從小到大排序，稱為“排序演算法”

  例： sort

• 還有一些其他演算法會用到“大”，“小”的概念
  使用STL時，在預設的情況下，以下三個說法等價：

  1)x比y小
  2)運算式“x<y”為真
  3)y比x大

(3)STL中“相等”的概念

• 等價概念有多種可能

  • “x和y相等”等價于“x==y為真”
  • “x和y相等”等價于“x小于y和y小于x同時為假”

• STL中“相等” 概念演示

  #include <iostream>
  #include <algorithm>
  using namespace std;
  class A
  {
      int v;
  
  public:
      A(int n) : v(n) {}
      bool operator<(const A &a2) const
      {
          //必須為常量成員函式
          cout << v << "<" << a2.v << "?" << endl;
          return false;
      }
      bool operator==(const A &a2) const
      {
          cout << v << "==" << a2.v << "?" << endl;
          return v == a2.v;
      }
  };
  int main()
  {
      A a[] =
          {A(1), A(2), A(3), A(4), A(5)};
      cout << binary_search(a, a + 4, A(9));
      //折半查找
      return 0;
  }
  

  輸出結果：
  3<9?
  2<9?
  1<9?
  9<1?
  1

【知識索引】【C++入門】