65.9K
CodeProject 正在变化。 阅读更多。
Home

STL 入门教程

David Hubbard
starIconstarIconstarIcon
emptyStarIcon
starIcon
emptyStarIcon

3.79/5 (67投票s)

2000年5月24日

viewsIcon

594404

STL 入门指南，介绍各种容器类型、字符串、流、迭代器和 STL 的方法

引言

STL 提供了一套基于模板的集合类以及处理这些集合的方法。集合类使开发人员能够访问快速高效的集合。而这些方法，被称为算法，则提供了基于模板的集合操作函数。

STL 的好处包括

  • 类型安全的集合
  • 易用性

模板

如果您已经熟悉模板，请跳到下一节。否则，请阅读本节以获得关于模板的简要教程。模板可以看作是一个带有类型检查的宏。例如，声明一个模板，我们将这样做：

template < class T >
class Value
{
	T _value;
	public:
	Value ( T value ) { _value = value; }
          
	T getValue ();
          
	void setValue ( T value );
};
     
template < class T >
T Value<T>::getValue () { return _value; }
     
template < class T >
void Value<T>::setValue ( T value ) { _value = value; }

此示例声明了一个名为 Value 的类，它存储一个参数化的值 _value，类型为 T。在 template 关键字之后，尖括号内是参数列表。列表告诉模板将使用哪些类型。模板参数列表的一个很好的类比是类构造函数的参数列表。与构造函数一样，模板的参数数量可以是一个或多个。

在类定义之外声明的模板方法需要 template 关键字，如上所示。要使用 Value 类声明一个浮点数数组，我们将这样做：

Value<float> values[10];   // array of values of type float

这声明了一个值数组，尖括号告诉我们 Value 将存储其值作为浮点数。

如果我们想声明一个列表来处理我们基于模板的 Value 类，我们可以这样做：

Template < class T  >
class ValueList
{
	Value<T> * _nodes.
public:
	ValueList ( int noElements )
	{
		_nodes = new Node<T>[noElements];
	}
          
	virtual ~ValueList ()
	{
		delete [] _nodes;
	}
};

在这里，我们声明了一个基于模板的类，它存储一个可变大小的值列表。

STL 集合类型

每种 STL 集合类型都有自己的模板参数，稍后将进行讨论。您使用的集合类型取决于您的需求和偏好。根据过去的经验，vector 和 map 类是最有用的。vector 类是简单和复杂集合类型的理想选择，而 map 类则用于需要关联类型集合时。deque 集合非常适合在基于队列的处理系统中，例如基于消息的系统。

向量
类型为 T 的元素集合。
列表
类型为 T 的元素集合。该集合存储为元素的双向链表，每个元素包含一个类型为 T 的成员。

要包含类定义，请使用

#include <list>
双端队列
长度可变的类型为 T 的元素集合。该序列的存储方式允许在两端进行元素的插入和删除，每次只复制一个元素，并且支持在序列中的任何位置进行插入和删除，但每次操作后都会进行序列复制。

要包含类定义，请使用

#include <deque>
map
类型为 pair<const Key, T> 的可变长度序列的集合。每对的第一个元素是排序键，第二个是其关联的值。序列的存储方式允许任意元素的查找、插入和删除。键可以很简单，如数字或字符串，也可以是复杂的键类。键类必须支持常规的比较操作，以便集合可以排序或搜索。

要包含类定义，请使用

#include <map>
set
一种控制长度可变的类型为 const Key 的元素序列的集合。每个元素既充当排序键又充当值。序列的存储方式允许任意元素的查找、插入和删除。

要包含类定义，请使用

#include <set>
multimap
类型为 pair<const Key, T> 的可变长度序列的集合。每对的第一个元素是排序键，第二个是其关联的值。序列的存储方式允许任意元素的查找、插入和删除。

要包含类定义，请使用

#include <map>
multiset
长度可变的类型为 const Key 的元素序列的集合。每个元素既充当排序键又充当值。序列的存储方式允许任意元素的查找、插入和删除。

