首页 > 其他分享 >Cpp Primer:Sec 11:关联容器

Cpp Primer:Sec 11:关联容器

时间:2022-12-21 11:24:32浏览次数:49  
标签:11 map set word 迭代 容器 关键字 Sec Cpp

Sec11 关联容器

  • 两个主要的关联容器:

    • map:key-value对,关键字起到索引的作用,值表示与索引关联的数据
      例子:字典
    • set:每个元素只包含一个关键字,set支持高效的关键字查询操作
  • STL提供8个关联容器

    按关键字有序保存元素
    map:				关联数组
    set:				关键字即值,只保存关键字
    multimap:			关键字可重复的map
    multiset:			关键字可重复的set
    无序集合(哈希阻止)
    unordered_map
    unordered_set
    unordered_multimap
    unordered_multiset
    
  • 在set中找单词

    set<string> exclude;
    if(exclude.find(word) == exclude.end()){
        ++word_cound[word];
    }
    

    find返一个迭代器,如果给定关键字在set中,迭代器指向关键字,否则,find返回尾后迭代器

11.2 关联容器概述

  • 定义set,只需指名关键词类型
    定义map,需要指名关键词和value类型

  • 关键字类型的要求

    对于有序容器,map,multimap,set和multiset,关键字类型必须定义元素比较的方法,默认情况是用<,但也可以自定义

    • 可以像一个算法提供我们自己定义的比较操作。所提供的操作必须在关键字类型上定义一个严格弱序。

    • 使用关键字类型的比较函数
      用来阻止一个容器中元素的操作的类型也是该容器类型的一部分。

      bool compareISBN(const Sales_data &lhs, const Sales_data &rhs) {
          return lhs.isbn() < rhs.isbn();
      }
      multiset<Sales_data, decltype(compareISBN)*>
          bookstore(compareISBN)
      

      常常用decltype指出自定义操作的类型,注意,当用decltype来获得一个函数指针类型时,必须加上一个*来指出我们要使用一个给定函数类型的指针。然后用compareISBN来初始化bookstore。这样添加元素的时候就可以使用自定义排序类型了

  • pair类型
    定义在头文件utility中。创建pair必须提供两个类型名。

    • 比较操作:
      是先比较first再比较second的

11.3 关联容器操作

key_type;		此容器类型的关键字类型
mapped_type;	每个关键字关联的类型,只适用于map
value_type;		对于set,与key_type相同,对于map,为pair<const key_type, mapped_type>
  • 关联容器迭代器
    解引用一个关联容器迭代器时,我们会得到一个类型为容器的value_type的值的引用。
    记得对map而言,value_type是一个pair类型,记得用first和second来访问。iter->first,iter->second

    • set的迭代器是const的
      set的元素仅可读

    • 遍历是按照字典序排列的。升序

    • map<int, int> m;
      auto it = m.begin();
      it->second = 0;
      
  • 算法:
    通常不用泛型算法。通常用自己定义的find。要快得多(hash)

  • 添加元素

    用insert,但是注意对于set和map来说,插入一个已经存在的元素对容器没有影响

    • 注意,对map插入元素,元素必须是pair

      // 向word_count插入word的4种方法
      word_count.insert({word, 1});
      word_count.insert(make_pair(word, 1));
      word_count.insert(pair<string, size_t>(word, 1));
      word_count.insert(map<string, size_t>::value_type(word, 1));
      

    用insert会返回一个迭代器,第一个first包含指向具有指定关键字的元素,以及一个指示插入是否成功的bool值
    如果bool值为false,可能是插入了重复的值

    • 对于multi容器,接受单个元素的insert操作返回一个指向新元素的迭代器。无须返回bool值。
  • 删除元素
    erase有3个版本:

    • 传递一个迭代器
    • 传递一个迭代器对
    • 接受一个key_type参数,此版本删除所有匹配得给定关键字的元素,返回实际删除的元素数量
  • map的下标操作

    map<string, size_t> word_count;
    word_count['Anna'] = 1;
    

    注:使用一个不在容器内的下标,会添加这个容器并赋值!
    c.at(k),单纯的访问关键字为k的元素,带参数检查

    • 对map来说,迭代器解引用与下标运算返回的类型不是一样的
      对map下标运算,会获得mapped_type对象,当解引用时,得到value_type对象
  • 访问元素
    iset.find():返回一个迭代器,如果找到就是指向找到,如果未找到就返回尾迭代器
    关心特定元素是否已在容器。
    iset.count():返回元素个数

  • 注:下标操作和at操作,只适用于非const的map和unorder_map

  • lower_bound(k), upper_bound(k)
    返回迭代器,指向第一个关键字 不小于/不大于 k的元素
    则:使用相同的关键字调用l和u会得到一个迭代器范围!表示具有该关键字的范围

  • equal_rage(k):
    返回一个迭代器pair,表示关键字等于k的元素范围,若k不存在,则pair俩成员均为尾迭代器

  • 为什么建议对map使用find代替下标操作:
    对map和unordered_map类型,如果下标访问一个不存在的元素,则会加入进去!!!!

