STL源码阅读(七)-程序员宅基地

技术标签：关联容器 SGI C/C++学习 slist STL

STL源码阅读(七) (SGI STL v3.3)

`stl_set.h (<set>)`

set使用红黑树实现，每个键值都不相同，且按序存储。注意operator=(即_Rb_tree的实现)先销毁赋值号左边的set，
然后将右边的set拷贝给左边的set，而不是原值替换。

set的所有函数都是用_Rb_tree的函数实现的，相当于_Rb_tree的一个包装类。

`stl_multiset.h (<set>)`

multiset使用红黑树实现，键值可重复，按序存储。相当于_Rb_tree的一个包装类。

`stl_map.h (<map>)`

使用红黑树实现，键值不可重复，按键值顺序排序。相当于_Rb_tree的一个包装类。
注意：嵌套类value_compare实际比较的还是键值。

`stl_multimap.h (<map>)`

使用红黑树实现，和map基本相同，只不过是可以重复相同的键值。

`stl_slist.h (<forward_list> C++11)`

和list相比，实现方式不同，list通过双向环状链表实现，而slist使用单向链表实现。另外，slist的
迭代器类型是前向迭代器，和list的双向迭代器相比更加节省内存。不足之处是slist不支持元素的快速随机访问。

// slist结点
struct _Slist_node_base
{
  _Slist_node_base* _M_next;
};

template <class _Tp>
struct _Slist_node : public _Slist_node_base
{
  _Tp _M_data;
};


// slist内存分配器
// 在创建链表时，多分配一个结点(_M_head)用于指向整个链表。


// slist迭代器，前向迭代器，只有++这一个单步方向


// 归并排序
template <class _Tp, class _Alloc>
void slist<_Tp,_Alloc>::sort()
{
  if (this->_M_head._M_next && this->_M_head._M_next->_M_next) {
    slist __carry;
    slist __counter[64];
    int __fill = 0;
    while (!empty()) {
      __slist_splice_after(&__carry._M_head,
                           &this->_M_head, this->_M_head._M_next);
      int __i = 0;
      while (__i < __fill && !__counter[__i].empty()) {
        __counter[__i].merge(__carry);
        __carry.swap(__counter[__i]);
        ++__i;
      }
      __carry.swap(__counter[__i]);
      if (__i == __fill)
        ++__fill;
    }

    for (int __i = 1; __i < __fill; ++__i)
      __counter[__i].merge(__counter[__i-1]);
    this->swap(__counter[__fill-1]);
  }
}

// 其它函数看看参考手册，了解其功能就能知道其怎么实现的了，没什么好说的了。

参考资料

本文链接：https://blog.csdn.net/corfox_liu/article/details/52134747

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

python简易爬虫v1.0-程序员宅基地

文章浏览阅读1.8k次，点赞4次，收藏6次。python简易爬虫v1.0作者：William Ma (the_CoderWM)进阶python的首秀，大部分童鞋肯定是做个简单的爬虫吧，众所周知，爬虫需要各种各样的第三方库，例如scrapy, bs4, requests, urllib3等等。此处，我们先从最简单的爬虫开始。首先，我们需要安装两个第三方库：requests和bs4。在cmd中输入以下代码：pip install requestspip install bs4等安装成功后，就可以进入pycharm来写爬虫了。爬

安装flask后vim出现：error detected while processing /home/zww/.vim/ftplugin/python/pyflakes.vim:line 28_freetorn.vim-程序员宅基地

文章浏览阅读2.6k次。解决方法：解决方法可以去github重新下载一个pyflakes.vim。执行如下命令git clone --recursive git://github.com/kevinw/pyflakes-vim.git然后进入git克降目录，./pyflakes-vim/ftplugin,通过如下命令将python目录下的所有文件复制到~/.vim/ftplugin目录下即可。cp -R ...._freetorn.vim

HIT CSAPP大作业：程序人生—Hello‘s P2P-程序员宅基地

文章浏览阅读210次，点赞7次，收藏3次。本文简述了hello.c源程序的预处理、编译、汇编、链接和运行的主要过程，以及hello程序的进程管理、存储管理与I/O管理，通过hello.c这一程序周期的描述，对程序的编译、加载、运行有了初步的了解。_hit csapp

18个顶级人工智能平台-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏27次。来源：机器人小妹　　很多时候企业拥有重复，乏味且困难的工作流程，这些流程往往会减慢生产速度并增加运营成本。为了降低生产成本，企业别无选择，只能自动化某些功能以降低生产成本。　　通过数字化..._人工智能平台

electron热加载_electron-reloader-程序员宅基地

文章浏览阅读2.2k次。热加载能够在每次保存修改的代码后自动刷新 electron 应用界面，而不必每次去手动操作重新运行，这极大的提升了开发效率。安装 electron 热加载插件热加载虽然很方便，但是不是每个 electron 项目必须的，所以想要舒服的开发 electron 就只能给 electron 项目单独的安装热加载插件[electron-reloader]:// 在项目的根目录下安装 electron-reloader，国内建议使用 cnpm 代替 npmnpm install electron-relo._electron-reloader

android 11.0 去掉recovery模式UI页面的选项_android recovery 删除部分菜单-程序员宅基地

文章浏览阅读942次。在11.0 进行定制化开发，会根据需要去掉recovery模式的一些选项就是在device.cpp去掉一些选项就可以了。_android recovery 删除部分菜单

随便推点

echart省会流向图（物流运输、地图）_java+echart地图+物流跟踪-程序员宅基地

文章浏览阅读2.2k次，点赞2次，收藏6次。继续上次的echart博客，由于省会流向图是从echart画廊中直接取来的。所以直接上代码<!DOCTYPE html><html><head> <meta charset="utf-8" /> <meta name="viewport" content="width=device-width,initial-scale=1,minimum-scale=1,maximum-scale=1,user-scalable=no" /&_java+echart地图+物流跟踪