STL 实用指南

• 下载源代码 4.12 KB

引言

STL（Standard Template Library，标准模板库）是当今 C++ 程序员的一项重要技能。我必须说，它需要一段时间来适应，也就是说，学习曲线相当陡峭，而且一些使用的名称并不直观（可能是因为所有好的名称都被用完了）。好处是，一旦学会，它们将为您省去很多麻烦。与 MFC 容器相比，它们更加灵活和强大。

列出的优点

• 可以轻松地进行排序和搜索
• 它们更安全，更容易调试
• 您可以理解 UNIX 开发者编写的代码。
• 这是您简历中可以添加的另一个缩写。

背景

本指南旨在帮助读者在计算机科学这个充满挑战的领域快速入门，而无需深入研究 STL 开发者为自娱自乐而创造的海量术语和枯燥的精确定义。

Using the Code

这里的代码主要是对 STL 实际用法的指导。

定义

• 模板 - 类的宏（以及结构、数据类型和函数）。有时也称为“饼干模具”。正式名称也叫“泛型”（generic）——类的模板称为泛型类。函数的模板称为，请稍等，泛型函数。
• STL - 标准模板库，由一群聪明人编写的模板，现在被所有 C++ 标准语言的一部分人使用。
• 容器 - 保存数据的类。STL 的例子有 vector、set、map、multimap 和 deque。
• Vector - 您的基本数组模板。它是一个容器。
• 迭代器 - 指向 STL 容器中元素的指针的专用术语。它还能做其他事情。

Hello World 程序

我一直想写一个，这是我宝贵的 24K 纯金机会：一个 hello world 程序。这个程序将一个字符字符串转换为字符向量，然后逐个字符地显示字符串。Vector 是您最普通的、类似数组的模板。可能，STL 容器中有大约一半是 vector，所以如果您理解了这个程序，您就掌握了 STL 的一半。

// Program: Vector Demo 1
// Purpose: To demonstrate STL vectors

// #include "stdafx.h" - include if you use pre compiled headers
#include <vector>  // STL vector header. There is no ".h"
#include <iostream>  // for cout
using namespace std;  // Ensure that the namespace is set to std

char* szHW = "Hello World";  
// This is - as we all know - a character array, 
// terminated with a null character

int main(int argc, char* argv[])
{
  vector <char> vec;  // A vector (STL array) of characters

  // Define an iterator for a vector of characters - this is always 
  // scoped to within the template
  vector <char>::iterator vi;

  // Initialize the character vector, loop through the string, 
  // placing the data in the vector character by character until 
  // the terminating NULL is reached
  char* cptr = szHW;  // Start a pointer on the Hello World string
  while (*cptr != '\0')
  {  vec.push_back(*cptr);  cptr++;  }
  // push_back places the data on the back of the vector 
  // (otherwise known as the end of the vector)

  // Print each character now stored in the STL array to the console
  for (vi=vec.begin(); vi!=vec.end(); vi++)  
  // This is your standard STL for loop - usually "!=" 
  // is used in stead of "<"
  // because "<" is not defined for some containers. begin() 
  // and end() retrieve iterators 
  // (pointers) to the beginning of the vector and to the end of vector
  {  cout << *vi;  }  // Use the indirection operator 
           // (*) to extract the data from the iterator
  cout << endl;  // No more "\n"

  return 0;
}

push_back 是将数据放入 vector 或 deque 的标准函数。insert 是一个类似的函数，功能大致相同，并且适用于所有容器，但更复杂。end() 实际上是“结束点加一”，允许循环正常工作——它实际上指向数据范围之外的点。这就像在常规循环中，您会说 for (i=0; i<6; i++) {ar[i] = i;} —— ar[6] 不存在，但它在循环中从未被访问到，所以没关系。

STL 烦恼 #1

STL 最早的烦恼之一就是它。用数据初始化它比 C/C++ 数组更困难。您基本上必须逐个元素进行初始化，或者先初始化一个数组然后进行转换。我理解人们正在为此努力。

