认识STL

整理自Mr希灵的博文、面经以及《C++ Primer, 5E》等。

标准库类型 string

标准库类型 string 表示可变长的字符序列。

定义和初始化 string 对象

  • 初始化 string 对象的方式

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    string s1;              // 默认初始化,s1是一个空串
    string s2(s1); // s2 是 s1 的一个副本
    string s2 = s1; // 等价于 s2(s1)
    string s3("value"); // s3 是字面值 "value" 的副本,不包含字面值最后的空字符
    string s3 = "value"; // 等价于 s3("value")
    string s4(n, 'c'); // 把 s4 初始化为连续 n 个字符 c 组成的串

    // 构造 string 的其他方法
    // n, len2 和 pos2 都是无符号值
    string s(cp, n); // s 是指向 cp 指向的数组中的前 n 个字符的拷贝
    // 此数组至少应该包含 n 个字符
    string s(s2, pos2); // s 是 string s2 从下标 pos2 开始的字符的拷贝
    // 若 pos2 > s2.size(),构造函数的行为未定义
    string s(s2, pos2, len2); // s 是 string s2 从下标 pos2 开始 len2 个字符的 // 拷贝,若 pos2 > s2.size(),构造函数的行为未定义
    // 不管 len2 的值为多少,至多拷贝 s2.size()-pos2个字符
  • 直接初始化和拷贝初始化

    • 如果使用等号 = 初始化一个变量,实际执行的是拷贝初始化
    • 如果不使用等号,则执行的是直接初始化(direct initialization)

string 对象上的操作

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
os << s;            // 将 s 写到输出流 os 中,返回 os
is >> s; // 从 is 中读取字符串赋给 s,字符串以空白分隔,返回 is
// string 对象会自动忽略开头的空白并从第一个非空白字符开始
// 直至遇见下一处空白为止。
getline(is, s); // 从 is 中读取一行赋给 s,返回 is
// getline 函数从给定的流中读入内容,直到遇到
// 换行符为止(换行符也被读进来),
// 然后把所读内容存入到 string 对象中(注意不存换行符)
s.empty(); // s 为空返回 true
s.size(); // 返回 s 中字符的个数
s[n]; // 返回 s 中第 n 个字符的引用,位置 n 从 0 开始
s1 + s2; // 返回 s1 和 s2 连接后的结果
s1 = s2; // 用 s2 的副本代替 s1 中原来的字符
s1 == s2;
s1 != s2; // 大小写敏感
<, <=, >, >= // 字典序比较,且大小写敏感

// 子字符串操作
s.substr(pos, n); // 返回一个 string,包含 s 中从 pos 开始的 n 个字符的拷贝。
// pos 的默认值为 0,n 的默认值为 s.size() - pos

// 修改 string 的操作
s.insert(pos, args) // 在 pos 之前插入 args 指定的字符
// pos 为下标的版本返回一个指向 s 的引用
// pos 为迭代器的版本返回指向第一个插入字符的迭代器
s.erase(pos, len) // 删除从位置 pos 开始的 len 个字符。如果 len 被省略,
// 则删除从 pos 开始直至 s 末尾的所有字符
// 返回一个指向 s 的引用
s.assign(args) // 将 s 中的字符替换为 args 指定的字符,返回一个指向 s 的引用
s.append(args) // 将 args 追加到 s, 返回一个指向 s 的引用
s.replace(range, args) // 删除 s 中范围 range 内的字符,替换为 args 指定的字符
// range 为一个下标+长度,或为一对指向 s 的迭代器
// 返回一个指向 s 的引用

args 可以是下列形式之一,str 不能与 s 相同,迭代器 b 和 e 不能指向 s

args 说明
str 字符串 str
str, pos, len str 中从 pos 开始最多 len 个字符
cp, len 从 cp 指向的字符数组的前(最多)len 个字符
cp cp 指向的以空字符结尾的字符数组
n, c n 个字符 c
b, e 迭代器 b 和 e 指定的范围内的字符
初始化列表 花括号包围的,以逗号分隔的字符列表

