/mySTL

Learn the STL sources and try to write the STL

Primary LanguageC++OtherNOASSERTION

[toc]

mySTL

学习C++ STL中底层相关的数据结构和算法，深入学习C++ Template编程，并实现对应的STL容器以及相关组件

环境

  • 操作系统 Win 10/11
  • 编译器 Vscode + gcc

主要容器与算法

  • allocator （空间配置器）
    • allocator/alloc（STL容器的整个底层内存分配与释放，以字节为单位，供allocator类使用）
    • construct （全局函数，实现construct和destroy的方式）
    • my_uninitialized（声明三个全局函数，用于对未初始化空间构造元素，fill or copy 方式）
  • iterator（迭代器相关，type_traits萃取不同型别属性）
  • container（基本容器）
    • vector 向量
    • list 双向链表
    • slist单向链表
    • stack
    • queue
    • set
    • map
    • hash_set
  • algorithm（基本常用的算法）
    • fill_n() 的函数体
    • fill(first, last, val)
    • copy()
    • copy_backward()

文件夹介绍

容器测试

  • 测试平台

    • 操作系统 Win 10/corei5 10th
    • 编译器 Vscode + gcc

  • 基本API测试

  • 性能测试

    • vector

      [--------------------- Performance Testing ---------------------]
|---------------------|-------------|-------------|-------------|
|        insert       |    100000   |   1000000   |  10000000   |
|         std         |      3ms    |     26ms    |    256ms    |
|        mystl        |      2ms    |     22ms    |    255ms    |
|---------------------|-------------|-------------|-------------|

    • list

      [--------------------- Performance Testing ---------------------]
|---------------------|-------------|-------------|-------------|
|        insert       |    100000   |   1000000   |  10000000   |
|         std         |     10ms    |    101ms    |    993ms    |
|        mystl        |      5ms    |     52ms    |    516ms    |
|---------------------|-------------|-------------|-------------|
[ PASSED ]
[------------------ End container test : list -------------------]

|---------------------|-------------|-------------|-------------|
|         sort        |     20000   |    200000   |   2000000   |
|         std         |     11ms    |    121ms    |   1706ms    |
|        mystl        |      5ms    |     73ms    |   1120ms    |
|---------------------|-------------|-------------|-------------|
      • std对应的sort使用的是快排的方法，mystl对应的sort使用的是归并排序的方法。

    • set

      [--------------------- Performance Testing ---------------------]
|---------------------|-------------|-------------|-------------|
|        insert       |    100000   |   1000000   |  10000000   |
|         std         |     47ms    |    386ms    |   3849ms    |
|        mystl        |     55ms    |    550ms    |   5467ms    |
|---------------------|-------------|-------------|-------------|
      • stl底层是红黑树，mystl底层是AVL树实现的，性能会有一定的差距

    • map

      [--------------------- Performance Testing ---------------------]
|---------------------|-------------|-------------|-------------|
|        insert       |    100000   |   1000000   |  10000000   |
|         std         |     44ms    |    401ms    |   3984ms    |
|        mystl        |     57ms    |    566ms    |   5537ms    |
|---------------------|-------------|-------------|-------------|
      • 和set底层是同样的AVL树实现的

    • hash_set

      [--------------------- Performance Testing ---------------------]
|---------------------|-------------|-------------|-------------|
|        insert       |    100000   |   1000000   |  10000000   |
|         std         |     21ms    |    143ms    |   1136ms    |
|        mystl        |      9ms    |     63ms    |    584ms    |
|---------------------|-------------|-------------|-------------|

参考资料