要包含类定义，请使用

#include <set>

STL 字符串

STL 字符串支持 ASCII 和 Unicode 字符字符串。

字符串
字符串是 ASCII 字符的集合，支持插入和删除。

要包含字符串类定义，请使用

#include <string>
wstring
wstring 是宽字符的集合，支持插入和删除。在 MFC 中，字符串类是 CString，它提供了 Format 和其他方法来操作字符串。CString 的优点是提供了 Format、TrimLeft、TrimRight 和 LoadString 等方法。提供一个包含这些方法的基于字符串的类很容易。

要包含 wstring 类定义，请使用

#include <xstring>

STL 流

流为开发人员提供了可以输出各种类型流元素的容器变量的类。

stringstream
一个字符串流，支持元素的插入，并通过重载的 << 运算符插入元素。str() 方法返回底层字符串的引用，而 c_str() 可用于获取指向字符串缓冲区的常量指针。
wstringstream
一个宽字符串流，支持元素的插入，并通过重载的 << 运算符插入元素。str() 方法返回底层字符串的引用，而 c_str() 可用于获取指向字符串缓冲区的常量指针。

要使用字符串流，我们将这样做：

stringstream strStr;
for ( long i=0; i< 10; i++ )
    strStr << "Element " << i << endl;

要包含字符串类定义，请使用

#include <strstring>

STL 集合通用类方法

empty
确定集合是否为空
size
确定集合中的元素数量
begin
返回一个指向集合开头的正向迭代器。它常用于遍历集合。
end
返回一个指向集合末尾之后一个位置的正向迭代器。它常用于测试迭代器是否有效或在循环遍历集合。
rbegin
返回一个指向集合末尾的逆向迭代器。它常用于反向遍历集合。
rend
返回一个指向集合开头之前一个位置的逆向迭代器。它常用于测试迭代器是否有效或在循环遍历集合。
clear
删除集合中的所有元素。如果您的集合包含指针，则必须手动删除元素。
erase
从集合中删除单个元素或一系列元素。要删除，只需使用指向元素或一对迭代器（显示要删除的元素范围）的迭代器调用 erase。此外，vector 支持基于数组索引的删除。

标准输出和输入

STL 还包含用于将内容打印到标准输出流的类。与标准 C++ 一样，这些类是 cout 和 wcout。要在控制台应用程序中使用它们，请包含 iostream 文件。示例如下：

#include <iostream>
     
void main ()
{
	char ch;
     
	cin >> ch;
	cout << &#8220;This is the output terminal for STL&#8221; << endl;
}

Vector 和 Deque 的添加和删除方法

我们简要看一下如何向 vector 和 deque 集合添加/删除元素。这些集合表示为数组，要添加元素，我们使用 push 方法，根据是添加到数组的前面（开头）还是后面（结尾）来选择 back 或 front。

通用方法是

push_back将元素添加到集合末尾。
push_front将元素添加到集合开头。
back获取对集合末尾元素的引用
front获取对集合末尾元素的引用
pop_back 删除集合末尾的元素
pop_front删除集合末尾的元素

例如，假设我们要构建一个基于消息类的消息处理系统

Class Msg
{
	int _type;
	int _priority;
	string _message;
	
	public:

	Msg ( int type, int priority, string & msg )
    { _type = type; priority = priority; _msg = msg; }
          
	Msg ( int type, int priority, char * msg )
	{ _type = type; priority = priority; _msg = msg; }
          
	int getType () { return _type; }
	int getPriority () { reutrn _priority; }
	string & getMsg () {return _msg; }
};

要存储消息，我们需要一个先进先出（FIFO）的集合，例如 deque：typedef deque<Msg> MsgList;

发送消息我们可能会这样做：

     Msg message( 0, 0, "My Message" );
     msgList.push_back(msg);

并且处理消息我们可以这样做：

