六一的部落格

关关难过关关过，前路漫漫亦灿灿。




不允许关键字重复的map系列容器: 通过关键字获得对应的值

map

unordered_map

  1. 下标运算符 []
  2. at操作
关联容器 是否支持
不允许关键字重复的map系列容器: map和unordered_map O
允许关键字重复的map系列容器: multimap和unordered_multimap X
set系列容器 X

下标类型同关键字类型

如果存在, 返回键值对中值的引用; 是个左值, 可以对其执行写操作 

1c[k];
2
3c.at(k);
  • 对连续存储的顺序容器和内置数组使用下标运算符, 或者执行at操作时, 将得到元素的引用; 对对应迭代器执行解引用也会得到元素的引用
  • 对map和unordered_map使用下标运算符, 或者执行at操作时, 将得到键值对中值的引用 mapped_type & ; 对对应迭代器执行解引用得到元素的引用 <const key_type, mapped_type> &

at操作

会检查关键字是否存在, 不存在则抛出 out_of_range 异常 

 1#include <iostream>
 2#include <map>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    map<int, int> s{ {1, 1}, {0, 0} };
 9    s.at(2);
10    return 0;
11}

输出 

terminating with uncaught exception of type std::out_of_range: map::at:  key not found

abort

下标运算符

如果关键字不存在, 使用该关键字为map添加新元素, 对键值对中的值进行值初始化

要求map和unordered_map无顶层const


示例

  1. 添加元素 
    1map<string, size_t> word_count;
2word_count["Anna"] = 1;
3// 添加{"Anna", 1}
  2. 记录输入的单词, 并统计每个单词出现的个数; 输出单词和出现次数 
    1map<string, size_t> word_count;
2string word;
3while (cin >> word)
4    ++word_count[word];
5for (const auto &w : word_count)
6    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : "time") << endl;
  3. 使用unordered_map替换map

    单词不太可能按照字典序输出 
    1unordered_map<string, size_t> word_count;
2string word;
3while (cin >> word)
4    ++word_count[word];
5for (const auto &w : word_count)
6    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << endl;

通过关键字查找元素

find

关联容器的成员函数; 接受关键字

拥有关键字的元素存在则返回指向元素的迭代器; 返回尾后迭代器

如果我们只关心给定关键字是否存在于容器中，使用find


允许关键字重复的关联容器: 拥有相同关键字的元素相邻存储

multimap

multiset

unordered_multimap

unordered_multiset

  1. 有序关联容器
  2. 无序关联容器: 拥有相同关键字的元素存放在同一个桶中

find返回迭代器, 指向相同关键字元素中的第一个; 递增迭代器可以得到所有拥有该关键字的元素


不允许关键字重复的关联容器

map

set

unordered_map

unordered_set

如果find返回的不是尾后迭代器, 该迭代器指向拥有该关键字的唯一元素


示例

  1. set

    如果输入的单词不在exclude中，记录并统计其个数 

     1map<string, size_t> word_count;
 2set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
 3
 4
 5string word;
 6while (cin >> word)
 7    if (exclude.find(word) == exclude.end())
 8        ++word_count[word];
 9for (const auto &w : word_count)
10    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : "time") << endl;

  2. map 

     1#include <iostream>
 2#include <map>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    map<int, int> exc{ {0, 0}, {1, 1} };
 9    auto it = exc.find(1);
10    if (it != exc.end())
11        cout << it->first << "\t" << it->second << endl;
12    return 0;
13}

    输出 

    1	1

统计给定关键字的出现次数

count

关联容器的成员函数; 接受关键字


不允许关键字重复的关联容器使用count成员函数

map

set

unordered_map

unordered_set

count返回值要么0要么1


find返回迭代器, count返回整数 

1set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
2
3iset.find(1);        // 返回指向1的迭代器
4iset.find(11);       // 返回iset.end()
5iset.count(1)        // 返回1
6iset.count(11);      // 返回0