append 和 assign 可以使用所有形式的 args

args replace(pos,len,args) replace(b,e,args) insert(pos,args) insert(iter,args)
str
str, pos, len
cp, len
cp
n, c
b, e
初始化列表
  • size 函数返回的是一个 string::size_type 类型的值,它是一个无符号类型。这种配套类型体现了标准库类型与机器无关的特性。

Tip:如果一条表达式中已经有了 size() 函数就不要再使用 int 了,这样可以避免混用 int 和 unsigned 可能带来的问题。

  • 当把 string 对象和字符(或字符串)字面值混在一条语句中使用时,必须确保每个加法运算符 (+) 的两侧的运算对象至少有一个是 string。(字符串字面值与 string 是不同的的类型)

标准库类型 vector

标准库类型 vector 表示对象的集合,其中所有对象的类型都相同。因为引用不是对象,所以不存在引用的 vector。

定义和初始化 vector 对象

  • 初始化 vector 对象的方法

    1
    2
    3
    4
    5
    6
    7
    8
    vector<T> v1;                   // v1 是一个空 vector,它潜在的元素是 T 类型的,执行默认初始化
    vector<T> v2(v1); // v2 中包含有 v1 所有元素的副本
    vector<T> v2 = v1; // 等价于 v2(v1)
    // 注意两个 vector 对象的类型必须相同
    vector<T> v3(n, val); // v3 包含了 n 个重复的元素,每个元素的值都为 val
    vector<T> v4(n); // v4 包含了 n 个重复地执行了值初始化的对象
    vector<T> v5{a, b, c, ... }; // v5 包含了初始值个数的元素,每个元素被赋予相应的初始值
    vector<T> v5 = {a, b, c, ... }; // 等价于 v5{a, b, c, ... }
  • 在大多数情况下这些初始化的方式可以相互等价地使用,不过也有例外:

    • 使用拷贝初始化(即使用 =)时,只能提供一个初始值
    • 如果提供的是一个类内初始值,则只能使用拷贝初始化或使用花括号的形式初始化
    • 如果提供的是初始元素值的列表,则只能把初始值放在花括号内执行列表初始化,而不能放圆括号内
  • 值初始化的两个特殊限制:

    • 有些类要求必须明确提供初始值时,只提供元素的数量而不设定初始值无法完成初始化工作
    • 如果只提供了元素而没有设定初始值,只能使用直接初始化
      1
      2
      vector<int> vi = 10;    // 错误
      vector<int> vi(10); // 正确
  • 如果初始化时使用了花括号的形式但是提供的值又不能用来列表初始化,就要考虑用这样的值来构造 vector 对象

    1
    2
    3
    4
    vector<string> v5{"hi"};        // 列表初始化,v5 有一个元素
    vector<string> v6("hi"); // 错误:不能用字符串字面值构造 vector 对象
    vector<string> v7{10}; // v7 有 10 个默认初始化的元素
    vector<string> v8{10, "hi"}; // v8 有 10 个值为 “hi” 的元素

vector 支持的操作

1
2
3
4
5
6
7
8
9
10
v.empty();              // 如果 v 不含有任何元素,返回真;否则返回假
v.size(); // 返回 v 中元素的个数
// 返回值的类型是由 vector 定义的 size_type 类型
v.push_back(t); // 向 v 的尾端添加一个值为 t 的元素
v[n]; // 返回 v 中第 n 个位置上元素的引用
v1 = v2; // 用 v2 中元素的拷贝替换 v1 中的元素
v1 = {a, b, c, ... }; // 用列表中元素的拷贝替换 v1 中元素
v1 == v2; // v1 和 v2 相等当且它们的元素数量相同且对应位置的元素值都相同
v1 != v2;
<, <=, >, >= // 字典序进行比较(前提是 vector 对象中元素的值可比较)