// Program: Initialization Demo
// Purpose: To demonstrate initialization of STL vectors

#include <cstring>  // same as <string.h>
#include <vector>
using namespace std;

int ar[10] = {  12, 45, 234, 64, 12, 35, 63, 23, 12, 55  };
char* str = "Hello World";

int main(int argc, char* argv[])
{
  vector <int> vec1(ar, ar+10);
  vector <char> vec2(str, str+strlen(str));
  return 0;
}

在编程中，完成同一项任务有很多种方法。填充 vector 的另一种方法是使用更熟悉的方括号，如下所示：

// Program: Vector Demo 2
// Purpose: To demonstrate STL vectors with
// counters and square brackets

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

char* szHW = "Hello World";
int main(int argc, char* argv[])
{
  vector <char> vec(strlen(sHW)); 
  // The argument initializes the memory footprint
  int i, k = 0;
  char* cptr = szHW;
  while (*cptr != '\0')
  {  vec[k] = *cptr;  cptr++;  k++;  }
  for (i=0; i<vec.size(); i++)
  {  cout << vec[i];  }
  cout << endl;
  return 0;
}

这个例子更简洁，但它给您的迭代器控制更少，并且有一个额外的整数计数器，您必须显式设置内存占用。

命名空间

与 STL 紧密相关的是命名空间的概念。STL 定义在 std 命名空间内。有 3 种方式可以指定它：

1. 在所有文件的顶部，但低于头文件的地方使用该命名空间。

   using namespace std;

   这对于简单的项目来说是最简单也是最好的，它将您限制在 std 命名空间内，任何您添加的内容都会被错误地放入 std 命名空间（我认为这样做是要下地狱的）。

2. 在每次使用前指定每个模板（像原型声明一样）。

   using std::cout;
   using std::endl;
   using std::flush;
   using std::set;
   using std::inserter;

   这稍微有些繁琐，但对于将要使用的函数来说是一个很好的助记符，并且您可以轻松地与其他命名空间进行交叉使用。

3. 每次使用 std 命名空间中的模板时，请使用 std 作用域限定符。

   typedef std::vector<std::string> VEC_STR;

   这很繁琐，但如果您混合使用大量命名空间，这是最好的方法。一些 STL 狂热者总是使用这种方法，并称任何不这样做的人是邪恶的。有些人会创建宏来简化问题。

此外，您可以在任何作用域内放置 using namespace std，例如，在函数的顶部或在控制循环内。

一些技巧

要避免在调试模式下出现一个恼人的错误代码，请使用以下编译器指令：

#pragma warning(disable: 4786)

另一个陷阱是：您必须确保在尖括号和名称之间有空格。这是因为 >> 是位移运算符，所以

vector <list<int>> veclis;

将会导致错误。相反，应该写成

vector <list <int> > veclis;

以避免编译错误。

另一个容器 - Set

这是从 MS 帮助文件中摘录的关于 set 的解释：“模板类描述了一个控制着类型为 const Key 的可变长度元素序列的对象。每个元素既充当排序键又充当值。该序列的表示方式允许在对序列中任意元素进行查找、插入和删除操作时，操作次数与元素数量成对数关系（对数时间）。此外，插入元素不会使任何迭代器失效，删除元素只会使指向被删除元素的迭代器失效。”

另一种更实用的定义是：Set 是一种包含所有唯一值的容器。这对于需要收集某个值出现次数的情况很有用。它按照实例化 set 时指定的顺序进行排序。如果您需要存储带有键/值对的数据，那么 map 是更好的选择。Set 被组织成一个链表，在插入和删除方面比 vector 快，但在搜索和末尾添加方面稍慢。

一个示例程序是：

// Program: Set Demo
// Purpose: To demonstrate STL sets

#include <string>
#include <set>
#include <iostream>
using namespace std;

