Skip to content

zSirius/iSTL

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

42 Commits
.vscode
.vscode
 
 
include
include
 
 
src
src
 
 
test
test
 
 
.gitignore
.gitignore
 
 
README.md
README.md
 
 

Repository files navigation

iSTL

以学习标准库STL实现原理、C++模版编程、元编程为目的编写的简易版STL。

目前已实现：

  • 空间配置器allocator
  • 容器vector、deuqe、list、map及其迭代器
  • 容器适配器stack、queue、priority_queue
  • 迭代器适配器reverse_iterator
  • uninitialized族初始化函数
  • string类及其接口

实现细节说明

空间配置器 alloc / allocator

  • 容器使用空间配置器进行内存分配，实现内存分配和对象构造的分离
  • 空间配置器alloc底层使用malloc申请内存，并使用placement new 运算符在内存上调用需要初始化对象的构造函数
  • 对于小内存 (<=128B) ，采用分离适配，以大小类为依据维护成多条空闲内存块的自由链表，避免频繁调用malloc分配小内存
  • alloctor是对alloc进一步封装的模板类，上层容器直接使用alloctor申请和释放内存

string

  • string采用了短字符串优化技术（Small String Optimization，SSO），参考libc++/llvm/clang的实现，采用空间利用率最高的一种SSO实现方式，在64bit机器上，本地缓存区高达22字节。该实现与机器相关，本项目基于64bit小端序机器实现
  • 对于长字符串，采用传统的eager copy方式，在堆上分配内存
  • string的内存增长策略与llvm/clang实现一致，详见istl::string::getNewCapacity函数注释
  • 采用SSO技术的底层数据结构：
            0        7                            63
            +-+------+-----------------------------+
            |0| size |          buffer             |
            +-+------+-----------------------------+
            |               buffer                 |
            +--------------------------------------+
            |               buffer                 |
            +--------------------------------------+

            0                                     63
            +-+------------------------------------+
            |1|            capacity                |
            +-+------------------------------------+
            |                size                  |
            +--------------------------------------+
            |                start                 |-> data
            +--------------------------------------+

          union {
            struct {
                unsigned char _buffer_size; 
                char _buffer[_SSO_THRESHOLD+1]; 
            };
            struct {
                size_t _capacity; 
                size_t _size; 
                char* _start; 
            };
          };

vector

  • vector是支持动态扩容的动态数组，内存扩张策略为倍增策略
  • 底层数据结构是连续的地址空间，当地址空间不够用的时候，会重新申请新的地址空间，并对迁移源数据到新的地址空间，这会导致之前获取的迭代器失效

deque

  • deque底层数据结构为一个块指针数据与多个连续的内存块：
              Block Pointer Array:
              +---+---+---+---+
              | * | * | * | * | ......
              +---+---+---+---+
                |   |   
                |   +---+
                v       v
              +---+   +---+
      Block:  | 1 |   | 2 |   ......
              +---+   +---+
  • 底层内存块内部地址连续，内存块之前地址不连续
  • 块的大小可以根据具体场景设计为动态或者固定，本项目块大小固定
  • deque扩容性能优秀，适合作为队列、栈等适配器的底层数据结构
  • deque的迭代器支持随机访问，但是deque的随机访问性能并不优秀

list

  • list为双向链表，为支持反向迭代器，底层实际设计为双向循环链表
  • 迭代器end()以及rend()指向dummy node
  • list的sort函数为迭代版的归并排序
        begin()    last valid node                       
      +------+     +------+     +------+                 
    +->| node | <-> | node | <-> | tail |<--------------+
    |  +------+     +------+     +------+               |
    |                          end() is a dummy node    |
    |                                                   |
    +---------------------------------------------------+

map

  • map底层为红黑树，实际上map就是红黑树接口的简单封装
  • 底层红黑树支持insert_unque和insert_equal，可以很容易的封装为map、multimap、set以及multiset
  • 为便于处理边界情况以及为支持反向迭代器，map底层的红黑树在实现上相较于传统红黑树，根结点之上多了一个头结点
  • 头节点left指向树中元素最小的结点，right指向树中元素最大的结点，parent指向根结点
  • 迭代器end()以及rend()指向头结点

迭代器

  • 每个容器在实现的时候都实现了对应的迭代器
  • 反向迭代器是一个迭代器适配器类，接受一个双向迭代器
  • iterator 和 const_iterator的设计：
  1. _Rb_tree的迭代器实现方式：设计成独立的两个类。
  2. list的迭代器实现方式：将迭代器声明成template<typename T, typename Ref, typename Ptr>的形式，通过参数Ref和Ptr来实现对返回元素cons属性的控制

uninitialized族函数

  • 实现了uninitialized_move、uninitialized_copy等函数，可以安全的在未初始化内存上构造对象
  • 运用模板元编程，在编译时根据数据是否是平凡可复制的（is_trivial）来选取不同的代码

性能测试及单元测试

性能测试以标准库为基准，单元测试使用GTest编写，验证实现与标准库实现行为一致。

