C++ 程式設計/STL

標準模板庫 (STL)

標準模板庫 (STL) 是 C++ 標準庫 的一部分，它提供了一組演算法、容器、迭代器和其他基本元件，這些元件以模板、類和函式的形式實現，對於擴充套件 C++ 的功能和標準化至關重要。 STL 的主要目標是透過強調效能和正確性來提供改進的實現標準化。

無需擔心您的陣列是否需要容納 257 條記錄，或因字串緩衝區溢位而噩夢連連，您可以享受 vector 和 string，它們可以自動擴充套件以容納更多記錄或字元。例如，vector 就像一個數組，區別在於 vector 的大小可以擴充套件以容納更多單元格，或者在需要時縮減。必須記住，STL 不會與 OOP 衝突，但本身不是面向物件的；特別是它不使用執行時多型性（即沒有虛擬函式）。

STL 的真正力量不在於其 容器 類，而在於它是一個框架，它結合了演算法和資料結構，使用迭代器進行間接操作，從而允許更高階演算法的通用實現有效地作用於各種形式的資料。舉個簡單的例子，相同的 std::copy 函式可用於將元素從一個數組複製到另一個數組，或複製檔案的位元組，或將 "text like this" 中以空格分隔的單詞複製到 std::vector<std::string> 等容器中。

 // std::copy from array a to array b
 int a[10] = { 3,1,4,1,5,9,2,6,5,4 };
 int b[10];
 std::copy(&a[0], &a[9], b);

 // std::copy from input stream a to an arbitrary OutputIterator
 template <typename OutputIterator>
 void f(std::istream &a, OutputIterator destination) {
   std::copy(std::istreambuf_iterator<char>(a),
             std::istreambuf_iterator<char>(),
             destination);
 }

 // std::copy from a buffer containing text, inserting items in
 // order at the back of the container called words.
 std::istringstream buffer("text like this");
 std::vector<std::string> words;
 std::copy(std::istream_iterator<std::string>(buffer),
           std::istream_iterator<std::string>(),
           std::back_inserter(words));
 assert(words[0] == "text");
 assert(words[1] == "like");
 assert(words[2] == "this");

歷史

Alexander Stepanov

C++ 標準庫整合了 STL 的一部分（由 SGI/惠普公司釋出為軟體庫）。C++ 標準模板庫的主要實現者是 Alexander Stepanov。

如今，我們稱被採用到 C++ 標準中的部分為 STL。ISO C++ 沒有指定標頭檔案內容，允許在標頭檔案中或真庫中實現 STL。

編譯器將已經包含一個實現作為 C++ 標準的一部分（例如，MS Visual Studio 使用 Dinkum STL）。所有實現都必須符合標準關於功能和行為的要求，但程式在所有主要硬體實現、作業系統和編譯器中的一致性也取決於 STL 實現的可移植性。它們還可能提供擴充套件功能或針對不同的設定進行最佳化。

有許多不同的 STL 實現，它們都基於語言標準，但仍彼此不同，這使得程式設計師對它透明，能夠實現程式碼庫的專業化和快速演進。有多種開源實現可用，可以參考這些實現。

STL 實現列表。