int main(int argc, char* argv[])
{
  set <string> strset;
  set <string>::iterator si;
  strset.insert("cantaloupes");
  strset.insert("apple");
  strset.insert("orange");
  strset.insert("banana");
  strset.insert("grapes");
  strset.insert("grapes");  
   // This one overwrites the previous occurrence
  for (si=strset.begin(); si!=strset.end(); si++)  
  {  cout << *si << " ";  }
  cout << endl;
  return 0;
}

// Output: apple banana cantaloupes grapes orange

如果您想成为 STL 的狂热者，您也可以将程序中的输出循环替换为以下行：

copy(strset.begin(), strset.end(), ostream_iterator<string>(cout, " "));

虽然有指导意义，但我个人认为这不够清晰，并且容易出错。如果您看到它，您现在就应该知道它的作用了。

所有 STL 容器

容器早于模板存在，是计算机科学的概念，已被整合到 STL 中。以下是 STL 实现的七种容器。

• vector - 您的标准安全数组。它只在“前端”扩展。
• deque - 功能上与 vector 相同。内部结构不同。它可以从前端和后端进行扩展。
• list - 只能一次向前遍历一个步骤。如果您已经熟悉列表的概念，STL list 是双向链表（包含指向前一个和后一个值的指针）。
• set - 包含已排序的唯一值。
• map - 已排序的值对集合，其中一个值是排序和搜索发生的键，另一个值是从容器中检索到的值。例如，代替 ar[43] = "overripe"，map 允许您这样做 ar["banana"] = "overripe"。因此，如果您想绘制以全名作为键的信息很容易实现。
• multiset - 与 set 相同，但不一定包含唯一值。
• multimap - 与 map 相同，但不一定包含唯一的键。

注意：如果您正在阅读 MFC 帮助文件，您还会遇到每个容器的效率说明。例如（log n * n）的插入时间。除非您处理大量数据，否则您应该忽略这一点。如果您开始注意到明显的延迟或处理对时间敏感的任务，那么您应该更多地了解各种容器的正确效率。

如何将 Map 与某个类一起使用

Map 是一个使用键来获取值的模板。

另一个问题是，您将希望使用自己的类而不是数据类型，例如到目前为止使用的 int。要创建一个“模板就绪”的类，您必须确保该类包含特定的成员函数和运算符。基本要求是：

• 默认构造函数（通常为空）
• 复制构造函数
• 重载“=”

您将根据特定模板的要求重载更多运算符，例如，如果您打算创建一个类作为 map 的键，您将不得不重载关系运算符。但这又是另一回事了。

// Program: Map Own Class
// Purpose: To demonstrate a map of classes

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

class CStudent
{
public :
  int nStudentID;
  int nAge;
public :
  // Default Constructor - Empty
  CStudent()  {  }
  // Full constructor
  CStudent(int nSID, int nA)  {  nStudentID=nSID; nAge=nA;  }
  // Copy constructor
  CStudent(const CStudent& ob)  
    {  nStudentID=ob.nStudentID; nAge=ob.nAge;  }
  // Overload =
  void operator = (const CStudent& ob)  
    {  nStudentID=ob.nStudentID; nAge=ob.nAge;  }
};

int main(int argc, char* argv[])
{
  map <string, CStudent> mapStudent;

  mapStudent["Joe Lennon"] = CStudent(103547, 22);
  mapStudent["Phil McCartney"] = CStudent(100723, 22);
  mapStudent["Raoul Starr"] = CStudent(107350, 24);
  mapStudent["Gordon Hamilton"] = CStudent(102330, 22);

  // Access via the name
  cout << "The Student number for Joe Lennon is " << 
    (mapStudent["Joe Lennon"].nStudentID) << endl;

  return 0;
}

TYPEDEF

如果您喜欢使用 typedef，这是一个示例：

typedef set <int> SET_INT;
typedef SET_INT::iterator SET_INT_ITER

一种惯例是将它们命名为大写字母并带下划线。

