发帖
扫码访问
 注册
 登录
首页 ›编程› 软件学院 › 查看内容

标准模板库（STL）使用入门（上 一）

2015-6-30 14:26 |来自: http://blog.jobbole.com 1401 0

摘要: 或许你已经把 C++ 作为主要的编程语言用来解决 TopCoder 上的问题。这意味着你已经简单使用过了 STL，因为数组和字符串都是作为 STL 对象传递给函数。也许你已经注意到了，很多程序员写代码比你快得多，也更简洁。 ...
关键词： nbsp 迭代 容器 一个 Vector 元素 函数 vectorint 数组 first

或许你已经把 C++ 作为主要的编程语言用来解决 TopCoder 上的问题。这意味着你已经简单使用过了 STL，因为数组和字符串都是作为 STL 对象传递给函数。也许你已经注意到了，很多程序员写代码比你快得多，也更简洁。

或许你还不是但想成为一名 C++ 程序猿，因为这种编程语言功能很强大还有丰富的库（也许是因为在 TopCoder 的练习室里和竞赛中看到了很多非常精简的解决方案）。

无论过去如何，这篇文章都会有所帮助。在这里，我们将回顾标准模板库（Standard Template Library—STL，一个非常有用的工具，有时甚至能在算法竞赛中为你节省大量时间）的一些强大特性。

要熟悉 STL，最简单的方式就是从容器开始。

容器

无论何时需要操作大量元素，都会用到某种容器。C语言只有一种内置容器：数组。

问题不在于数组有局限性（例如，不可能在运行时确定数组大小）。相反，问题主要在于很多任务需要功能更强大的容器。

例如，我们可能需要一个或多个下列操作：

  • 向容器添加某种字符串
  • 从容器中移除一个字符串
  • 确定容器中是否存在某个字符串
  • 从容器中返回一些互不相同的元素
  • 对容器进行循环遍历，以某种顺序获取一个附加字符串列表。

当然，我们可以在一个普通数组上实现这些功能。但是，这些琐碎的实现会非常低效。你可以创建树结构或哈希结构来快速解决问题，但是想想：这种容器的实现是取决于即将存储的元素类型吗？例如，我们要存储平面上的点而不是字符串的话，是不是要重写这个模块才能实现功能？

如果不是，那我们可以一劳永逸地为这种容器开发出接口，然后对任何数据类型都能使用。简言之，这就是 STL 容器的思想。

前言

程序要使用 STL 时，应包含（#include）适当的标准头文件。对大部分容器来说，标准头文件的名称和容器名一致，且不需扩展名。比如说，如果你要用栈（stack），只要在程序最开头添加下面这行代码：

1
#include

容器类型（还有算法、运算符和所有 STL也一样）并不是定义在全局命名空间，而是定义在一个叫“std”的特殊命名空间里。在包含完所有头文件之后，写代码之前添加下面这一行：

1
using namespace std;

还有另一个很重要的事情要记住：容器类型也是模板参数。在代码中用“尖括号”(‘<’/’>’)指明模板参数。比如：

1
vector<int> N;

如果要进行嵌套式的构造，确保“方括号”之间不是紧挨着——留出一个空格的位置。（译者：C++11新特性支持两个尖括号之间紧挨着，不再需要加空格）

1
2
3
vector< vector<int> > CorrectDefinition;
 
vectorint>> WrongDefinition; // Wrong: compiler may be confused by 'operator >>'

Vector

最简单的 STL 容器就是 vector。Vector 只是一个拥有扩展功能的数组。顺便说一下，vector 是唯一向后兼容 C 代码的容器——这意味着 vector 实际上就是数组，只是拥有一些额外特性。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> v(10);
 
 for(int i = 0; i < 10; i++) {
 
      v[i] = (i+1)*(i+1);
 
 }
 
 for(int i = 9; i > 0; i--) {
 
      v[i] -= v[i-1];
 
 }

实际上，当你敲下

1
vector<int> v;

就创建了一个空 vector。注意这样的构造方式：

1
vector<int> v[10];

这里我们把’V’声明成一个存放了 10 个 vector 类型元素的数组，初始化为空。大部分情况下，这不是我们想要的。在这里用圆括号代替方括号。Vector 最常使用的特性就是获取容器大小。

1
int elements_count = v.size();

有两点要注意：首先，size() 函数返回的值是无符号的，这点有时会引起一些问题。因此，我经常定义宏，有点像 sz(C) （把C 的大小作为一个普通的带符号整型返回）这样的。其次，如果你想知道容器是否为空，把 vector 的 size() 返回值和0比较不是一个好的做法。你最好使用 empty() 函数：

1
2
bool is_nonempty_notgood = (v.size() >= 0); // Try to avoid this
bool is_nonempty_ok = !v.empty();

