/TinySTL

基于C++11的简易STL标准库

Primary LanguageC++

TinySTL

项目简介

  基于C++11的简易STL标准库，主要参考侯捷老师《STL源码剖析》的SGI版本以及我的开发环境gcc 5.4.0的libstdc++版本，实现了大部分STL中的容器与函数。实现过程中的一些收获，主要是《STL源码剖析》中没有提及的部分，会写在下方。

  本项目旨在学习常用数据结构与算法以及 C++ template 编程，目前代码约7K行，使用中文文档与中文注释，忽略掉一些针对多线程优化的代码和异常处理，仍存在许多不足与bug，会一直进行维护，修复发现的bug。

实现进度

功能模块

  1. allocator.h：空间分配器，包括 malloc_alloc 和 pool_alloc

    • malloc_alloc 直接使用 malloc() 分配内存
    • pool_alloc 使用基于 free-list 的内存池实现，容器缺省使用 pool_alloc 分配内存

  2. construct.h：标准构造/析构函数

  3. type_traits.h：POD与非POD类型萃取器，基于g++ 5.4.0中的 integral_constant 等编译器内置类型计算

  4. iterator.h：迭代器萃取器以及迭代器全局函数

  5. uninitialized.h：内存初始化函数

  6. vector.h

  7. list.h

  8. 基于deque.h的stack.h和queue.h

  9. heap.h

  10. 基于tree.h的set.h和map.h

  11. 基于hashtable.h的unordered_set.h和unordered_map.h

  12. algorithm.h：泛型函数

测试模块

  1. test_vector.cpp

  2. test_list.cpp

  3. test_deque.cpp

  4. test_heap.cpp

  5. test_tree.cpp

  6. test_hashtable.cpp

  测试包括容器的所有成员函数测试以及主要接口的效率测试，发现自己重写的 TinySTL 容器效率要比 gcc 5.4.0 的 libstdc++ 版本里的容器好上一些。

待开发模块

  1. algorithm.h中的一系列算法待补完