Note03--STL容器

2017-01-14 19:44:18来源:CSDN作者:myonelotus人点击

第七城市
  1. Vector:适合需要随机访问元素的情况
    (1) 保存元素序列,提供对这些元素的随机访问。
    (2) 元素保存在连续内存中。
    (3) 能够在Vector尾部快速地插入和删除元素,在其他位置(非尾部)插入和删除操作比较慢,因为必须调整元素位置。Vector提供了任意元素的快速访问(常量时间)。
    (4) 如果在程序中需要快速访问元素,但不会频繁在中间添加或删除元素,应该使用Vector;一个好的经验法则是在本来需要使用数组的地方使用Vector。
    (5) 标准库为vector对象提供的内存分配策略为:创建空的vector对象时容量为0;当现有容量用完后,重新分配空间时容量的增幅为原容量的1/2,如果增幅小于1,则取1,;reverse操作将容量设定为指定大小。
  2. List:适合需要在容器的中间位置插入和删除元素的情况
    (1) 与数组和Vector一样,List保存了元素的序列,但List的元素不一定保存在连续内存中。
    (2) List中的每个元素都指定了如何在List中找到前一个和后一个元素(通常是通过指针)。
    (3) 如果准备插入和删除大量元素,但是不要求快速查找,应该使用LIst。
    (4) List是双向链表,没有提供快速的随机访问。
  3. Deque:适合需要在容器的尾部或首部插入和删除元素的情况
    (1) 提供快速的元素访问(常量时间),在序列两端提供了快速插入和删除,在序列中间插入和删除的速度较慢(线性时间)。
    (2) 如果需要在两头快速插入和删除元素,还要求快速访问所有元素,应该使用Deque而不是Vector。
  4. Array
    (1) Array是对标准C风格数组的替代品,特别适合于大小固定的集合。
    (2) 好处:Array总是能知道自己的大小,不会自动转换为指针类型,从而避免了某些类型的Bug。没有提供插入和删除操作,但大小固定。
    (3) 访问速度快(常量时间)。
  5. Queue
    (1) “先入先出”。
    (2) “排队”时使用。
  6. Priority_queue
    (1) 提供Queue功能,但其中每个元素都有一个优先级。元素按照优先顺序从队列中移除。在优先级相同的情况下,删除元素的顺序没有定义。
    (2) Priority_queue插入和删除一般比简单的queue插入和删除要慢,因为只有对元素排序,才能支持优先级的顺序。
    (3) Priority_queue可以建模“带有意外的排队”,如:银行排队中,企业账户比普通顾客的优先级高。
  7. Stack
    (1) “后进先出”
  8. Set:适合需要使用键集合的情况
    (1) 元素唯一
    (2) 当需要保证元素顺序,插入/删除操作数组和查找操作数组接近,需要尽可能优化两种操作性能时,应该使用Set。
    (3) 插入和删除的操作比Vector快,但比List慢,查找操作比List快,但比Vector慢。
  9. Multiset
    (1) 存储重复元素
  10. Map:适合键-值对的集合的情况
    (1) key/value
    (2) count和find运算的区别:
    count返回map容器中给定键K的出现次数,其返回值只能是0或1,适合用于解决判断map容器中某键是否存在的问题;
    find返回在map容器中存在按给定键k索引的元素的情况下,返回指向该元素的迭代器,否则返回超出末端迭代器,适合用于解决在map容器中查找指定键对应元素的问题。
    map
multimap<string, string>::iterator iter = authors.find(searchItem);if (iter !=authors.end()){    authors.earse(searchItem);}typedef mutlimap<string, string>::iterator itType;

//确定该作者对应的mutlimap元素的范围

pair<itType, itType> pos = authors.equal_range(searchItem);if (pos.first != pos.second){    //删除该作者的所有作品    authors.erase(pos.first, pos.second);}
  1. 总结
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
    这里写图片描述
  2. 删除元素
    (1)使用 list、set 或 map遍历删除某些元素时:
    方法一:
std::list< int> List;std::list< int>::iterator itList;for( itList = List.begin(); itList != List.end(); ){     if( WillDelete( *itList) )     {         itList = List.erase( itList);     }         else             itList++;}
方法二:
std::list< int> List;      std::list< int>::iterator itList;      for( itList = List.begin(); itList != List.end(); )      {            if( WillDelete( *itList) )            {               List.erase( itList++ );            }            else               itList++;      }
(2)使用 vector、deque遍历删除元素时,也可以通过erase的返回值来获取下一个元素的位置
std::vector< int> Vec;      std::vector< int>::iterator itVec;      for( itVec = Vec.begin(); itVec != Vec.end(); )      {            if( WillDelete( *itVec) )            {                 itVec = Vec.erase( itVec);            }            else               itList++;      }
  1. 容器举例
    (1) 从一个文件中读入未知数目的单词,以生成英文句子。
    因为单词数量未知,且需要一非确定的顺序处理这些单词,所以采用vector实现最合适,因为vector支持随机访问。
    (2) 读入固定数目的单词,在输入时将它们按字母顺序插入到容器中。
    采用list实现最合适,因为需要在容器的任意位置插入元素。
    (3) 读入未知数目的单词。总是在容器尾部插入新单词,从容器首部删除下一个值。
    采用Deque实现最合适,因为总是在容器尾部插入新单词,从容器首部删除下一个值。
    (4) 从一个文件中读入未知数目的整数。对这些整数排序,然后把他们输出到标准输出设备。
    如果一边输入一边排序,则采用list实现最合适。因为在读入时需要在容器的任意位置插入元素;如果先读入所有整数,再进行排序,则采用vector最合适,因为进行排序最好有随机访问能力。
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台