11.4 无序容器

原理一般是哈希 hash

  • 操作:
    find,insert等
  • 存储上组织为 桶
    bucket
    每个桶保存0或者多个元素
// 桶接口
c.bucket_count();
c.max_bucket_count();
c.bucket_size(n);
c.bucket(k);

// 桶迭代
local_iterator;	// 可以用访问桶中元素的迭代器版本
const_local_iterator;
c.begin(n), c.end();
c.cbegin(n), c.cend();

// 哈希策略
c.load_factor();
c.max_load_factor();
c.rehash(n);
c.reverse(n);

注意:hash函数是可重载的

标签:11,map,set,word,迭代,容器,关键字,Sec,Cpp
From: https://www.cnblogs.com/orangestar/p/16995833.html

相关文章

  • Cpp Primer:Sec 8, 9, 10
    目录Sec8IO库8.1IO类8.2文件输入输出8.3stringstreamSec9顺序容器9.4Vector对象如何增长?Sec10泛型算法10.2初识10.3定制操作10.3.3lambda捕获与返回10.4再探迭......
  • Cpp Primer:Sec 12:动态内存
    目录Sec12动态内存12.1动态内存与智能指针12.2动态数组Sec12动态内存12.1动态内存与智能指针new:在动态内存中为对象分配空间,并返回一个指向该对象的指针delete:......
  • Cpp Primer:Sec 13:拷贝控制
    目录Sec13拷贝控制13.1拷贝、赋值与销毁13.2拷贝控制和资源管理13.3交换操作13.4拷贝控制示例13.5动态内存管理类13.6对象移动13.6.1右值引用13.6.2移动构造函数......
  • Cpp Primer:Sec 14:重载与类型转换
    目录Sec14重载运算与类型转换14.1基本概念14.2输入输出运算符14.9重载、类型转换与运算符Sec14重载运算与类型转换当运算符作用于类类型的运算对象时,可以通过运算符......
  • Cpp Primer:Sec 15:面向对象程序设计
    目录Sec15面向对象程序设计15.1OOP:概述15.2定义基类和派生类15.2.2定义派生类15.2.3类型转换与继承15.3虚函数15.4抽象基类15.5访问控制与继承15.6继承中的类作......
  • C++primer:Sec 1, 2, 3
    目录Sec1BeginSec2变量和基本类型2.1基本内置类型2.2变量2.3复合类型(CompoundType)2.4const限定符2.5处理类型Sec3字符串、向量和数组3.1using3.2string:3.3......
  • 11~12 集合、IO流
    11集合11.1算法和数据结构一、算法:可以解决具体的问题(解决流程),有设计解决的具体的流程(算法1、算法2),有评价这个算法的具体指标(时间复杂度、空间复杂度)二、数据结构:1.......
  • delphi11安卓权限的改变
    delphi11安卓权限的改变///<author>cxg2022-12-21</author>unituRights;interfaceusesSystem.Permissions,System.SysUtils,System.Types,System.UITyp......
  • D10.4开发的安卓程序,D11编译报错的解决方法
    D10.4开发的安卓程序,D11编译报错的解决方法如果用D11打开工程,10.4下很多自带的jar都已经被去除了如果立即编译的话,会报错:这个时候,你只要右键Libraries,在弹出的菜单中......
  • S1 - Lesson 113 - 114
    Words conductor[售票员] fare[车费]thebusfarethetrainfaretheairfareTickets,please.fare,please changecanyouchangeaten-poundnote?wher......