void process_msgs ()
{
	bool done = false;
	while ( !done )
	{
		// if no messages stop
		if ( msgList.size() == 0 )
		{ done == true; continue;}
		// get msg and process
		Msg & msg = msgList.front();
		
		switch ( msg.getType() )
		{ // process messages }
		
		// remove msg from que
		msgList.pop_front();
	}
}

只需几行代码，我们就创建了一个通用的消息传递系统。如果我们想要一个完整的系统，我们可以创建一个简单的 COM 服务器，它公开一个邮件接口，并使用消息列表存储消息。

运算符 []

对于 vector、map、deque、string 和 wstring 集合，元素通常使用以下方式添加：

      operator []

访问指定位置的元素，并且对于 map、string 和 wstring 支持元素插入。

使用此运算符的一个简单示例是声明一个使用 map 的列表

typedef map<int, string> StringList
StringList strings;
stringstream strStr
for ( long i=0; i<10; i++ )
{
	stringstream strStr;
	strStr << "String " << i;
	strings[i] = strStr.str();
}
for ( long i=0; i<10; i++ )
{
	string str = strings[5];
	cout << str.c_str() << endl;
}

我们创建了一个 map，其键为整数，存储字符串。

迭代器

迭代器支持访问集合中的元素。它们在整个 STL 中用于访问和列出容器中的元素。特定集合的迭代器定义在集合类定义中。下面我们列出三种类型的迭代器：iterator、reverse_iterator 和 random access。随机访问迭代器就是可以以任何步长值向前和向后遍历集合的迭代器。例如，使用 vector 我们可以这样做：

vector<int>    myVec;
vector<int>::iterator    first, last;
for ( long i=0; i<10; i++ )
	myVec.push_back(i);
first = myVec.begin();
last = myVec.begin() + 5;
if ( last >= myVec.end() )
	return;
myVec.erase( first, last );

这段代码将删除 vector 的前五个元素。请注意，我们将最后一个迭代器设置为我们感兴趣的最后一个元素的下一个位置，并将其与 end()（它返回集合中最后一个有效项之后的迭代器）的返回值进行比较。在使用 STL 时，请始终记住，要标记操作的结束，请使用指向操作中最后一个有效元素之后的下一个元素的迭代器。

三种类型的迭代器是

iterator（集合正向迭代器）
允许集合以正向遍历。要使用迭代器：
for ( iterator element = begin(); element < end(); element++ ) 
	t = (*element);

正向迭代器支持以下操作：

a++, ++a, *a, a = b, a == b, a != b
reverse_iterator（集合逆向迭代器）
允许集合以逆向遍历。例如：
for ( reverse_iterator element = rbegin(); element < rend(); element++ ) 
	t = (*element);

所有集合都支持正向迭代器。逆向迭代器支持以下操作：

a++, ++a, *a, a = b, a == b, a != b
random access（用于 vector，声明为正向和逆向迭代器）
允许以任何步长值向前或向后遍历集合。一个例子是：
for ( iterator element = begin(); element < end(); element+=2 ) 
	t = (*element);
vector 集合支持随机访问迭代器。迭代器是访问 STL 集合最常用的类型，它们也用于从集合中删除元素。看下面的例子：
iterator element = begin(); erase(element);

这将使迭代器指向集合的第一个元素，然后将其从集合中删除。如果我们使用的是 vector，我们可以这样做：

iterator firstElement = begin();
          iterator lastElement = begin() + 5;
          erase(firstElement,lastElement);
          
to remove the first five elements of a collection.
          Random access iterators support the following:
          
          
a++, ++a, a--, --a, a += n, a -= n, a &#8211; n, a + n*a, a[n],
a = b, a == b, a != b, a < b, a <= b, a > b, a >= b

重要的是要记住，当您获取集合的迭代器时，不要在修改集合后继续使用该迭代器。一旦集合被修改，在大多数情况下，迭代器将失效。

声明集合

每个集合都使用其模板参数来确定集合将存储哪些元素。下面列出了我们正在讨论的集合，并在旁边显示了它们的模板参数。在参数中，T 表示要存储在集合中的元素类型，A 表示分配器（分配元素），Key 表示元素的键，而 Pred 表示集合如何排序。

template < class T, class A = allocator<T> > class vector
template < class T, class A = allocator<T> > class list
template < class T, class A = allocator<T> > class deque
template <class Key, class T, class Pred = less<Key>, class A = allocator<T> > class map
template <class Key, class Pred = less<Key>, class A = allocator<Key> > class set
template <class Key, class T, class Pred = less<Key>, class A = allocator<T> > class multimap
template <class Key, class Pred = less<Key>, class A = allocator<Key> > class multiset

这个列表看起来有点令人望而生畏，但它为集合提供了一个快速参考。在大多数情况下，您将使用默认参数，您唯一需要关心的是您正在存储什么以及如何存储。T 指的是您将存储的内容，对于支持键的集合；Key 显示元素如何关联。

根据之前的经验，vector、map 和 deque 类是最常用的，所以我们可以用它们作为声明集合的例子：

使用 typedef 声明集合

typedef vector<int> myVector
typedef map< string, int > myMap
typedef deque< string > myQue

第一个声明声明了一个整数 vector，第二个声明了一个整数集合，其键类型为 string，最后一个声明了一个字符串队列（或堆栈）。

声明集合的另一种方法是从 STL 集合派生一个集合，如下例所示：

class myVector : public vector<int> {};

这两种方法都有用，取决于个人喜好。另一个重要的考虑因素是声明集合所支持的迭代器作为单独的类型。如果我们使用上面的例子，我们将声明：

typedef myVector::iterator vectorIterator
typedef myVector::reverse_iterator revVectorIterator

这使得集合的用户可以直接访问迭代器，而无需强制使用以下语法：

myVector coll;
for ( myVector::iterator element = coll.begin(); element < coll.end(); element++ )

作用域解析运算符可能很麻烦。

算法

到目前为止，我们已经讨论了如何最低限度地使用 STL，现在我们需要深入研究集合最重要的部分。我们如何操作集合？例如，如果我们有一个字符串列表，我们需要什么来按字母顺序对列表进行排序，或者如果我们想搜索一个集合以查找与给定条件匹配的一组元素。这就是 STL 算法的用武之地。在您的 Visual Studio 安装中，在 include 目录下，您会找到一个名为 algorithm 的 include 文件。在 algorithm 中，声明了一组基于模板的函数。这些函数可用于操作 STL 集合。这些函数可以分为以下几类：序列、排序和数值。使用这些类别，我们可以列出算法的所有方法：

序列
count, count_if, find, find_if, adjacent_find, for_each, mismatch, equal, search, copy, copy_backward, swap, iter_swap, swap_ranges, fill, fill_n, generate, generate_n, replace, replace_if, transform, remove, remove_if, remove_copy, remove_copy_if, unique, unique_copy, reverse, reverse_copy, rotate, rotate_copy, random_shuffle, partition, stable_partition
排序
sort, stable_sort, partial_sort, partial_sort_copy, nth_element, binary_search, lower_bound, upper_bound, equal_range, merge, inplace_merge, includes, set_union, set_intersection, set_difference, set_symmetric_difference, make_heap, push_heap, pop_heap, sort_heap, min, max, min_element, max_element, lexicographical_compare, next_permutation, prev_permutation
数值
accumulate, inner_product, partial_sum, adjacent_difference

由于这是一个非常长的列表，我们将只检查算法中的几个方法。非常重要的是要注意，这里的方法是模板化的，所以我们不需要使用 STL 容器来使用这些方法。例如，我们可以有一个整数列表，然后对该列表进行排序：

#include <vector>
#include <algorithm>
#include <iostream>
     
vector<int>              myVec;
vector<int>::iterator    item;
ostream_iterator<int>    out(cout," ");
// generate array
for ( long i=0; i<10; i++ )
    myVec.push_back(i);
// shuffle the array
random_shuffle( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );
// sort the array in ascending order
sort( myVec.begin(), myVec.end() );
copy( myVec.begin(), myVec.end(), out );

此示例显示了如何声明 vector 然后使用 STL 容器对其进行排序。我们也可以在不使用容器的情况下执行相同的操作：

ostream_iterator<int>  out(cout," ");
// generate array (note: one extra element, end in STL is one element past last valid)
int myVec[11];
for ( long i=0; i<10; i++ )
    myVec[i] = i;
int * begin = &myVec[0];
int * end = &myVec[10];
// shuffle the array
random_shuffle( begin, end );
copy( begin, end, out );
// sort the array in ascending order
sort( begin, end );
copy( begin, end, out );

如何使用算法很大程度上取决于您，但它们提供了丰富的方法来操作容器。

多线程问题

STL 不是线程安全的，因此如果您的集合将在多线程环境中使用，您必须提供锁。可以使用标准的锁定机制，如互斥锁、信号量和临界区。提供锁的一个简单机制是声明一个锁类。在该类中，构造函数创建锁，析构函数销毁锁。然后提供 lock() 和 unlock() 方法。例如：

class Lock
{
public:
	HANDLE    _hMutex;            // used to lock/unlock object
     
	Lock() : _hMutex(NULL)
	{ _hMutex = ::CreateMutex( NULL, false,NULL) ); }
     
	virtual ~Lock() { ::CloseHandle( _hMutex ); }
     
	bool lock ()
	{
		if ( _hMutex == NULL )
			return false;
		WaitForSingleObject( _hMutex, INFINITE );
		return true;
	}
     
	void unlock () { ReleaseMutex(_hMutex);      }
     
};