允许关键字重复的关联容器: 查找拥有给定关键字的所有元素

  1. 如果一个multimap或multiset中有多个关键字相同的元素, 这些元素在容器中相邻存储

    multimap

    multiset
  2. 如果unordered_multimap和unordered_multiset中有多个关键字相同的元素, 这些元素在同一个桶中, 且存储位置相邻

    unordered_multimap

    unordered_multiset

使用find + count

  1. 有序关联容器: multimap 

     1string search_item("Alain de Botton");        // 作者名
 2auto entries = authors.count(search_item);    // 书籍个数
 3auto iter = authors.find(search_item);        // 第一本书的位置
 4
 5while(entries)
 6{
 7    cout << iter->second << endl;             // 输出书名
 8    ++iter;                                   // 直接后移
 9    --entries;
10}

  2. 无序关联容器: unordered_multimap 

     1#include <string>
 2#include <iostream>
 3#include <unordered_map>
 4
 5using namespace std;
 6
 7int main()
 8{
 9    unordered_multimap<int, string> us{ {0, "start"},
10                                        {0, "begin"},
11                                        {1, "first"},
12                                        {3, "third"} };
13
14    cout << us.bucket_count() << endl;
15
16    auto cnt = us.count(0);
17    auto it = us.find(0);
18
19    for (; cnt > 0; ++it, --cnt)
20    {
21        cout << it->first << "\t" << it->second << endl;
22    }
23
24    return 0;
25}

    输出 

    5
0	start
0	begin

使用迭代器


lower_bound和upper_bound

返回迭代器

二者构成左闭合区间 [b, e)

允许关键字重复的关联容器 是否支持
multiset O
multimap O
unordered_multiset X
unordered_multimap X

不适用于无序关联容器

  • lower_bound

    迭代器指向第一个关键字不小于k的元素(闭区间下限); 如果关键字不在容器中, 指示拥有该关键字的新元素的插入位置 

    1c.lower_bound(b);

  • upper_bound

    迭代器指向第一个关键字大于k的元素(开区间上限); 如果关键字不在容器中, 指示拥有该关键字的新元素的插入位置 

    1c.upper_bound(e);

  • 示例

    1. 关键字不存在 

      元素序列: 1 2 3 5 6 7
关键字: 4

返回迭代器指向元素:
lower_bound = 5
upper_bound = 5

    2. 查找元素 

      1string search_item("Alain de Botton");        // 作者名
2
3for (auto beg = authors.lower_bound(search_item),
4        end = authors.upper_bound(search_item);
5    beg != end; ++beg)
6    cout << beg->second << endl;    // 输出书名
7
8// 如果关键字不在容器中, beg和end相等

equal_range

返回一对迭代器, 保存在pair中

  1. 关键字存在: 第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素的后继
  2. 关键字不存在: 两个迭代器相等, 指向关键字可以插入的位置 
1c.equal_range(k);

  • 示例

    1. 有序关联容器: multimap 

      1string search_item("Alain de Botton");        // 作者名
2
3for (auto pos = authors.equal_range(search_item);        
4        pos.first != pos.second;
5        ++pos.first)
6    cout << pos.first->second << endl;

    2. 无序关联容器: unordered_multimap 

       1#include <string>
 2#include <iostream>
 3#include <unordered_map>
 4
 5using namespace std;
 6
 7int main()
 8{
 9    unordered_multimap<int, string> us{ {0, "start"},
10                                        {0, "begin"},
11                                        {1, "first"},
12                                        {3, "third"} };
13
14    auto range = us.equal_range(0);
15    for(; range.first != range.second; ++range.first)
16    {
17        cout << range.first->first << "\t" << range.first->second << endl;
18    }
19
20    return 0;
21}

      输出 

      0	start
0	begin

关联容器: 访问元素和查找关键字


December 26, 2023   December 28, 2023  


不允许关键字重复的map系列容器: 通过关键字获得对应的值

map

unordered_map

  1. 下标运算符 []
  2. at操作