要使用 size_type,需首先指定它是由哪种类型定义的。vector 对象的类型总是包含着元素的类型。

1
2
vector<int>::size_type      // 正确
vector::size_type // 错误

迭代器

使用迭代器

和指针不一样的是,获取迭代器不是使用取地址符,有迭代器的类型同时拥有返回迭代器的成员。比如,这些类型都拥有名为 begin 和 end 的成员:

  • begin 成员负责返回指向第一个元素(或第一个字符)的迭代器
  • end 成员则负责返回指向容器(或 string 对象)“尾元素的下一个位置(one past the end)”的迭代器,称为尾后迭代器(off-the-end iterator)
    1
    auto b = v.begin(), e = v.end();    // b 和 e 的类型相同

如果容器为空,则 begin 和 end 返回的是同一个迭代器,都是尾后迭代器。

标准容器迭代器的运算符

1
2
3
4
5
6
7
*iter               // 返回迭代器 iter 所指元素的引用
iter->mem // 解引用 iter 并获取该元素的名为 mem 的成员,等价于 (*iter).mem
// 箭头运算符 -> 将解引用和成员访问两个操作结合在一起
++iter // 令 iter 指示容器中的下一个元素
--iter // 令 iter 指示容器中的上一个元素
iter1 == iter2 // 如果两个迭代器指示的是同一个元素或者它们是同一个容器的尾后迭代器,则相等
iter1 != iter2 // 反之,不相等

因为 end 返回的迭代器并不实际指示某个元素,所以不能对其进行递增或解引用的操作。

迭代器类型

实际上,那些拥有迭代器的标准库类型使用 iteration 和 const_iterator 来表示迭代器的类型:

1
2
3
4
5
vector<int>::iterator it;           // it 能读写 vector<int> 的元素
string::iterator it2; // it2 能读写 string 对象中的字符

vector<int>::const_iterator it3; // it3 只能读元素,不能写元素
string::const_iterator it4; // it4 只能读字符,不能写字符

  • 如果标准库类型对象是常量,只能使用 const_iterator
  • 如果标准库类型对象不是常量,那么既能使用 iterator,也能使用 const_iterator
  • begin 和 end 返回的具体类型由对象是否是常量决定
    • 对象是常量,返回 const_iterator
    • 对象不是常量,返回 iterator
    • 专门返回 const_iterator 类型的函数:cbegin 和 cend

WARNING:谨记,但凡是使用了迭代器的循环体,都不要向迭代器所属的容器添加元素,这会使迭代器失效。

vector 和 string 迭代器支持的运算

string 和 vector 的迭代器比标准库容器迭代器提供了更多额外的运算符

1
2
3
4
5
6
7
8
9
iter + n        // 迭代器加上一个整数值仍得到一个迭代器,迭代器指示的新位置与原来相比向前移动了若干个元素。
// 结果迭代器或者指示容器内的一个元素,或者指示容器尾元素的下一个位置
iter - n // 迭代器加上一个整数值仍得到一个迭代器,迭代器指示的新位置与原来相比向后移动了若干个元素。
// 结果迭代器或者指示容器内的一个元素,或者指示容器尾元素的下一个位置
iter += n // 迭代器加法的复合赋值语句
iter -= n // 迭代器减法的复合赋值语句
iter1 - iter2 // 两个迭代器相减的结果是它们之间的距离。参与运算的两个迭代器必须指向的是同一个容器中的
// 元素或者尾元素的下一个位置
>, >=, <, <= // 参与运算的两个迭代器必须指向的是同一个容器中的元素或者尾元素的下一个位置

顺序容器