• 來自 gnu 的 libstdc++（以前是 libg++ 的一部分）
• SGI STL 庫 (http://www.sgi.com/tech/stl/) 免費 STL 實現。
• Rogue Wave 標準庫（惠普、SGI、SunSoft、西門子-尼克斯多夫）/Apache C++ 標準庫 (STDCXX)
• Dinkum STL 庫由 P.J. Plauger 編寫 (http://www.dinkumware.com/) 商業 STL 實現，被廣泛使用，因為它被微軟許可並在其共同維護，並且是隨 Visual Studio 附帶的 STL 實現。
• Apache C++ 標準庫 (http://stdcxx.apache.org/) （開源）
• STLport STL 庫 (http://www.stlport.com/) 開源且高度跨平臺的實現，基於 SGI 實現。

容器

我們將在本書的這一部分中討論的容器是標準名稱空間 (std::) 的一部分。它們都起源於 STL 的原始 SGI 實現。

序列容器

序列 - 比陣列更容易

序列類似於 C 陣列，但它們更易於使用。vector 通常是學習的第一個序列。其他序列 list 和雙端佇列與 vector 類似，但在某些特殊情況下效率更高。（它們的行為在迭代器在容器更改時保持有效性方面也存在重要差異；迭代器有效性是使用 C++ 中的容器時一個重要的，儘管有點高階的概念。）

• vector - "易於使用的陣列"
• list - 實際上是一個雙向連結串列
• deque - 雙端佇列（正確發音為 "deck"，常被誤讀為 "dee-queue"）

vector

vector 本身就是一個模板類，它是一個 序列容器，允許您輕鬆建立 動態陣列，用於儲存程式中幾乎任何資料型別或物件的元素（每個例項一種型別）。vector 類為您處理大多數記憶體管理。

由於 vector 包含連續的元素，因此它是用作舊式 C 樣式陣列的理想選擇，在這種情況下您需要儲存資料，並且是需要儲存動態資料作為陣列（在程式執行期間大小會發生變化）的理想選擇（舊式 C 樣式陣列無法做到這一點）。但是，與靜態陣列相比，vector 會產生非常小的開銷（取決於編譯器的質量），並且不能透過初始化列表進行初始化。

訪問 vector 的成員或追加元素所需的時間是固定的，與 vector 的大小無關，而查詢 vector 元素中的特定值或將元素插入 vector 所需的時間與其位置成正比（與大小相關）。

示例

/*
David Cary 2009-03-04
quick demo for wikibooks
*/

#include <iostream>
#include <vector>
using namespace std;

vector<int> pick_vector_with_biggest_fifth_element(vector<int> left,vector<int> right)
{
    if(left[5] < right[5])
    {
        return( right );
    }
    // else
    return left ;
}

int* pick_array_with_biggest_fifth_element(int * left,int * right)
{
    if(left[5] < right[5])
    {
        return( right );
    }
    // else 
    return left ;
}

int vector_demo(void)
{
    cout << "vector demo" << endl;
    vector<int> left(7);
    vector<int> right(7);

    left[5] = 7;
    right[5] = 8;
    cout << left[5] << endl;
    cout << right[5] << endl;
    vector<int> biggest(pick_vector_with_biggest_fifth_element( left, right ) );
    cout << biggest[5] << endl;

    return 0;
}

int array_demo(void)
{
    cout << "array demo" << endl;
    int left[7];
    int right[7];

    left[5] = 7;
    right[5] = 8;
    cout << left[5] << endl;
    cout << right[5] << endl;
    int * biggest =
        pick_array_with_biggest_fifth_element( left, right );
    cout << biggest[5] << endl;

    return 0;
}

int main(void)
{
    vector_demo();
    array_demo();
}

成員函式

vector 類模擬了 Container 概念，這意味著它具有 begin()、end()、size()、max_size()、empty() 和 swap() 方法。

• 資訊性
  • vector::front - 返回 vector 的第一個元素的引用。
  • vector::back - 返回 vector 的最後一個元素的引用。
  • vector::size - 返回向量中元素的數量。
  • vector::empty - 如果向量中沒有元素，則返回 true。
• 標準操作
  • vector::insert - 將元素插入向量（單個和範圍），將後面的元素向上移動。效率低下。
  • vector::push_back - 將元素追加（插入）到向量的末尾，如果需要，則為其分配記憶體。攤銷 O(1) 時間。
  • vector::erase - 從向量中刪除元素（單個和範圍），將後面的元素向下移動。效率低下。
  • vector::pop_back - 刪除向量的最後一個元素，（可能減少容量 - 通常不會減少，但這取決於特定的 STL 實現）。攤銷 O(1) 時間。
  • vector::clear - 刪除所有元素。但是請注意，如果資料元素是指向動態建立的記憶體的指標（例如，使用 new 運算子），則不會釋放該記憶體。
• 分配/大小修改
  • vector::assign - 用於刪除 源 向量 並將指定元素複製到空的 目標 向量 中。
  • vector::reserve - 如果需要，更改向量的容量（分配更多記憶體）。在許多 STL 實現中，容量只能增長，而不能減少。
  • vector::capacity - 返回向量的當前容量（分配的記憶體）。
  • vector::resize - 更改向量的大小。
• 迭代
  • vector::begin - 返回一個指向向量開始遍歷的迭代器。
  • vector::end - 返回一個指向向量末尾之後的迭代器。
  • vector::at - 返回對 向量 中指定位置的資料元素的引用，並進行邊界檢查。

vector<int> v;
for (vector<int>::iterator it = v.begin(); it!=v.end(); ++it/* increment operand is used to move to next element*/) {
    cout << *it << endl;
}

vector::迭代器

std::vector<T> 提供隨機訪問迭代器；與所有容器一樣，對迭代器的主要訪問是透過 begin() 和 end() 成員函式。這些函式針對常量和非常量容器進行了過載，分別返回型別為 std::vector<T>::const_iterator 和 std::vector<T>::iterator 的迭代器。

vector 示例

 /* Vector sort example */
 #include <iostream>
 #include <vector>
 
 int main()
 {
         using namespace std;
  
         cout << "Sorting STL vector, \"the easier array\"... " << endl;
         cout << "Enter numbers, one per line.  Press ctrl-D to quit." << endl;
 
         vector<int> vec; 
         int tmp;
         while (cin>>tmp) {
                 vec.push_back(tmp);
         }
 
         cout << "Sorted: " << endl;
         sort(vec.begin(), vec.end());   
         int i = 0;
         for (i=0; i<vec.size(); i++) {
                 cout << vec[i] << endl;;
         }
 
         return 0;
 }

對sort的呼叫實際上呼叫了函式模板std::sort的例項化，它將對由兩個隨機訪問迭代器指定的任何半開範圍起作用。

如果您想使上面的程式碼更“STLish”，您可以用以下方式編寫此程式

 #include <iostream>
 #include <vector>
 #include <algorithm>
 #include <iterator>
 
 int main()
 {
        using namespace std;
 
        cout << "Sorting STL vector, \"the easier array\"... " << endl;
        cout << "Enter numbers, one per line.  Press ctrl-D to quit." << endl;
 
        istream_iterator<int> first(cin);
        istream_iterator<int> last;
        vector<int> vec(first, last);
 
        sort(vec.begin(), vec.end());
 
        cout << "Sorted: " << endl;
 
        copy(vec.begin(), vec.end(), ostream_iterator<int>(cout, "\n"));
 
        return 0;
 }

連結串列

STL 提供了一個名為 list 的類模板（是標準名稱空間 (std::) 的一部分），它實現了一個非侵入式雙向連結串列。連結串列可以在恆定時間內在中間插入或刪除元素，但沒有隨機訪問。std::list 的一個有用特性是，只要該專案保留在列表中，對插入到列表中的專案的引用、指標和迭代器就會保持有效。

list 示例

 /* List example - insertion in a list */
 #include <iostream>
 #include <algorithm>
 #include <iterator>
 #include <list>

 void print_list(std::list<int> const& a_filled_list)
 {
        using namespace std;

        ostream_iterator<int> out(cout, "  ");
        copy(a_filled_list.begin(), a_filled_list.end(), out);
 }

 int main()
 {
	 std::list<int> my_list;

	 my_list.push_back(1);
	 my_list.push_back(10);
	 print_list(my_list); //print : 1 10

	 std::cout << std::endl;

	 my_list.push_front(45);
	 print_list(my_list); //print : 45 1 10

	 return 0;
 }

關聯容器（鍵和值）

這種型別的容器使用鍵值指向容器中的每個元素，從而簡化了程式設計師搜尋容器的過程。與其遍歷陣列或向量元素來查詢特定元素，您可以簡單地請求 people["tero"]。與向量和其他容器一樣，關聯容器可以擴充套件以容納任意數量的元素。

對映和多對映

map 和 multimap 是關聯容器，它們管理鍵/值對作為元素，如上所示。每個容器的元素將使用實際的鍵作為排序標準自動排序。兩者之間的區別在於對映不允許重複項，而多對映則允許。

• map - 唯一的鍵
• multimap - 可以多次使用相同的鍵
• set - 唯一的鍵是值
• multiset - 鍵是值，可以多次使用相同的鍵

  /* Map example - character distribution  */
  #include <iostream>
  #include <map>
  #include <string>
  #include <cctype>
 
  using namespace std;
 
  int main()
  {
          /* Character counts are stored in a map, so that 
           * character is the key.
           * Count of char a is chars['a']. */
          map<char, long> chars;
 
          cout << "chardist - Count character distributions" << endl;
          cout << "Type some text. Press ctrl-D to quit." << endl;
          char c;
          while (cin.get(c)) {
                  // Upper A and lower a are considered the same 
                  c=tolower(static_cast<unsigned char>(c));
                  chars[c]=chars[c]+1; // Could be written as ++chars[c];
          }
 
          cout << "Character distribution: " << endl;
            
          string alphabet("abcdefghijklmnopqrstuvwxyz");
          for (string::iterator letter_index=alphabet.begin(); letter_index != alphabet.end(); letter_index++) {
                  if (chars[*letter_index] != 0) {
                          cout << char(toupper(*letter_index))
                               << ":" << chars[*letter_index]
                               << "\t" << endl; 
                  }
          }
          return 0;
  }

容器介面卡

• stack - 後進先出 (LIFO)
• queue - 先進先出 (FIFO)
• 優先順序佇列

迭代器

C++ 的迭代器是 STL 的基礎之一。其他語言中也存在迭代器，但 C++ 使用了不同形式的迭代器，有優點也有缺點。

在 C++ 中，迭代器是概念而不是特定型別，它們是指標的泛化，作為容器使用的抽象。迭代器根據其屬性（如遍歷屬性）進一步細分。

迭代器的基本思想是提供一種方法來遍歷一些物件集合的概念。

一些（重疊的）迭代器類別包括

• 單迭代器
• 無效迭代器
• 隨機訪問迭代器
• 雙向迭代器
• 正向迭代器
• 輸入迭代器
• 輸出迭代器
• 可變迭代器

一對迭代器 [begin, end) 用於定義一個半開範圍，其中包括從 begin 到 end 標識的元素，但 end 標識的元素除外。作為特殊情況，對於任何有效的迭代器 x，半開範圍 [x, x) 為空。

C++ 中最原始的迭代器示例（也可能是其語法的靈感來源）是內建指標，它們通常用於迭代陣列中的元素。

遍歷容器

訪問（但不能修改）容器中的每個元素組型別C<T>使用迭代器。

 for (
      typename C<T>::const_iterator iter = group.begin();
      iter != group.end();
      ++iter
     )
 {
     T const &element = *iter;
 
     // access element here
 }

請注意 typename 的用法。它告知編譯器 'const_iterator' 是一個型別，而不是一個靜態成員變數。（它僅在模板程式碼中必要，實際上在 C++98 中，在常規的非模板程式碼中它是無效的。這可能會在 C++ 標準的下一個修訂版中發生變化，從而始終允許上面的 typename。）

修改容器中的每個元素組型別C<T>使用迭代器。

 for (
      typename C<T>::iterator iter = group.begin();
      iter != group.end();
      ++iter
     )
 {
     T &element = *iter;
 
     // modify element here
 }

在遍歷容器時修改容器本身時，某些容器（如 vector）需要小心，以確保迭代器不會失效並最終指向無效元素。例如，而不是

  for (i = v.begin(); i != v.end(); ++i) {
    ...
    if (erase_required) {
      v.erase(i);
    }
  }

執行

  for (i = v.begin(); i != v.end(); ) {
    ...
    if (erase_required) {
        i = v.erase(i);
    } else {
        ++i;
    }
  }

該erase()成員函式返回下一個有效的迭代器，或者end()，從而結束迴圈。請注意，++i在erase()被呼叫時不會被執行。

仿函式

仿函式或函式物件，是一個具有 operator () 的物件。仿函式的重要性在於它們可以在許多 C++ 函式可以使用的上下文中使用，同時還能維護狀態資訊。除了迭代器之外，仿函式是 STL 利用的最基本的概念之一。

STL 提供了許多預先構建的仿函式類；例如，std::less 通常用於為需要確定兩個物件中哪一個在“前面”的演算法指定預設比較函式。

 #include <vector>
 #include <algorithm>
 #include <iostream>

 // Define the Functor for AccumulateSquareValues
 template<typename T>
 struct AccumulateSquareValues
 {
     AccumulateSquareValues() : sumOfSquares()
     {
     }
     void operator()(const T& value)
     {
         sumOfSquares += value*value;
     }
     T Result() const
     {
         return sumOfSquares;
     }
     T sumOfSquares;
 };

 std::vector<int> intVec;
 intVec.reserve(10);
 for( int idx = 0; idx < 10; ++idx )
 {
     intVec.push_back(idx);
 }
 AccumulateSquareValues<int> sumOfSquare = std::for_each(intVec.begin(), 
                                                         intVec.end(), 
                                                         AccumulateSquareValues<int>() );
 std::cout << "The sum of squares for 1-10 is " << sumOfSquare.Result() << std::endl;

 // note: this problem can be solved in another, more clear way:
 // int sum_of_squares = std::inner_product(intVec.begin(), intVec.end(), intVec.begin(), 0);

演算法

STL 還提供了一些有用的演算法，以 _模板函式_ 的形式提供，這些函數借助迭代器概念來操作 STL 容器（或派生類）。

STL 演算法並不侷限於 STL 容器，例如

#include <algorithm>

  int array[10] = { 2,3,4,5,6,7,1,9,8,0 };

  int* begin = &array[0];
  int* end = &array[0] + 10;

  std::sort(begin, end);// the sort algorithm will work on a C style array

帶有 _if 字尾的演算法

帶有 _copy 字尾的演算法

• 非修改演算法
• 修改演算法
• 移除演算法
• 變異演算法
• 排序演算法
• 排序範圍演算法
• 數值演算法

排序和相關操作

最小值和最大值

標準庫提供了函式模板 min 和 max，它們分別返回兩個引數的最小值和最大值。每個模板都有一個過載版本，允許您自定義值的比較方式。

template<class T>
const T& min(const T& a, const T& b);

template<class T, class Compare>
const T& min(const T& a, const T& b, Compare c);

template<class T>
const T& max(const T& a, const T& b);

template<class T, class Compare>
const T& max(const T& a, const T& b, Compare c);

如何使用 Compare 型別引數的示例

 #include <iostream>
 #include <algorithm>
 #include <string>

 class Account
 {
	 private :
         std::string owner_name;
	 int credit;
	 int potential_credit_transfer;

	 public :
	 Account(){}
	 Account(std::string name, int initial_credit, int initial_credit_transfer) :
	 	 owner_name(name),
	         credit(initial_credit),
	         potential_credit_transfer(initial_credit_transfer)
	 {}

	 bool operator<(Account const& account) const { return credit < account.credit; }

	 int potential_credit() const { return credit + potential_credit_transfer; }

	 std::string const& owner() const { return owner_name; }
 };

 struct CompareAccountCredit
 {
	 bool operator()(Account const& account1, Account const& account2) const 
         { return account1 < account2; }
 };

 struct CompareAccountPotentialCredit
 {
	 bool operator()(Account const& account1, Account const& account2) const 
         { return account1.potential_credit() < account2.potential_credit(); }
 };

 int main()
 {
	 Account account1("Dennis Ritchie", 1000, 250), account2("Steeve Jobs", 500, 10000), 
         result_comparison;

	 result_comparison = std::min(account1, account2, CompareAccountCredit());
	 std::cout << "min credit of account is : " + result_comparison.owner() << std::endl;

	 result_comparison = std::min(account1, account2, CompareAccountPotentialCredit());
	 std::cout << "min potential credit of account is : " + result_comparison.owner() << std::endl;

	 return 0;
 }

分配器

分配器由標準 C++ 庫（特別是 STL）使用，以允許對記憶體分配策略進行引數化。

分配器的主題有些晦澀，大多數應用程式軟體開發人員可以安全地忽略它。所有允許指定分配器的標準庫構造都有一個預設分配器，如果使用者沒有提供，則使用該分配器。

如果程式碼的記憶體使用方式非常特殊，以至於在使用通用預設分配器時會導致效能問題，則自定義分配器會很有用。在其他情況下，預設分配器也不適用，例如在實現全域性運算子 new 和 delete 的替換時使用標準容器。