这是因为，不是所有容器都能在常量时间内返回自己的大小，而且你绝不应该为了确定链表中至少包含一个节点元素就对一条双链表中的所有元素计数。

另一个 vector 中经常使用的函数是 push_back。Push_back 函数向 vector 尾部添加一个元素，容器长度加 1。思考下面这个例子：

1
2
3
4
5
6
7
8
9
vector<int> v;
 
for(int i = 1; i < 1000000; i *= 2) {
 
     v.push_back(i);
 
}
 
int elements_count = v.size();

别担心内存分配问题——vector 不会一次只分配一个元素的空间。相反，每次用 push_back 添加新元素时，vector 分配的内存空间总是比它实际需要的更多。你应该担心的唯一一件事情是内存使用情况，但在 TopCoder 上这点可能不是问题。（后面再进一步探讨 vector 的内存策略）

当你需要重新改变 vector 的大小时，使用 resize() 函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> v(20);
 
for(int i = 0; i < 20; i++) {
 
     v[i] = i+1;
 
}
 
v.resize(25);
 
for(int i = 20; i < 25; i++) {
 
     v[i] = i*2;
}

Resize() 函数让 vector 只存储所需个数的元素。如果你需要的元素个数少于 vector 当前存储的个数，剩余那些元素就会被删除。如果你要求 vector 变大，使用这个函数也会扩大它的长度，并用 0 填充新创建的元素。

注意，如果在使用了 resize() 后又用了 push_back()，那新添加的元素就会位于新分配内存的后面，而不是被放入新分配的内存当中。上面的例子得到的 vector 大小是25，如果在第二个循环中使用 push_back()，那vector 的大小最后会是30。

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> v(20);
 
for(int i = 0; i < 20; i++) {
 
     v[i] = i+1;
 
}
v.resize(25);
 
for(int i = 20; i < 25; i++) {
     v.push_back(i*2); //把下标值写入元素 [25..30), not [20..25) ! <
}

使用 clear() 函数来清空 vector。这个函数使 vector 包含 0 个元素。它并不是让所有元素的值为0——注意——它是完全删除所有元素，成为空容器。

有很多种方式初始化 vector。你也许用另一个 vector 来创建新的 vector：

1
2
3
4
vector<int> v1;
 // ...
 vector<int> v2 = v1;
 vector<int> v3(v1);

上面的例子中，v2 和 v3 的初始化过程一样。如果你想创建指定大小的 vector，使用下面的构造函数：

1
vector<int> Data(1000);

上面的例子中，变量 data 创建后将包含1,000 个0值元素。记得使用圆括号，而不是方括号。如果你想用其他东西来初始化 vector，你可以这么写：

1
vector names(20, “Unknown”);

记住，你可以创建任何类型的 vector。**数组很重要。通过 vector 创建二维数组，最简单的方式就是创建一个存储 vector 元素的 vector。

1
vector< vector<int> > Matrix;

你现在应该清楚如何创建一个给定大小的二维 vector：

1
2
3
4
5
int N, N;
 
// ...
 
vector< vector<int> > Matrix(N, vector<int>(M, -1));

这里，我们创建了一个 N*M 的矩阵，并用 -1 填充所有位置上的值。向 vector 添加数据的最简单方式是使用 push_back()。但是，万一我们想在除了尾部以外的地方添加数据呢？Insert() 函数可以实现这个目的。同时还有 erase() 函数来删除元素。但我们得先讲讲迭代器。

你还应该记住另一个非常重要的事情：当 vector 作为参数传给某个函数时，实际上是复制了这个 vector（也就是值传递）。在不需要这么做的时候创建新的 vector 可能会消耗大量时间和内存。实际上，很难找到一个任务需要在传递 vector 为参数时对其进行复制。因此，永远不要这么写：

1
2
3
4
void some_function(vector<int> v) { // Never do it unless you’re sure what you do!
 
     // ...
}

相反，使用下面的构造方法（引用传递）：

1
2
3
4
void some_function(const vector<int>& v) { // OK
 
     // ...
}

如果在函数里要改变 vector 中的元素值，那就去掉‘const’修饰符。

1
2
3
4
int modify_vector(vector<int>& v) { // Correct
 
     V[0]++;
}

键值对

在讨论迭代器之前，先说说键值对（pairs）。STL 中广泛使用键值对。一些简单的问题，像 TopCoder SRM 250 和 500 分值的简单题，通常需要一些简单的数据结构，它们都非常适合用 pair 来构造。STL 中的 std::pair 就是一个元素对。最简单的形式如下：

1
2
3
4
5
6
7
template<typename T1, typename T2> struct pair {
 
     T1 first;
 
     T2 second;
 
};