顺序容器是将单一类型元素聚集起来成为容器,然后根据位置来存储和访问这些元素。标准库常用顺序容器如下:

  • vector,可变大小数组。支持快速随机访问,在尾部之外的位置插入或删除元素可能很慢。
  • deque,双端队列。支持快速随机访问,在头尾部插入速度很快。
  • list,双向链表。支持双向顺序访问,在 list 中任何位置插入删除都很快。
  • forward_list,单向链表。只支持单向顺序访问,在链表任何位置插入删除都很快。
    容器只定义了少量操作,大多数额外操作则由算法库提供。容器类型的操作集合具有以下层次结构特点:一些操作适用于所有容器类型;另外一些操作则只适用于顺序或关联容器类型;还有一些操作只适用于顺序或关联容器类型的一个子集。

顺序容器的定义和初始化

所有的容器都是类模版,要定义某种特殊的容器,必须在容器后的尖括号内提供存放元素的数据类型。容器元素类型必须满足以下两个约束:

  • 元素类型必须支持赋值运算;
  • 元素类型的对象必须可以复制。

所有容器类型都定义了默认构造函数,用于创建指定类型的空容器对象。除了默认构造函数,容器类型还提供其他的构造函数,使程序员可以指定元素初值。在 C++11 中,我们可以对容器进行列表初始化。

1
2
3
4
5
6
7
8
vector<string> svec;  //默认构造函数
vector<string> svec2(svec); //将一个容器复制给另一个容器时,类型必须匹配
list<string> slist(svec.begin(), svec.end()); //初始化为一段元素的副本

const list<int>::size_type list_size = 64;
list<string> slist(list_size, "eh"); //分配和初始化指定数目的元素

list<string> authors = {"Qin","Li"}; //C++11列表初始化

顺序容器的常用操作

添加元素

顺序容器添加元素

1
2
3
4
5
6
7
8
vector<string> container;
string text_word;
while (cin >> text_word)
container.push_back(text_word);

list<int> ilist;
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_front(ix);

任何 insert 或 push 操作都可能导致迭代器失效。当编写循环将元素插入到 vector 或 deque 容器中时,程序必须确保迭代器在每次循环后都得到更新。为了避免存储 end 迭代器,可以在每次做完插入运算后重新计算 end 迭代器值:

1
2
3
4
5
6
vector<int>::iterator first = v.begin(); //不要令last = v.end();
while (first != v.end())
{
first = v.insert(first, 42); // insert new value
++first; // advance first just past the element we added
}

改变容器的大小

为避免每次添加元素都会执行内存分配和释放的操作,vector 和 string 每次获取新的内存空间时,都会分配比需求更大的空间作为备用,以此减少内存分配的次数。

1
2
3
4
5
6
7
8
vector<int> c(10,2);
int a = c.size(); //返回容器c中的元素个数
bool b = c.empty(); //判断容器是否为空

c.resize(15); // 将 5 个值为 0 的元素添加到 c 的末尾
c.resize(20, -1); // 将 5 个值为 -1 的元素添加到 c 的末尾
c.reserve(30); // 分配至少能容纳 30 个元素的内存空间
c.capacity(); // 返回容器可以容纳的元素个数 30,此时 c.size()=20

resize() 和 reserve() 区别:

  • size 指容器当前拥有的元素个数,调用 resize(n) 后,容器的 size 即为 n。
  • capacity 则指容器在必须分配新存储空间之前可以存储的元素总数,也可以说是预分配存储空间的大小。调用 reserve(n) 后,若容器的 $capacity < n$,则重新分配内存空间,从而使得 capacity 等于 n。如果 $capacity \ge n$,capacity 无变化。
  • 容器调用 resize() 函数后,所有的空间都已经初始化了,所以可以直接访问。而 reserve() 函数预分配出的空间没有被初始化,所以不可访问。

删除元素

顺序容器删除元素
pop_front 和 pop_back 函数的返回值并不是删除的元素值,而是 void。要获取删除的元素值,则必须在删除元素之前调用 front 或 back 函数。

1
2
3
4
while (!ilist.empty()) { 
process(ilist.front()); // do something with the current top of ilist
ilist.pop_front(); // done; remove first element
}