ANSI / ISO 字符串

ANSI/ISO 字符串通常在 STL 容器中使用。这是您的标准字符串类，虽然广受赞誉，但缺乏格式化语句。您必须改用 << 和 iostream 代码（dec、width 等）来将您的字符串组合起来。

必要时，使用 c_str() 来检索指向字符的指针。

迭代器

我曾说过迭代器是“指针”，但还有更多。它们看起来像指针，行为也像指针，但实际上它们是被嵌入的，其中间接运算符（一元 *）和 -> 被重载以从容器中返回一个值。将它们存储很长时间是一个坏主意，因为一旦将值添加到容器或从容器中移除，它们通常就会失效。在这方面，它们有点像句柄。普通的迭代器可以被修改，以便容器可以以不同的方式遍历。

• iterator - 对于除 vector 之外的任何容器，您只能一次向前一步遍历容器。也就是说，您只能使用 ++ 运算符，而不能对它使用 -- 或 += 运算符。仅对于 vector，您可以使用 +=、--、-=、++ 以及所有比较运算符 <、<=、>、>=、==、!=。
• reverse_iterator - 如果您想在非 vector 容器中向后而不是向前遍历，请将 iterator 替换为 reverse_iterator，将 begin() 替换为 rbegin()，将 end() 替换为 rend()，此时 ++ 将会向后遍历。
• const_iterator - 一个前向迭代器，它返回一个 const 值。如果您想清楚地表明它指向一个只读值，请使用此项。
• const_reverse_iterator - 一个后向迭代器，它返回一个 const 值。

Set 和 Map 中的排序顺序

模板除了值的类型之外，还有其他参数。您还可以传递回调函数（称为谓词——这是一个接收一个参数并返回 bool 值的函数）。例如，假设您想要一个自动按升序排序的字符串集合。您只需像这样创建一个 set 类：

set <int, greater<int> > set1

greater <int> 是另一个用于函数（泛型函数）的模板，它用于在值被放置到容器中时对其进行排序。如果您希望 set 按降序排序，您应该这样写：

set <int, less<int> > set1

在许多其他情况下，您必须将谓词作为参数传递给 STL 类，在下面描述的算法中。

STL 烦恼 #2 - 冗长的错误消息

模板名称会为编译器进行展开，因此当编译器遇到问题时，它会输出非常冗长且难以阅读的错误消息。我还没有找到很好的解决办法。最好的方法是培养在错误代码的末尾查找和关注解释性说明的能力。另一个相关的烦恼：如果您双击模板错误，它会带您到模板代码中发生错误的位置，这也很难阅读。有时，最好只是仔细检查您的代码，而完全忽略错误消息。

算法

算法是应用于模板的函数。这就是 STL 的真正强大之处开始显现的地方。您可以学习一些通常适用于大多数模板容器的函数名称。您可以轻松地进行排序、搜索、操作和交换。它们总是在一个范围内执行。例如：sort(vec.begin()+1, vec.end()-1) 对第一个和最后一个值以外的所有值进行排序。

容器本身不传递给算法，只传递容器中包含范围的两个迭代器。通过这种方式，算法不直接受容器限制，而是受该特定算法支持的迭代器限制。此外，许多时候您还会将一个特殊准备好的函数（即前面提到的谓词）的名称作为参数传递。您甚至可以传递普通的旧值。

算法应用示例

// Program: Test Score
// Purpose: To demonstrate the use of algorithm 
// with respect to a vector of test scores

#include <algorithm>  // If you want to use an 
   // algorithm this is the header used.
#include <numeric>  // (For Accumulate)
#include <vector>
#include <iostream>
using namespace std;

int testscore[] = {67, 56, 24, 78, 99, 87, 56};

// predicate that evaluates a passed test
bool passed_test(int n)
{
  return (n >= 60);
}

// predicate that evaluates a failed test
bool failed_test(int n)
{
  return (n < 60);
}

