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 的替换时使用标准容器。