vector

数据量：1000w

操作 std::vector (ms) istl::vector (ms)
push_back 252.100 163.042
access 0 0
insert at begin 37.7044 53.0964
insert at middle 16.776 25.672
insert at end 0 0
batch insert 193.684 216.244
erase at begin 84.0654 78.3162
erase at middle 59.013 66.5972
erase at end 0 0
batch erase 102.978 99.0688
clear 0 0
pop_back 0 0

数据量：100w

操作 std::vector (ms) istl::vector (ms)
push_back 25.4707 13.4007
access 0 0
insert at begin 3.4049 5.266
insert at middle 1.5899 2.5601
insert at end 0 0
batch insert 14.240 14.8551
erase at begin 6.8213 6.7611
erase at middle 5.1276 5.0698
erase at end 0 0
batch erase 8.9734 9.1618
clear 0 0
pop_back 0 0

数据量：10w

操作 std::vector (ms) istl::vector (ms)
push_back 2.7921 1.4591
access 0 0
insert at begin 0.432 0.6691
insert at middle 0.1847 0.3165
insert at end 0 0
batch insert 1.7586 1.9185
erase at begin 1.0973 1.0242
erase at middle 0.7915 0.7801
erase at end 0 0
batch erase 1.0126 1.0665
clear 0 0
pop_back 0 0

deque

数据量：1000w

操作 std::deque (ms) istl::deque (ms)
push_back 299.153 1091.64
push_front 527.323 1374.08
access 0 0
clear 253.167 0
pop_back 255.377 57.3192
pop_front 124.511 69.338

数据量：100w

操作 std::deque (ms) istl::deque (ms)
push_back 18.7634 113.692
push_front 24.4703 114.444
access 0 0
clear 20.8797 0
pop_back 19.4013 5.7256
pop_front 10.3751 5.9401

数据量：10w

操作 std::deque (ms) istl::deque (ms)
push_back 2.3962 14.317
push_front 2.6543 14.1437
access 0 0
clear 0.1796 0
pop_back 1.5459 0.7167
pop_front 0.8656 0.7901

list

数据量：100w

操作 std::list (ms) istl::list (ms)
push_back 573.282 984.960
push_front 577.485 998.222
access 0 0
insert 0.0017 0
erase 0.0005 0
clear 1353.6 1764.3
pop_back 503.495 831.038
pop_front 854.853 875.957
splice 0 463.229
remove 17.5232 507.249
unique 514.187 2003.36
merge 20.2024 1927.83
sort 11551.5 128462
reverse 2054.5 2569.59

数据量：10w

操作 std::list (ms) istl::list (ms)
push_back 65.4247 80.2646
push_front 72.7535 77.851
access 0 0
insert 0.0024 0
erase 0.0003 0
clear 154.825 143.157
pop_back 60.1328 70.6258
pop_front 95.4812 70.0446
splice 0 40.7983
remove 1.767 40.9219
unique 57.4371 155.756
merge 2.0643 162.891
sort 558.344 8900.99
reverse 125.341 231.669

数据量：1w

操作 std::list (ms) istl::list (ms)
push_back 7.23555 3.49065
push_front 7.22295 4.01985
access 0 0
insert 0.0005 0
erase 0.00005 0
clear 14.9949 6.487
pop_back 6.014 3.20425
pop_front 8.3887 3.50095
splice 0 1.1034
remove 0.1583 1.1097
unique 4.1031 6.00735
merge 0.1449 4.34845
sort 23.9327 217.333
reverse 6.8625 9.2808

priority_queue

数据量：1000w

操作 std::priority_queue (ms) istl::priority_queue (ms)
push 35.3153 39.0924
top 0 0
pop 851.453 890.184

数据量：100w

操作 std::priority_queue (ms) istl::priority_queue (ms)
push 3.9278 5.312
top 0 0
pop 86.7977 101.117

数据量：10w

操作 std::priority_queue (ms) istl::priority_queue (ms)
push 0.4845 0.54925
top 0 0
pop 6.7534 9.15055

map

数据量：1000w

操作 std::map (ms) istl::map (ms)
insert 2533.73 2592.7
find 0 0
erase 2393.2 928.377

数据量：100w

操作 std::map (ms) istl::map (ms)
insert 231.612 191.148
find 0 0
erase 215.613 58.642

数据量：10w

操作 std::map (ms) istl::map (ms)
insert 17.9147 12.163
find 0 0
erase 17.4782 4.7374

code sum

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
C/C++ Header                    18            606            159           3083
C++                             13            530            890           1581
Markdown                         1             69              0            280
JSON                             4              1              0            153
-------------------------------------------------------------------------------
SUM:                            36           1206           1049           5097
-------------------------------------------------------------------------------

About

参考c++标准库stl实现的simple stl

Resources

Readme
Activity

Stars

0 stars

Watchers

1 watching

Forks

0 forks
Report repository

Releases

No releases published

Packages

 
 
 

Contributors

Languages