erase 操作不会检查它的参数,因此必须确保用作参数的迭代器或迭代器范围是有效的。通常,程序员必须在容器中找出要删除的元素后,才使用 erase 操作。寻找一个指定元素的最简单方法是使用标准库的 find 算法。

1
2
3
4
string searchValue("Quasimodo"); 
list<string>::iterator iter = find(slist.begin(), slist.end(), searchValue);
if (iter != slist.end())
slist.erase(iter);

容器适配器

除了顺序容器外,标准库来提供了三种容器适配器:stack、queue 和 priority_queue。适配器(adaptor)是标准库中的一个通用概念,容器、迭代器和函数都有适配器。本质上,一个适配器是一种机制,使得某种事物的行为看起来像另外一件事物一样。

实际上,适配器是根据原始的容器类型所提供的操作,通过定义新的操作接口,来适应基础的容器类型。顺序容器适配器包括 stack、queue 和 priority_queue 类型。

栈的常用操作:

  • s.empty(),判断栈是否为空,为空则返回true。
  • s.size(),返回栈中元素个数。
  • s.pop(),删除栈顶元素,但不返回其值。
  • s.top(),返回栈顶元素的值,不降元素弹出栈。
  • s.push(),在栈顶压入新元素。

队列的常用操作:

  • q.empty() , q.size() 同栈
  • q.pop(),删除队首元素,但不返回其值。
  • q.push(),在队尾压入一个新元素。
  • q.front(),返回队首元素,但不删除此元素
  • q.back(),返回队尾元素。(只适用于 queue)
  • q.top(),返回最高优先级元素,但不删除此元素(只适用于 priority_queue)

关联容器

关联容器支持通过键来高效地查找和读取元素,两个基本的关联容器类型是 map 和 set。

  • map 的元素以键-值(key-value)对的形式组织:键用于元素在 map 中的索引,而值则表示所存储和读取的数据。
  • set 仅包含一个键,并有效地支持关于某个键是否存在的查询。map 可理解为字典,set 可理解为一类元素的集合。

关联容器和顺序容器的本质差别在于:关联容器通过键(key)存储和读取元素,而顺序容器则通过元素在容器中的位置顺序存储和访问元素。

set 和 map 类型的对象所包含的元素都具有不同的键,不允许为同一个键添加第二个元素。如果一个键必须对应多个实例,则需使用 multimap 或 multiset,这两种类型允许多个元素拥有相同的键。

pair 类型

pair 包含两个数据值。在创建 pair 对象时,必须提供两个类型名:pair 对象所包含的两个数据成员各自对应的类型名字。如果在创建 pair 对象时不提供初始化式,则调用默认构造函数对其成员采用值初始化。

1
2
3
pair <string, int> word_count;
typedef pair<string, string> Author; //利用 typedef 简化其声明
Author joyce("James", "Joyce");

与其他标准库类型不同,对于 pair 类,可以直接访问其数据成员:其成员都是公有的,分别命名为 first 和 second。只需使用普通的点操作符(成员访问标志)即可访问其成员:

1
2
3
string firstBook; 
if (author.first == "James" && author.second == "Joyce")
firstBook = "Stephen Hero";

除了构造函数,标准库还定义了一个 make_pair 函数,由传递给它的两个实参生成一个新的 pair 对象。可如下使用该函数创建新的 pair 对象,并赋给已存在的 pair 对象:

1
2
3
4
5
pair<string, string> next_auth; 
string first, last;
while (cin >> first >> last) {
next_auth = make_pair(first, last);
}

map 类型

map 对象的元素是键-值对,也即每个元素包含两个部分:键以及由键关联的值。map 的 value_type 就反映了这个事实。该类型比前面介绍的容器所使用的元素类型要复杂得多:value_type 是存储元素的键以及值的 pair 类型,而且键为 const。如下,word_count 数组的 value_type 为 pair 类型。