int main(int argc, char* argv[])
{
  int total;
  // Initialize a vector with the data in the testscore array
  vector <int> vecTestScore(testscore, 
     testscore + sizeof(testscore) / sizeof(int));
  vector <int>::iterator vi;

  // Sort and display the vector
  sort(vecTestScore.begin(), vecTestScore.end());
  cout << "Sorted Test Scores:" << endl;
  for (vi=vecTestScore.begin(); vi != vecTestScore.end(); vi++)
  {  cout << *vi << ", ";  }
  cout << endl;

  // Display statistics

  // min_element returns an _iterator_ to the 
  // element that is the minimum value in the range
  // Therefor * operator must be used to extract the value
  vi = min_element(vecTestScore.begin(), vecTestScore.end());
  cout << "The lowest score was " << *vi << "." << endl;

  // Same with max_element
  vi = max_element(vecTestScore.begin(), vecTestScore.end());
  cout << "The highest score was " << *vi << "." << endl;

  // Use a predicate function to determine the number who passed
  cout << count_if(vecTestScore.begin(), vecTestScore.end(), passed_test) << 
    " out of " << vecTestScore.size() << 
    " students passed the test" << endl;

  // and who failed
  cout << count_if(vecTestScore.begin(), 
    vecTestScore.end(), failed_test) << 
    " out of " << vecTestScore.size() << 
    " students failed the test" << endl;

  // Sum the scores
  total = accumulate(vecTestScore.begin(), 
     vecTestScore.end(), 0);
  // Then display the Average
  cout << "Average score was " << 
    (total / (int)(vecTestScore.size())) << endl;

  return 0;
}

后会有期，内存分配器

它们用于模板的初始化阶段。它们是神秘的幕后生物，实际上只在您进行高级内存优化时才需要关注，并且最好被视为黑盒子。通常，您甚至不需要指定它们，因为它们是默认参数，一般不被修改。最好了解它们是什么，以防它们出现在那些就业测试中。

派生或嵌入模板

您可以像使用普通类一样使用 STL 类。

它可以被嵌入

class CParam
{
  string name;
  string unit;
  vector <double> vecData;
};

或用作基类

class CParam : public vector <double>
{
  string name;
  string unit;
};

派生使用应谨慎。具体形式取决于您的编程风格。

模板中的模板

要创建更复杂的数据结构，您可以在模板中嵌套模板。最好提前为内部模板使用 typedef，因为您肯定需要再次使用内部模板。

// Program: Vector of Vectors Demo
// Purpose: To demonstrate nested STL containers

#include <iostream>
#include <vector>

using namespace std;

typedef vector <int> VEC_INT;

int inp[2][2] = {{1, 1}, {2, 0}};  
  // Regular 2x2 array to place into the template
int main(int argc, char* argv[])
{
  int i, j;
  vector <VEC_INT> vecvec;
  // if you want to do this in all one step it looks like this
  // vector <vector <int> > vecvec;
  
  // Fill it in with the array
  VEC_INT v0(inp[0], inp[0]+2);  // passing two pointers 
    // for the range of values to be copied to the vector
  VEC_INT v1(inp[1], inp[1]+2);

  vecvec.push_back(v0);
  vecvec.push_back(v1);

  for (i=0; i<2; i++)
  {
    for (j=0; j<2; j++)
    {
      cout << vecvec[i][j] << "  ";
    }
    cout << endl;
  }
  return 0;
}

// Output:
// 1 1
// 2 0

尽管初始化起来很麻烦，但一旦完成并填充完毕，您就拥有了一个可以无限扩展的二维数组（直到内存空间耗尽）。根据情况，对于任何容器组合都可以做到这一点。

结论

STL 很有用，但并非没有其烦恼。正如中国人所说：学好它，你就如虎添翼。

相关链接

• Josuttis 网站
• 非常好用的初始化库

历史

• 提交于 2004 年 3 月 23 日
• 编辑于 2004 年 4 月 2 日