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

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

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

摘要: 123456int data = { 1, 5, 2, 4, 3 };vectorint X(data, data+5);int v1 = *max_element(X.begin(), X.end()); // Returns value of max element in vectorint i1 = min_element(X.begin(), X.end()) – X.begin; // ...
关键词： nbsp 元素 迭代 一个 容器 函数 Set vector find vectorint


1
2
3
4
5
6
int data[5] = { 1, 5, 2, 4, 3 };
 vector<int> X(data, data+5);
 int v1 = *max_element(X.begin(), X.end()); // Returns value of max element in vector
 int i1 = min_element(X.begin(), X.end()) – X.begin; // Returns index of min element in vector
 int v2 = *max_element(data, data+5); // Returns value of max element in array
 int i3 = min_element(data, data+5) – data; // Returns index of min element in array

现在，你可以看到一个有效的宏定义如下：

1
#define all(c) c.begin(), c.end()

不要将宏定义中的右边部分全部放到圆括号中去——那是错的！

另一个很好的算法是 sort()，使用很简单。思考下面的示例：

1
2
3
4
5
vector<int> X;
// ...
sort(X.begin(), X.end()); // Sort array in ascending order
sort(all(X)); // Sort array in ascending order, use our #define
sort(X.rbegin(), X.rend()); // Sort array in descending order using with reverse iterators

编译 STL 程序

在这里有必要指出 STL 的错误信息。由于 STL 分布在源代码中，那编译器就必须创建有效的可执行文件，而 STL 的一个特性就是错误信息不可读。例如，如果你把一个 vector<int> 作为常引用参数（当你应该这么做的时候）传递给某个函数：