然后声明一个从 STL 集合之一派生的类，并在该类中重写可能导致元素插入或删除的集合的访问方法。例如，一个通用的 vector 类将是：

template <class T>
class LockVector : vector<T>, Lock
{
public:
	LockVector () : vector<T>(), Lock()
	{}
	virtual LockVector ()
	{}
     
	void insert ( T & obj )
	{
		if ( !lock())
			return;
		vector<T>::push_back (obj);
		unlock();
	}
};

结论

希望我已经为您提供了关于如何使用 STL 的良好教程。如果不是，请尝试上面列出的一些网站，或者去您当地的书店或 amazon.com 购买一本关于该主题的书。我相信 STL 可以带来许多好处，我也希望您能从中受益。

其他 STL 网站

  • David Musser 的 Rensselaer STL 网站
  • Renssalaer STL 在线参考
  • 维也纳技术大学的 STL 教程
  • Boris Fomitchev 将 SGI STL 移植到其他编译器
  • Mumit Khan 的 STL 新手指南
  • David Harvey 的“A Tiny STL Primer”
  • Jak Kirman 的“A Very Modest STL Tutorial”
  • P. J. Plauger 的 Dinkum 标准模板库参考
  • G. Bowden Wise 的 STL 概述
  • Ian Burrell 的 STL 页面
  • Cay Horstmann 的“Safe STL”
  • Warren Young 的 STL 资源列表
  • Rob Kremer 的标准模板库概述
  • Alexander Stepanov 的 Byte Magazine 文章
  • Dr. Dobb's Journal 对 Alexander Stepanov 的采访

直接链接

  • http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/tut.html
  • http://www.cs.brown.edu/people/jak/proglang/cpp/stltut/
  • http://www.roy.org/docs/stl

关于 STL 和泛型编程的书籍

Leen Ammeraal 著《STL for C++ Programmers》。
John Wiley，1996。ISBN 0-471-97181-2。

Ulrich Breymann 著《Designing Components with the C++ STL》。
Addison Wesley Longman，1998。ISBN 0-201-17816-8。

David Musser 和 Atul Saini 著《STL Tutorial and Reference Guide》。
Addison-Wesley，1996。ISBN 0-201-63398-1。

Mark Nelson 著《C++ Programmer’s Guide to the Standard Template Library》。
IDG Books，1995。ISBN 1-56884-314-3。

© . All rights reserved.