1
2
3
4
5
map <string,int> word_count;
word_count.insert(make_pair("James", "Joyce"));
map<string, int>::iterator map_it = word_count.begin();
cout << map_it->first;
cout << " " << map_it->second;

给 map 添加元素

map 容器中添加键-值元素对,可使用 insert 成员实现;或者,先用下标操作符获取元素,然后给获取的元素赋值。在这两种情况下,一个给定的键只能对应于一个元素这一事实影响了这些操作的行为。

用下标操作符来获取该键所关联的值。

  • 如果该键已在容器中,则返回该键所关联的值。
  • 只有在所查找的键不存在时,map 容器才为该键创建一个新的元素,并将它插入到此 map 对象中。此时,所关联的值采用值初始化:类类型的元素用默认构造函数初始化,而内置类型的元素初始化为 0。
    1
    2
    3
    4
    map<string, int> word_count; // empty map from string to int 
    string word;
    while (cin >> word)
    ++word_count[word];

使用下标给 map 容器添加新元素时,元素的值部分将采用值初始化。通常,我们会立即为其赋值,其实就是对同一个对象进行初始化并赋值。而插入元素的另一个方法是:直接使用 insert 成员,其语法更紧凑:

1
2
word_count.insert(map<string, int>::value_type("Anna", 1)); 
word_count.insert(make_pair("Anna", 1));

map 对象中一个给定键只对应一个元素。如果试图插入的元素所对应的键已在容器中,则 insert 将不做任何操作。但是,带有一个键-值 pair 形参的 insert 版本将返回一个值:包含一个迭代器和一个 bool 值的 pair 对象,其中迭代器指向 map 中具有相应键的元素,而 bool 值则表示是否插入了该元素。如果该键已在容器中,则其关联的值保持不变,返回的 bool 值为 true。在这两种情况下,迭代器都将指向具有给定键的元素。

1
2
3
4
5
6
7
8
9
map<string, int> word_count; 
string word;
while (cin >> word) {
// inserts element with key equal to word and value 1;
// if word already in word_count, insert does nothing
pair<map<string, int>::iterator, bool> ret = word_count.insert(make_pair(word, 1));
if (!ret.second) // word already in word_count
++ret.first->second; // increment counter
}

查找并读取 map 中的元素

不能使用下标来查找 map 中的某一元素是否存在,因为如果该键不在 map 容器中,那么下标操作会插入一个具有该键的新元素。map 容器提供了两个操作:count 和 find,用于检查某个键是否存在而不会插入该键。

对于 map 对象,count 成员的返回值只能是 0 或 1。map 容器只允许一个键对应一个实例,所以 count 可有效地表明一个键是否存在。find 操作返回指向元素的迭代器,如果元素不存在,则返回 end 迭代器。

1
2
3
4
int occurs = 0;
map <string, int>::iterator it = word_count.find("foobar");
if(it != wor_count.end())
occurs = it->second;

从 map 对象中删除元素

map删除元素

1
2
3
if (word_count.erase(removal_word)) 
cout << "ok: " << removal_word << " removed\n";
else cout << "oops: " << removal_word << " not found!\n";

map 对象的迭代遍历

与其他容器一样,map 同样提供 begin 和 end 运算,以生成用于遍历整个容器的迭代器。例如,可如下将 map 容器 word_count 的内容输出:

1
2
3
4
5
6
map<string, int>::const_iterator it = word_count.begin();
while(it != word_count.end()){
cout<< it->first << " occurs "
<< it->second << " times " <<endl;
++it;
}

set 类型

map 容器是键-值对的集合,好比以人名为键的地址和电话号码。相反地,set 容器只是单纯的键的集合。例如,某公司可能定义了一个名为 bad_checks 的 set 容器,用于记录曾经给本公司发空头支票的客户。当只想知道一个值是否存在时,使用 set 容器是最适合的。例如,在接收一张支票前,该公司可能想查询 bad_checks 对象,看看该客户的名字是否存在。