1
2
3
4
5
6
7
8
void f(const vector<int>& v) {
 
     for(
 
          vector<int>::iterator it = v.begin(); // hm... where’s the error?..
          // ...
     // ...
}

这里的错误是，你正试图对一个定义了 begin() 成员函数的常量对象创建非常量迭代器（因为识别这种错误比实际更正它更难）。正确的代码是这样：

1
2
3
4
5
6
7
8
9
10
11
12
void f(const vector<int>& v) {
 
      int r = 0;
 
      // Traverse the vector using const_iterator
 
      for(vector<int>::const_iterator it = v.begin(); it != v.end(); it++) {
 
           r += (*it)*(*it);
      }
      return r;
 }

尽管如此，还是来说说‘typeof’,它是 GNU C++ 非常重要的特性。在编译过程中，这个运算符会被替换成表达式的类型。思考下面的示例：

1
typeof(a+b) x = (a+b);

这句代码创建了变量 x，它的类型和表达式 （a + b）的类型一致。注意，对任何类型的 STL 容器来说，typeof(v.size()) 得到的值都是无符号的。但在Topcoder 上，typeof 最重要的应用是遍历容器。思考下列宏定义：

1
2
3
#define tr(container, it)
 
     for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

使用这些宏，我们可以遍历每一种容器而不仅仅是 vector。这些宏会为常量对象生成 const_iterator，为非常量对象生成常规迭代器，而你永远不会在这里出错。

1
2
3
4
5
6
7
8
9
10
11
12
void f(const vector<int>& v) {
 
      int r = 0;
 
      tr(v, it) {
 
           r += (*it)*(*it);
 
      }
 
      return r;
 }

注意：为了提高可读性，在 #define 这一行我并没有添加额外的圆括号。阅读文章的后续部分得到更多关于 #define 的正确表述，你可以在练习室里面自己试试。

Vector 不需要真的遍历宏定义，但对于更复杂的数据类型（不支持下标，迭代器是获取数据的唯一方式）来说很方便。我们稍后会在文章中谈及这一点。

Vector 中的数据操作

可以用 insert() 函数往 vector 中插入一个元素：

1
2
3
vector<int> v;
// ...
v.insert(1, 42); // Insert value 42 after the first

从第二个（下标为1的元素）往后的所有元素都要右移一位，从而空出一个位置给新插入的元素。如果你打算添加很多元素，那多次右移并不可取——明智的做法是单次调用 insert()。因此，insert() 有一种区间形式：

1
2
3
4
5
6
vector<int> v;
 vector<int> v2;
 // ..
 // Shift all elements from second to last to the appropriate number of elements.
 // Then copy the contents of v2 into v.
 v.insert(1, all(v2));

Vector 还有一个成员函数 erase，它有两种形式。猜猜都是什么：

1
2
3
erase(iterator);
 
erase(begin iterator, end iterator);

第一个例子删除 vector 中的单个元素，第二个例子用两个迭代器指定区间并从vector 中删除整个区间内的元素。

字符串（string）

这是一个操纵字符串的特殊容器。这个字符串容器稍微不同于 vector<char>。绝大部分的不同在于字符串控制函数和内存管理策略。字符串有不支持迭代器的子串函数 substring()，只支持下标：

1
2
3
4
5
6
string s = "hello";
 
string s1 = s.substr(0, 3), // "hel"
       s2 = s.substr(1, 3), // "ell"
       s3 = s.substr(0, s.length()-1), "hell"
       s4 = s.substr(1); // "ello"

谨防对空串执行（s.length() – 1），因为 s.length() 的返回值不带符号，而 unsigned(0) – 1 得到的结果绝对不是你想的那样。

Set

总是很难决定要先描述哪种容器——set 还是 map。我的观点是，如果读者了解一些算法的基本知识，从‘set’开始会更容易理解。

思考我们需要一个拥有下列特性的容器：

  • 添加一个元素，但不允许和已有元素重复[复制？]
  • 移除元素
  • 获取元素个数（不同元素的个数）
  • 检查集合中是否存在某个元素

这个操作的使用相当频繁。STL 为此提供了特殊容器——set。Set 可以在 O(log N)（其中 N 是 set 中对象的个数）的时间复杂度下添加、移除元素，并检查特定元素是否存在。向 set 添加元素时，如果和已有元素值重复，那新添加的元素就会被抛弃。在常数时间复杂度 O(1) 下返回 set 的元素个数。我们将在后面讨论 set 和 map 的算法实现——现在，我们研究一下函数接口：

1
2
3
4
5
6
7
8
9
10
11
set<int> s;
 for(int i = 1; i <= 100; i++) {
      s.insert(i); // Insert 100 elements, [1..100]
 }
 
 s.insert(42); // does nothing, 42 already exists in set
 
 for(int i = 2; i <= 100; i += 2) {
      s.erase(i); // Erase even values
 }
 int n = int(s.size()); // n will be 50

Set 不使用 push_back() 成员函数。这样是有道理的：因为 set 中元素的添加顺序并不重要，因此这里用不上 push_back()。

由于 set 不是线性容器，不可能用下标获取 set 中的元素。因此，遍历 set 元素的唯一方法就是使用迭代器。

1
2
3
4
5
6
7
8
9
10
// Calculate the sum of elements in set
 
 set<int> S;
 // ...
 
 int r = 0;
 
 for(set<int>::const_iterator it = S.begin(); it != S.end(); it++) {
      r += *it;
 }

在这里使用遍历宏会更简洁。为什么？想象一下你有这样的容器 set<pair<string,pair<int,vector<int>>>>，怎么遍历呢？写迭 代器的类型名称？天呐，还是用我们为遍历迭代器类型而定义的宏吧。

1
2
3
4
5
6
7
8
9
set< pair<string, pair< int, vector<int> > > SS;
 
 int total = 0;
 
 tr(SS, it) {
 
      total += it->second.first;
 
 }

注意这样的语法‘it->second.first’。由于‘it’是一个迭代器，所以我们必须在运算前从 ‘it’得到对象。因此，正确的语法是‘(*it).second.first’。无论如何，写‘something->’总是比写 ‘(*something)’更容易。完整的解释会很长——只要记住，对迭代器而言两种语法都允许。

使用‘find()’成员函数确定集合 set 中是否存在某个元素。不要搞混了，因为 STL 中有很多‘find()’。有一个全局算法‘find()’，输入两个迭代器和一个元素，它能工作在 O(N) 的线性时间复杂度下。你可能会用它来搜索 set 中的元素，但是明明存在一个 O(log N) 时间复杂度的算法，为何要用一个 O(N) 的算法呢？在 set 和 map （还包括 multiset/multimap、hash_map/hash_set等容器）中搜索元素时，不要使用全局的搜索函数 find() ——反而应该使用成员函数‘set::find()’。作为‘顺序的’find函数，set::find 会返回一个迭代器，不论这个迭代器指向被找到的元素，还是指向‘end()’。因此，像这样检查元素是否存在：

1
2
3
4
5
6
7
8
9
10
set<int> s;
 
 // ...
 
 if(s.find(42) != s.end()) {
      // 42 presents in set
 }
 else {
      // 42 not presents in set
 }

作为成员函数被调用时，另一个工作在 O(log N) 时间复杂度下的算法是计数函数 count。有的人认为这样

1
2
3
4
if(s.count(42) != 0) {
 
      // …
 }

或者甚至这样

1
2
3
4
if(s.count(42)) {
 
      // …
 }

写更方便。个人来说，我不这么想。在 set/map 中使用 count() 没有意义：元素要么存在，要么不存在。对我来说，我更愿意使用下面两个宏：

1
2
3
#define present(container, element) (container.find(element) != container.end())
 
#define cpresent(container, element) (find(all(container),element) != container.end())

（记住 all(c) 代表“c.begin(), c.end()”）

这里，‘present()’用成员函数‘find()’ （比如 set/map 等等）来返回容器中是否存在某个元素，而‘cpresent’则是为 vector 定义的。

使用 erase() 函数从 set 中删除一个元素。

1
2
3
4
5
set<int> s;
 
 // …
 s.insert(54);
 s.erase(29);

Erase() 函数也有区间操作形式：

1
2
3
4
5
6
7
8
9
10
11
set<int> s;
 
 // ..
 
 set<int>::iterator it1, it2;
 
 it1 = s.find(10);
 
 it2 = s.find(100);
 // Will work if it1 and it2 are valid iterators, i.e. values 10 and 100 present in set.
 s.erase(it1, it2); // Note that 10 will be deleted, but 100 will remain in the container

Set 有一个区间构造函数：

1
2
int data[5] = { 5, 1, 4, 2, 3 };
set<int> S(data, data+5);

这样可以轻松避免 vector 中的重复元素，然后排序：

1
2
3
4
5
6
vector<int> v;
 
 // …
 
 set<int> s(all(v));
 vector<int> v2(all(s));

这里，‘v2’将和‘v’包含相同元素，但以升序排列，并且移除了重复元素。任何可比较的元素都可以存储在 set中。这个在后面解释。

Map

Map 有两种解释。简单版本如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
map<string, int> M;
 
 M["Top"] = 1;
 
 M["Coder"] = 2;
 
 M["SRM"] = 10;
 
 int x = M["Top"] + M["Coder"];
 
 if(M.find("SRM") != M.end()) {
 
      M.erase(M.find("SRM")); // or even M.erase("SRM")
 }

很简单，对吧？

实际上，map 非常像 set，除了一点——它包含的不只是值而是键值对 pair<key, value>。Map 保证最多只有一个键值对拥有指定键。另一个很讨喜的地方是， map 定义了下标运算符 []。

用宏‘tr()’可以轻易遍历 map。注意，迭代器是键值对 std::pair。因此，用 it->second 来取值，示例如下：

1
2
3
4
5
6
7
8
9
10
11
map<string, int> M;
 
// …
 
int r = 0;
 
tr(M, it) {
 
     r += it->second;
 
}

不要通过迭代器来更改 map 元素的键，因为这可能破坏 map 内部数据结构的完整性（见下面的解释）。

在 map::find() 和 map::operator [] 之间有一个重要的区别。Map::find() 永远不会改变 map 的内容，而操作符 [] 则会在元素不存在时创建一个新元素。有时这样做很方便，但当你不想添加新元素时，在循环中多次使用操作符 [] 绝对不是好主意。这就是为什么把 map 作为常引用参数传递给某个函数时，可能不用操作符 [] 的原因：

1
2
3
4
5
6
7
8
9
10
11
void f(const map<string, int>& M) {
 
      if(M["the meaning"] == 42) { // Error! Cannot use [] on const map objects!
 
      }
 
      if(M.find("the meaning") != M.end() && M.find("the meaning")->second == 42) { // Correct
 
           cout << "Don't Panic!" << endl;
      }
 }

关于 Map 和 Set 的注意事项

从内部看，map 和 set 几乎都是以红黑树的结构存储。我们确实不必担忧内部结构，要记住的是，遍历容器时 map 和 set 的元素总是按升序排列。而这也是为何在遍历 map 或 set时，极力不推荐改变键值的原因：如果所做的修改破坏了元素间的顺序，这至少会导致容器的算法失效。

但在解决 TopCoder 的问题时，几乎都会用上 map 和 set 的元素总是有序这个事实。

另一件重要的事情是，map 和 set 的迭代器都定义了运算符 ++ 和 –。因此，如果 set 里存在值 42，而它不是第一个也不是最后一个元素，那下列代码会奏效：

1
2
3
4
5
6
7
8
9
10
set<int> S;
 
 // ...
 
 set<int>::iterator it = S.find(42);
 
 set<int>::iterator it1 = it, it2 = it;
 it1--;
 it2++;
 int a = *it1, b = *it2;

这里的‘a’包含 42 左边的第一个相邻元素，而‘b’则包含右边的第一个相邻元素。

进一步讨论算法

是时候稍微深入探讨算法。大部分算法都声明在标准头文件 #include <algorithm> 中。首先，STL 提供了三种很简单的算法：min(a, b)、max(a, b)、swap(a, b)。这里，min(a, b) 和 max(a, b) 分别返回两个元素间的最小值和最大值，而 swap(a, b) 则交换两个元素的值。

算法 sort() 的使用也很普遍。调用 sort(begin, end) 按升序对一个区间的元素进行排序。注意，sort() 需要随机存取迭代器，因此它不能作用在所有类型的容器上。无论如何，你很可能永远都不会对已然有序的 set 调用 sort()。

你已经了解了算法 find()。调用 find(begin, end, element) 返回‘element’首次出现时对应的迭代器，如果找不到则返回 end。和 find(…) 相反，count(begin, end, element) 返回一个元素在容器或容器的某个范围内出现的次数。记住，set 和 map 都有成员函数 find() 和 count()，它们的时间复杂度是 O(log N)，而 std::find() 和 std::count() 的时间复杂度是 O(N)。

其他有用的算法还有 next_permutation() 和 prev_permutation()。先说说 next_permutation。调用 next_permutation(begin, end) 令区间 [begin, end) 保存区间元素的下一个全排列顺序，如果当前顺序已是最后一种全排列则返回 false。当然， next_permutation 使得许多任务变得相当简单。如果你想验证所有的全排列方式，只要这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> v;
 
for(int i = 0; i < 10; i++) {
 
     v.push_back(i);
 
}
 
do {
 
     Solve(..., v);
 
} while(next_permutation(all(v));

在第一次调用 next_permutation(…) 之前，别忘了确保容器中的元素已排序。元素的初始状态应该形成第一个全排列状态；否则，某些全排列状态会被遗漏，得不到验证。

字符串流

你常常需要进行一些字符串的处理、输入或输出，C++ 为此提供了两个有趣的对象：‘istringstream’和‘ostringstream’。这两个对象都声明在标准头文件 #include <sstream> 中。

对象 istringstream 允许你从一个字符串读入，就像从一个标准输入读数据一样。直接看源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void f(const string& s)
{
      // Construct an object to parse strings
 
      istringstream is(s);
 
      // Vector to store data
 
      vector<int> v;
 
      // Read integer while possible and add it to the vector
 
      int tmp;
 
      while(is >> tmp)
      {
           v.push_back(tmp);
      }
 }

对象 ostringstream 用来格式化输出。代码如下：

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
string f(const vector<int>& v)
{
 
      // Constucvt an object to do formatted output
 
      ostringstream os;
      // Copy all elements from vector<int> to string stream as text
 
      tr(v, it)
      {
 
           os << ' ' << *it;
 
      }
      // Get string from string stream
 
      string s = os.str();
      // Remove first space character
 
      if(!s.empty())
      { // Beware of empty string here
           s = s.substr(1);
      }
      return s;
}

总结

为了继续探讨 STL，我将总结后面会用到的模板列表。这会简化代码示例的阅读，并且希望能提高你的 TopCoder 技巧。模板和宏的简短列表如下：

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

路过
雷人
握手
鲜花
鸡蛋
收藏 分享 邀请
上一篇：标准模板库（STL）使用入门（上 一）下一篇：clip-path动画分享

最新评论

相关分类