关联容器 是否支持
不允许关键字重复的map系列容器: map和unordered_map O
允许关键字重复的map系列容器: multimap和unordered_multimap X
set系列容器 X

下标类型同关键字类型

如果存在, 返回键值对中值的引用; 是个左值, 可以对其执行写操作 

1c[k];
2
3c.at(k);
  • 对连续存储的顺序容器和内置数组使用下标运算符, 或者执行at操作时, 将得到元素的引用; 对对应迭代器执行解引用也会得到元素的引用
  • 对map和unordered_map使用下标运算符, 或者执行at操作时, 将得到键值对中值的引用 mapped_type & ; 对对应迭代器执行解引用得到元素的引用 <const key_type, mapped_type> &

at操作

会检查关键字是否存在, 不存在则抛出 out_of_range 异常 

 1#include <iostream>
 2#include <map>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    map<int, int> s{ {1, 1}, {0, 0} };
 9    s.at(2);
10    return 0;
11}

输出 

terminating with uncaught exception of type std::out_of_range: map::at:  key not found

abort

下标运算符

如果关键字不存在, 使用该关键字为map添加新元素, 对键值对中的值进行值初始化

要求map和unordered_map无顶层const


示例

  1. 添加元素 
    1map<string, size_t> word_count;
2word_count["Anna"] = 1;
3// 添加{"Anna", 1}
  2. 记录输入的单词, 并统计每个单词出现的个数; 输出单词和出现次数 
    1map<string, size_t> word_count;
2string word;
3while (cin >> word)
4    ++word_count[word];
5for (const auto &w : word_count)
6    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : "time") << endl;
  3. 使用unordered_map替换map

    单词不太可能按照字典序输出 
    1unordered_map<string, size_t> word_count;
2string word;
3while (cin >> word)
4    ++word_count[word];
5for (const auto &w : word_count)
6    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : " time") << endl;

通过关键字查找元素

find

关联容器的成员函数; 接受关键字

拥有关键字的元素存在则返回指向元素的迭代器; 返回尾后迭代器

如果我们只关心给定关键字是否存在于容器中，使用find


允许关键字重复的关联容器: 拥有相同关键字的元素相邻存储

multimap

multiset

unordered_multimap

unordered_multiset

  1. 有序关联容器
  2. 无序关联容器: 拥有相同关键字的元素存放在同一个桶中

find返回迭代器, 指向相同关键字元素中的第一个; 递增迭代器可以得到所有拥有该关键字的元素


不允许关键字重复的关联容器

map

set

unordered_map

unordered_set

如果find返回的不是尾后迭代器, 该迭代器指向拥有该关键字的唯一元素


示例

  1. set

    如果输入的单词不在exclude中，记录并统计其个数 

     1map<string, size_t> word_count;
 2set<string> exclude = {"The", "But", "And", "Or", "An", "A", "the", "but", "and", "or", "an", "a"};
 3
 4
 5string word;
 6while (cin >> word)
 7    if (exclude.find(word) == exclude.end())
 8        ++word_count[word];
 9for (const auto &w : word_count)
10    cout << w.first << " occurs " << w.second << ((w.second > 1) ? " times" : "time") << endl;

  2. map 

     1#include <iostream>
 2#include <map>
 3
 4using namespace std;
 5
 6int main()
 7{
 8    map<int, int> exc{ {0, 0}, {1, 1} };
 9    auto it = exc.find(1);
10    if (it != exc.end())
11        cout << it->first << "\t" << it->second << endl;
12    return 0;
13}

    输出 

    1	1

统计给定关键字的出现次数

count

关联容器的成员函数; 接受关键字


不允许关键字重复的关联容器使用count成员函数

map

set

unordered_map

unordered_set

count返回值要么0要么1


find返回迭代器, count返回整数 

1set<int> iset = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
2
3iset.find(1);        // 返回指向1的迭代器
4iset.find(11);       // 返回iset.end()
5iset.count(1)        // 返回1
6iset.count(11);      // 返回0

