/MiniSTL

Tiny STL based on SGI STL

Primary LanguageC++MIT LicenseMIT

MiniSTL

本仓库原是《STL源码剖析》一书的代码合集,后续在其基础上运用部分C++17特性进行了代码改写。
最终希望参考SGI STL SOURCEfolly src 实现一个MiniSTL。

学习计划

针对sgi stl srcfolly src,有学习计划如下:

  • 第一阶段:通读《STL源码剖析》全文,了解数据结构的底层实现与算法流程,针对书本完成代码撰写与整理。
  • 第二阶段:补全各容器实现。
  • 第三阶段:针对现有内容撰写完备的单元测试。
  • 第四阶段:逐步完善现有实现完成一个简易STL。(进行中)
  • 最终阶段:尝试改进现有实现,并与std做性能对比,分析原因。

目录

  1. 空间适配器(allocator)

构造析构工具(construct.h)

二级空间适配器(alloc.h)

内存基本处理工具(uninitialized.h)

  1. 迭代器与traits编程技法(iterator && traits)

iterator_traits(stl_iterator.h)

type_traits(type_traits.h)

  1. 序列式容器(sequence containers)

vector(stl_vector.h)

list(stl_list.h)

deque(stl_deque.h)

stack(stl_stack.h)

queue(stl_queue.h)

priority_queue(stl_priority_queue.h)

slist(slist.h)

  1. 关联式容器(associattive containers)

rb_tree(rb_tree.h)

set(stl_set.h)

map(stl_map.h)multiset(stl_multiset.h)

multimap(stl_multimap.h)

hashtable(hashtable.h)

hashset(hashset.h)

hashmultiset(hash_multiset.h)

hashmultimap(hash_multimap.h)

  1. 算法(algorithm)

数值算法(stl_numeric.h)

基本算法(stl_algobase.h)

set相关算法(stl_algoset.h)

heap算法(heap_algorithm.h)

其他算法(stl_algo.h)

  1. 函数对象(function object)

函数对象(function.h)

  1. 配接器(adapter)

 容器类配接器(stackqueue)

 迭代器配接器(insert_iteratorreverse_iteratoristream_iterator)

 函数配接器(not1not2bind1stbind2ndcompose1compose2ptr_fun...)

  1. 智能指针(smart_pointer)

shared_ptr(shared_ptr.h)
unique_ptr(unique_ptr.h)

编译环境

OS:macOS Monterey 12.1

CXX_Compiler:Apple clang version 13.0.0

Cmake:3.21.4

CppVersion:C++17

编译流程

  1. git clone this repo
  2. cd $work_path/MiniSTL && mkdir build && cd build;
    cmake .. && make;
  3. libSTL.a is in $work_path/MiniSTL/build/Source

运行单测

  1. run unit_test need install gtest
  2. git clone this repo
  3. cd $work_path/MiniSTL && mkdir build && cd build;
    cmake .. -DENABLE_MINISTL_TEST=ON && make;
  4. run exec file TEST in $work_path/MiniSTL/build/Test

LICENSE

MIT.