set 容器支持大部分的 map 操作,包括上面描述的构造函数、 insert 操作、 count 和 find 操作、 erase 操作等。但是, 不支持下标操作符,而且没有定义 mapped_type 类型。在 set 容器中,value_type 不是 pair 类型,而是与 key_type 相同的类型。它们指的都是 set 中存储的元素类型。这一差别也体现了 set 存储的元素仅仅是键,而没有所关联的值。与 map 一样,set 容器存储的键也必须唯一,而且不能修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
vector<int> ivec;
for(vector<int>::size_type i = 0; i != 10; ++i){
ivec.push_back(i);
ivec.push_back(i);
}
set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl; // prints 20
cout << iset.size() << endl; // prints 10

set<string> set1;
set1.insert("the");

set<int> iset2;
iset2. insert( ivec.begin(), ivec.end() ); // iset2 has 10 elements

iset.find(1); // returns iterator that refers to the element with key == 1
iset.find(11); // returns iterator == iset.end()
iset.count(1); // returns 1

set<int>::iterator set_it = isec.find(1);
cout<< *set_it << endl;

正如不能修改 map 中元素的键部分一样,set 中的键也为 const。在获得指向 set 中某元素的迭代器后,只能对其做读操作,而不能做写操作。

multimap 和 multiset 类型

map 和 set 容器中,一个键只能对应一个实例。而 multiset 和 multimap 类型则允许一个键对应多个实例。例如,在电话簿中,每个人可能有单独的电话号码列表。在作者的文章集中,每位作者可能有单独的文章标题列表。multimap 和 multiset 类型与相应的单元素版本具有相同的头文件定义:分别是 map 和 set 头文件。

multimap 和 multiset 所支持的操作分别与 map 和 set 的操作相同,只有一个例外:multimap 不支持下标运算。不能对 multimap 对象使用下标操作,因为在这类容器中,某个键可能对应多个值。为了顺应一个键可以对应多个值这一性质,map 和 multimap,或 set 和 multiset 中相同的操作都以不同的方式做出了一定的修改。在使用 multimap 或 multiset 时,对于某个键,必须做好处理多个值的准备,而非只有单一的值。

由于键不要求是唯一的,因此每次调用 insert 总会添加一个元素。

带有一个键参数的 erase 版本将删除拥有该键的所有元素,并返回删除元素的个数。而带有一个或一对迭代器参数的版本只删除指定的元素,并返回 void 类型。

关联容器 map 和 set 的元素是按顺序存储的, multimap 和 multset 也一样。因此,在 multimap 和 multiset 容器中,如果某个键对应多个实例,则这些实例在容器中将相邻存放。 在 multimap 和 multiset 中查找元素有三种策略,而且三种策略都基于一个事实——在 multimap 中,同一个键所关联的元素必然相邻存放。

  • 使用 find 和 count 操作
  • lower_bound 和 upper_bound
  • enual_range 函数

multimap/set查找

equal_range 函数返回存储一对迭代器的 pair 对象。如果该值存在,则 pair 对象中的第一个迭代器指向该键关联的第一个实例,第二个迭代器指向该键关联的最后一个实例的下一位置。如果找不到匹配的元素,则 pair 对象中的两个迭代器都将指向此键应该插入的位置。

1
2
3
4
5
pair<authors_it, authors_it> pos = authors.equal_range(search_item); 
while (pos.first != pos.second) {
cout << pos.first->second << endl;
++pos.first;
}

常用泛型算法

标准库为容器类型定义的操作很少,并没有为每个容器实现更多的操作。因为这部分操作可以抽象出来为所有的容器工作,那就是泛型算法。所谓“泛型”是指这些算法可以应用于多种容器类型上,而容器内的元素类型也可以多样化。标准库提供了 100 多个泛型算法,主要定义于头文件\<algorithm> 中,还有一组泛化的算术算法定义于头文件 \<numeric> 中。