普通的 pair 就是一对整型值。来点更复杂的，pair> 就是一个字符串和两个整型组成的值对。第二种情况也许能这么用：

1
2
3
4
pairint,int> > P;
string s = P.first; // extract string
int x = P.second.first; // extract first int
int y = P.second.second; // extract second int

键值对的最大优势就在于它们有内置操作来比较 pair 对象。键值对优先对比第一个元素值，再比较第二个元素。如果第一个元素不相等，那结果就只取决于第一个元素之间的比较；只有在第一个元素相等时才比较第二 个元素。使用 STL 的内置函数，可以轻易地对数组（或 vector）对进行排序。

例如，如果要对存放整型值坐标点的数组排序，使得这些点排列成一个多边形，一种很好的思路就是把点放入 vector>>，其中每个元素表示成 {polar angle,{x, y}}（点的极角和点的坐标值）。调用 STL 的排序函数可以按你的期望对点进行排序。

关联容器中也广泛使用 pair，这点会在文章后面提及。

迭代器

什么是迭代器？STL 迭代器是访问容器数据的最普通的方式。思考这个简单的问题：将包含 N 个整型（int）的数组 A 倒置。从类 C 语言的方案开始：

1
2
3
4
5
6
7
8
9
10
11
12
13
void reverse_array_**(int *A, int N) {
 
     int first = 0, last = N-1; // First and last indices of elements to be swapped
 
     While(first < last) { // Loop while there is something to swap
 
          swap(A[first], A[last]); // swap(a,b) is the standard STL function
 
          first++; // Move first index forward
 
          last--; // Move last index back
     }
}

对你来说这些代码应该一目了然。很容易用指针来重写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void reverse_array(int *A, int N) {
 
      int *first = A, *last = A+N-1;
 
      while(first < last) {
 
           Swap(*first, *last);
 
           first++;
 
           last--;
 
      }
 
 }

看看这个代码的主循环，它对指针‘first’和‘last’只用了四种不同的操作：

  • 比较指针（first < last），
  • 通过指针取值（*first,*last），
  • 指针自增，以及
  • 指针自减

现在，想象你正面临第二个问题：将一个双链表翻转，或部分翻转。第一个程序使用了下标，肯定不行。至少效率不够，因为不可能在常数时间内通过下标获取双链表中的元素值，必须花费 O(N) 的时间复杂度，所以整个算法的时间复杂度是 O(N^2)。

但是你看：第二个程序对任何类似指针（pointer-like）的对象都能奏效。唯一的要求是，对象能够执行上面所列 出的四种操作：取值（一元运算符 *），对比（<），和自增/自减（++/–）。拥有这些属性并和容器相关联的对象就叫迭代器。任何 STL 容器都可以通过迭代器遍历。尽管 vector 不常用，但对其他类型的容器很重要。

那么，我们现在讨论的这个东西是什么？一个语法上很像指针的对象。为迭代器定义如下操作：

  • 从迭代器取值，int x = *it；
  • 让迭代器自增和自减 it1++，it2–；
  • 通过‘！=’和‘<’来比较迭代器大小；
  • 向迭代器添加一个常量值 it += 20；（向前移动了 20 个元素位置）
  • 获取两个迭代器之间的差值，int n = it2 – it1；

和指针不同，迭代器提供了许多更强大的功能。它们不仅能操作任何类型的容器，还能执行范围检查并分析容器的使用。

当然，迭代器的最大优势就是极大地增加了代码重用性：基于迭代器写的算法在大部分的容器上都能使用，而且，自己写的容器要是提供了迭代器，就能作为参数传给各种各样的标准函数。

不是所有类型的迭代器都会提供所有潜在的功能。实际上，存在所谓的“常规迭代器”和“随机存取迭代器”两种分类。简单地 说，常规迭代器可以用‘==’和‘！=’来做比较运算，而且还能自增和自减。它们不能做减法，也不能在常规迭代器上做加法。基本上来说，不可能对所有类型 的容器都在常数时间范围内实现以上描述的操作。尽管如此，翻转数组的函数应该这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
template<typename T> void reverse_array(T *first, T *last) {
 
     if(first != last) {
 
          while(true) {
 
               swap(*first, *last);
 
               first++;
 
               if(first == last) {
 
                    break;
 
               }
 
               last--;
 
               if(first == last) {
 
                    break;
 
               }
 
          }
 
     }
 
}

这个程序和前面一个程序的主要差别在于，我们没有在迭代器上进行“<”比较，只用了“==”比较。再次强调，如果你对函数原型感到惊讶（发现函数原型和实际不同），不要慌张：模板只是声明函数的一种方式，对任何恰当的参数类型都是有效的。

对指向任意对象类型的指针和所有常规迭代器来说，这个函数应该都能完美运行。

