Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1877309
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 2388
  • 用 户 组: 普通用户
  • 注册时间: 2016-12-21 22:26
个人简介

90后空巢老码农

文章分类

全部博文(184)

文章存档

2021年(26)

2020年(56)

2019年(54)

2018年(47)

2017年(1)

我的朋友

分类: C/C++

2018-08-24 23:31:23

今天来讲讲stl里面的序列容器,只讲主要vectorlistdeque,剩下的stackqueue底层是靠deque或者list实现的,heap底层是靠vector实现的,prior_queue底层又是靠heap实现的,所以说呢,感觉掌握了上述三个,就应该没啥大问题了。

先来讲vector,这个应该是大家最熟悉的了,底层实现基本上就是数组,但是多了个动态分配的功能,基本思想就是每一次容量满了之后,都会另辟一块空间来存放其包含的所有内容,其容量增长顺序一般是2n次幂的形式,248 …,其余的形式就跟数组没什么区别了,这里需要注意一点的是,如果插入元素之后再次调用原来的迭代器,是失效的,因为如果刚刚好该vector换了地址,并且扩容了,就不知道该怎么搞了~~~

list的实现是靠双向循环链表,之前一直以为是双向的,但是没有往循环链表上面去想,哎,被大神们的思想折服了,双向循环链表的话,其自身只需要一个节点的哨兵迭代器就可以搞定begin()end()两个了,其形状如下图:

这里我最想提到的一点就是list由于其链式结构,没办法用sort算法来进行排序,只能自己手写,下是listsort源代码:



点击(此处)折叠或打开

  1. template <class T, class Alloc>
  2. void list<T, Alloc>::sort() {
  3.   if (node->next == node || link_type(node->next)->next == node) return;
  4.   list<T, Alloc> carry;
  5.   list<T, Alloc> counter[64];
  6.   int fill = 0;
  7.   while (!empty()) {
  8.     carry.splice(carry.begin(), *this, begin());
  9.     int i = 0;
  10.     while(i < fill && !counter[i].empty()) {
  11.       counter[i].merge(carry);
  12.       carry.swap(counter[i++]);
  13.     }
  14.     carry.swap(counter[i]);
  15.     if (i == fill) ++fill;
  16.   }

  17.   for (int i = 1; i < fill; ++i) counter[i].merge(counter[i-1]);
  18.   swap(counter[fill-1]);
  19. }

说实话,第一遍没看懂,自己跟着走了一组数之后慢慢的明了了,其中carrycounter[i]均是辅助list,每次从当前链表中取出一个元素,和之前的元素归并,注意,counter[i]在这里只存储2^i个有序数,所以这里,list总共可以排序2^64  -1 个数~~

deque:关于deque,我只想说一下它的内部存储结构à分段连续。有没有很懵逼~~哈哈,刚开始看到这里的时候,我也很懵逼,但是看下图就OK了,会让你想起fs当中一个叫inode的东西~~

其中map是一个存放指针的数组,即指针的指针~~,它的每一个元素指向一块缓冲区buffer,这是用来实际存放数据的地方,其初始化工作是建立map,初始化其中间几个元素的buffer用来放数据,这样做的好处是,两面都可以进行数据的增减操作,如果当前map所指的buffer全部放满之后,仍然有数据进来,就需要向vector一样来进行前一工作啦~~~

阅读(2291) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~