允许关键字重复的关联容器: 查找拥有给定关键字的所有元素

  1. 如果一个multimap或multiset中有多个关键字相同的元素, 这些元素在容器中相邻存储

    multimap

    multiset
  2. 如果unordered_multimap和unordered_multiset中有多个关键字相同的元素, 这些元素在同一个桶中, 且存储位置相邻

    unordered_multimap

    unordered_multiset

使用find + count

  1. 有序关联容器: multimap 

     1string search_item("Alain de Botton");        // 作者名
 2auto entries = authors.count(search_item);    // 书籍个数
 3auto iter = authors.find(search_item);        // 第一本书的位置
 4
 5while(entries)
 6{
 7    cout << iter->second << endl;             // 输出书名
 8    ++iter;                                   // 直接后移
 9    --entries;
10}

  2. 无序关联容器: unordered_multimap 

     1#include <string>
 2#include <iostream>
 3#include <unordered_map>
 4
 5using namespace std;
 6
 7int main()
 8{
 9    unordered_multimap<int, string> us{ {0, "start"},
10                                        {0, "begin"},
11                                        {1, "first"},
12                                        {3, "third"} };
13
14    cout << us.bucket_count() << endl;
15
16    auto cnt = us.count(0);
17    auto it = us.find(0);
18
19    for (; cnt > 0; ++it, --cnt)
20    {
21        cout << it->first << "\t" << it->second << endl;
22    }
23
24    return 0;
25}

    输出 

    5
0	start
0	begin

使用迭代器


lower_bound和upper_bound

返回迭代器

二者构成左闭合区间 [b, e)

允许关键字重复的关联容器 是否支持
multiset O
multimap O
unordered_multiset X
unordered_multimap X

不适用于无序关联容器

  • lower_bound

    迭代器指向第一个关键字不小于k的元素(闭区间下限); 如果关键字不在容器中, 指示拥有该关键字的新元素的插入位置 

    1c.lower_bound(b);

  • upper_bound

    迭代器指向第一个关键字大于k的元素(开区间上限); 如果关键字不在容器中, 指示拥有该关键字的新元素的插入位置 

    1c.upper_bound(e);

  • 示例

    1. 关键字不存在 

      元素序列: 1 2 3 5 6 7
关键字: 4

返回迭代器指向元素:
lower_bound = 5
upper_bound = 5

    2. 查找元素 

      1string search_item("Alain de Botton");        // 作者名
2
3for (auto beg = authors.lower_bound(search_item),
4        end = authors.upper_bound(search_item);
5    beg != end; ++beg)
6    cout << beg->second << endl;    // 输出书名
7
8// 如果关键字不在容器中, beg和end相等

equal_range

返回一对迭代器, 保存在pair中

  1. 关键字存在: 第一个迭代器指向第一个与关键字匹配的元素，第二个迭代器指向最后一个匹配元素的后继
  2. 关键字不存在: 两个迭代器相等, 指向关键字可以插入的位置 
1c.equal_range(k);

  • 示例

    1. 有序关联容器: multimap 

      1string search_item("Alain de Botton");        // 作者名
2
3for (auto pos = authors.equal_range(search_item);        
4        pos.first != pos.second;
5        ++pos.first)
6    cout << pos.first->second << endl;

    2. 无序关联容器: unordered_multimap 

       1#include <string>
 2#include <iostream>
 3#include <unordered_map>
 4
 5using namespace std;
 6
 7int main()
 8{
 9    unordered_multimap<int, string> us{ {0, "start"},
10                                        {0, "begin"},
11                                        {1, "first"},
12                                        {3, "third"} };
13
14    auto range = us.equal_range(0);
15    for(; range.first != range.second; ++range.first)
16    {
17        cout << range.first->first << "\t" << range.first->second << endl;
18    }
19
20    return 0;
21}

      输出 

      0	start
0	begin
  • 上一篇 关联容器: 无序关联容器


    • Tess   Hugo

    六一的部落格 © 2023-2024   CC BY-NC-SA 4.0