还是回到 STL 上吧。STL 算法常常使用两个迭代器，称为“begin”和“end”。尾部迭代器不指向最后一个对象，而是指向第一个无效对象，或是紧跟在最后一个对象后面的对象。这一对迭代器使用起来通常很方便。

每一个 STL 容器都有 begin() 和 end() 两个成员函数，分别返回容器的初始迭代器和尾部迭代器。

基于这些原理，只有容器 c 为空时，“c.begin() == c.end()”才成立，而“c.end() – c.begin()”总是会等于 c.size()。（后一句只有在迭代器可以做减法运算时才有效，例如，begin() 和 end() 都返回随机存取迭代器，但不是所有容器的这两个函数都这样。见前面的双向链表示例。）

兼容 STL 的翻转函数应该这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
template<typename T> void reverse_array_stl_compliant(T *begin, T *end) {
 
      // We should at first decrement 'end'
 
      // But only for non-empty range
 
      if(begin != end)
 
      {
 
           end--;
 
           if(begin != end) {
 
                while(true) {
 
                     swap(*begin, *end);
 
                     begin++;
 
                     If(begin == end) {
 
                          break;
 
                     }
 
                     end--;
 
                     if(begin == end) {
 
                          break;
 
                     }
 
                }
 
           }
 
      }
 }

注意，这个函数和标准函数 std::reverse(T begin, T end) 的功能一样，这个标准函数可以在算法模块找到（头文件要包含 #include ）。

另外，只要对象定义了足够的功能函数，任何对象都可以作为迭代器传递给 STL 算法和函数。这些就是模板的强大来源。看下面的例子：

1
2
3
4
5
6
7
8
9
10
vector<int> v;
 
 // ...
 
 vector<int> v2(v);
 
 vector<int> v3(v.begin(), v.end()); // v3 equals to v2
 
 int data[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 };
 vector<int> primes(data, data+(sizeof(data) / sizeof(data[0])));

最后一行代码用一个普通数组 C 构造了一个 vector。不带下标的‘data’作为一个指向数组头的指针。‘data + N’指向第 N 个元素，因此，当 N 表示数组大小时，‘data + N’就指向第一个不在数组内的元素，那么‘data + length of data’可以作为数组‘data’的尾部迭代器。表达式‘sizeof(data)/sizeof(data[0])’返回数组 data 的大小，但只在少数情况下才成立。因此，除非是用这种方法构造的容器，否则不要在任何其他情况下使用这个表达式来获取容器大小。

此外，我们甚至可以像下面这样构造容器：

1
2
3
4
vector<int> v;
 
 // ...
 vector<int> v2(v.begin(), v.begin() + (v.size()/2));

构造的vector容器 v2 等于v 的前半部分。下面是翻转函数 reverse() 的示例：

1
2
int data[10] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 };
reverse(data+2, data+6); // the range { 5, 7, 9, 11 } is now { 11, 9, 7, 5 };

每个容器都有 rbegin()/rend() 函数，它们返回反向迭代器（和正常迭代器的指向相反）。反向迭代器用来从后往前地遍历容器。因此：

1
2
vector<int> v;
vector<int> v2(v.rbegin()+(v.size()/2), v.rend());

上面用 v 的前半部分来构造 v2，但顺序上前后颠倒。要创建一个迭代器对象，必须指定类型。在容器的类型后面加上“::iterator”、“::const_iterator”、 “::reverse_iterator”或“::const_reverse_iterator”就可以构建迭代器的类型。因此，可以这样遍历 vector：

1
2
3
4
5
6
7
8
9
10
vector<int> v;
 
 // ...
 
 // Traverse all container, from begin() to end()
 
 for(vector<int>::iterator it = v.begin(); it != v.end(); it++) {
 
      *it++; // Increment the value iterator is pointing to
 }

我推荐使用‘!=’而不是‘<’，使用‘empty()’而不要用‘size() != 0’——对于某些容器类型来说，无法高效地确定迭代器的前后顺序。

现在你了解了 STL 算法 reverse()。很多 STL 算法的声明方式相同：得到一对迭代器（一个范围的初始迭代器和尾部迭代器），并返回一个迭代器。

Find() 算法在一个区间内寻找合适的元素。如果找到了合适的元素，就返回指向第一个匹配元素的迭代器。否则，返回的值指向区间的尾部。看代码：

1
2
3
4
5
6
7
8
9
10
11
12
vector<
声明：文章版权归原作者所有 部分文章转自互联网 如有侵权请联系 [邮箱地址] 删除

路过
雷人
握手
鲜花
鸡蛋
收藏 分享 邀请
上一篇：Chrome 远程调试协议分析与实战（2014）下一篇：标准模板库（STL）使用入门（上 二）

最新评论

相关分类