大多数泛型算法是工作于容器的一对迭代器所标识的范围,并完全通过迭代器来实现其功能。这段由迭代器指定的范围称为“输入范围”。带有输入范围参数的算法总是使用前两个参数标记该范围,分别指向要处理的第一个元素和最后一个元素的下一个位置。

查找

find 和 count 算法在输入范围中查找指定值。find 算法返回引用第一个匹配元素的迭代器,count 算法返回元素在输入序列中出现次数的计数。它们都在输入范围中查找等于 val 的元素,使用基础类型的相等(==)操作符。find 返回第一个匹配元素的迭代器,如果不存在在匹配元素就返回 end。count 返回 val 出现次数的计数。

1
2
find(beg, end, val); 
count(beg, end, val);

find 函数的源码如下:

1
2
3
4
5
6
7
8
9
template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val)
{
while(first != last){
if(*first == val) return first;
++first;
}
return last;
}

一个例子,查找数组中的某个值。由于指针就像内置数组上的迭代器一样,因此可以用find在数组中查找值。使用begin和end函数可以获取指向数组首尾元素的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
int myints[]={ 10, 20, 30, 40 };
int* p;
p = find(begin(myints), end(myints), 30);
if(p != myints+4)
cout << *p << endl;
}

排序

C++ 中最经常使用的算法应该就是排序算法,也就是 sort 函数。当然还有 partial_sort 以及stable_sort。sort 函数排序默认是从小到大,如果想给自定义类型排序,可以重载运算符或者自定义比较函数。

  • 升序:sort(begin, end, less<data-type>());
  • 降序:sort(begin, end, greater<data-type>());
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    #include <algorithm>
    #include <iostream>
    using namespace std;

    int main()
    {
    int a[10]={2,4,1,23,5,76,0,43,24,65},i;
    for(i=0;i<10;i++) cout << a[i] << " ";
    cout << endl;
    sort(a,a+10,greater<int>());
    for(i=0;i<10;i++) cout << a[i] << " ";
    cout << endl;
    }

当然,也可以自己写比较函数

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
#include <iostream>  
#include <cstring>
#include <algorithm>
using namespace std;

struct Data
{
char data[100];
}str[100];

bool cmp(const Data &elem1, const Data &elem2)
{
if (strcmp(elem1.data, elem2.data) < 0)
return true;
return false;
}

int main()
{
int n, i;
while (cin >> n)
{
for (i=0; i<n; ++i)
cin >> str[i].data;

sort(str, str+n, cmp);

for (i=0; i<n; ++i)
cout << str[i].data << endl;
}
return 0;
}

去重

unique 的作用是从输入序列中删除”所有相邻的重复元素。该算法删除相邻的重复元素,然后重新排列输入范围内的元素,并且返回一个迭代器(容器的长度没变,只是元素顺序改变了),表示无重复的值范围的结束。

1
2
3
4
sort(words.begin(), words.end());   //排序
vector<string>::iterator end_unique =
unique(words.begin(), words.end()); //去重
words.erase(end_unique, words.end()); //删除结尾元素

在 STL 中 unique 函数是一个去重函数, unique 的功能是去除相邻的重复元素(只保留一个),其实它并不真正把重复的元素删除,是把重复的元素移到后面去了,然后依然保存到了原数组中, 返回去重后最后一个元素的地址,因为 unique 去除的是相邻的重复元素,所以一般用之前都会要排一下序。

源代码如下:

1
2
3
4
5
6
7
8
9
10
template <class ForwardIterator>
ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
if (first==last) return last;
ForwardIterator result = first;
while (++first != last){
if (!(*result == *first)) *(++result)=*first;
}
return ++result;
}

赋值

fill 函数可以可以向容器当中的一定范围能赋值,一共接受 3 个参数,类似于 memset 函数。

1
fill(beg, end, val)