C++项目笔记——MyTinySTL(1)概述

项目地址：ww1820/MyTinySTL: A tiny STL in C++11，练手项目 (github.com)

STL（Standard Template Library）

• C++ Standard Library，C++ 标准库
  • C++ Standard Template Library，C++ 标准模板库

STL 是 C++ 标准库的一部分，不用单独安装。. C++ STL 借助模板（Template）把常用的 数据结构 及其算法都实现了一遍，并且做到了数据结构和算法的分离（GP vs. OOP）。

C++标准库以头文件的形式呈现：

• 新式C++头文件不带.h 后缀，如#include<vector>
• 旧式C++头文件带.h 后缀，如#include<stdio.h>
• 新式头文件内的组件封装于namespace std
• 旧式头文件内的组件不封装于namespace std

六大组件

1. 分配器（Allocators）：内存管理。
2. 迭代器（Iterators）：泛化的指针，算法通过迭代器访问容器中的数据。
3. 容器（Containers）：封装了大量常用的数据结构。
4. 算法（Algorithms）：定义了一些常用算法，处理数据。
5. 仿函数（Functors）：具有函数特质的对象（重载operator()的类）。
6. 适配器（Adapters）：修改接口。

容器的分类与结构

• 顺序容器：
  • Array：长度固定的数组，存储空间连续，支持随机访问
  • Vector：动态数组，存储空间连续，支持随机访问
  • Deque：双端队列，存储空间分段连续，支持随机访问
  • List：双向链表，存储空间不连续，不支持随机访问
  • Forward-List：单向链表，存储空间不连续，不支持随机访问
• 关联容器：红黑树实现，有序。Multi的key可以重复
  • Set/MultiSet
  • Map/MultiMap
• 无序容器：哈希表（Separate Chaining）实现
  • Unoedered Set/MultiSet
  • Unoedered Map/MultiMap

1. C++ Primer 中指出 string 是与vector相似的容器，但专门用于保存字符。随机访问块。在尾部插入/删除速度快。

2. deque由若干段连续空间串接而成，一旦有必要在deque的头部或尾端增加新的空间，便配置一段定量连续的空间，串接在deque的头部或尾端。deque的最大任务，就是在这些分段连续的空间上维护其整体连续的假象，并提供随机存取的接口。

   deque首次插入一个元素，默认会动态分配512字节空间，当这512字节空间用完后，它会再动态分配自己另外的512字节空间，然后虚拟地连在一起。deque的随机访问和遍历性能比vector差。

测试

主要文件结构

MyTinySTL
│      alloc.h       // 分配器
│      allocator.h   
│      construct.h
│      uninitialized.h
│      memory.h
│      iterator.h    // 迭代器
│      type_traits.h // 萃取器
│      list.h        // 容器
│      vector.h
│      deque.h
│      rb_tree.h
│      set.h
│      map.h
│      hashtable.h
│      unordered_map.h
│      unordered_set.h
│      astring.h
│      basic_string.h
│      queue.h
│      stack.h
│      algo.h		 // 算法
│      algobase.h
│      algorithm.h
│      numeric.h
│      heap_algo.h
│      set_algo.h
│      functional.h  //仿函数
│      exceptdef.h   //其他
│      util.h
│
└─Test       	     // 测试文件
    │  test.cpp      // 程序入口
    │  algorithm_performance_test.h
    │  algorithm_test.h
    │  deque_test.h
    │  list_test.h
    │  map_test.h
    │  queue_test.h
    │  set_test.h
    │  stack_test.h
    │  string_test.h
    │  test.h
    │  unordered_map_test.h
    │  unordered_set_test.h
    │  vector_test.h
    │  CMakeLists.txt
    │  README.md

测试程序

int main()
{

  using namespace mystl::test;

  std::cout.sync_with_stdio(false);

  //算法测试: 包含了 mystl 的 81 个算法测试 algorithm_test.h
  RUN_ALL_TESTS();
  // 仅仅针对 sort, binary_search 做了性能测试 algorithm_performance_test.h
  algorithm_performance_test::algorithm_performance_test();
  // vector test : 测试 vector 的接口与 push_back 的性能
  vector_test::vector_test();
  // list test : 测试 list 的接口与 insert, sort 的性能
  list_test::list_test();
  // deque test : 测试 deque 的接口和 push_front/push_back 的性能
  deque_test::deque_test();
  // queue test : 测试 queue, priority_queue 的接口和它们 push 的性能
  queue_test::queue_test();
  queue_test::priority_test();
  // stack test : 测试 stack 的接口 和 push 的性能
  stack_test::stack_test();
  // map test : 测试 map, multimap 的接口与它们 insert 的性能
  map_test::map_test();
  map_test::multimap_test();
  // set test : 测试 set, multiset 的接口与它们 insert 的性能
  set_test::set_test();
  set_test::multiset_test();
  // unordered_map test : 测试 unordered_map, unordered_multimap 的接口与它们 insert 的性能
  unordered_map_test::unordered_map_test();
  unordered_map_test::unordered_multimap_test();
  // unordered_set test : 测试 unordered_set, unordered_multiset 的接口与它们 insert 的性能
  unordered_set_test::unordered_set_test();
  unordered_set_test::unordered_multiset_test();
  // string test : 测试 string 的接口和 insert 的性能
  string_test::string_test();

#if defined(_MSC_VER) && defined(_DEBUG)
  _CrtDumpMemoryLeaks();
#endif // check memory leaks
}

关于宏的两点：

1. 特殊符号 # 和 ##

   # ： 预处理时，将#后连接的实参字符串化

   ## ：一种分隔连接方式，它的作用是先分隔，然后进行强制连接。在普通的宏定义中，预处理器一般把空格解释成分段标志，对于每一段和前面比较，相同的就被替换。但是这样做的结果是，被替换段之间存在一些空格。如果我们不希望出现这些空格，就可以通过添加一些##来替代空格。

   例如：

   #define TYPE1(type,name)   type name_##type##_type
   #define TYPE2(type,name)   type name##_##type##_type
   
   TYPE1(int, c); // int 　name_int_type; (因为##号将后面分为 name_ 、type 、 _type三组，替换后强制连接)
   TYPE2(int, d); // int 　d_int_type;    (因为##号将后面分为 name、_、type 、_type四组，替换后强制连接)

2. 宏定义中的do{ }while(0)

   使用do{…}while(0)构造后的宏定义不会受到大括号、分号等的影响，总是会按你期望的方式调用运行。

// 测试案例的类名，替换为 test_case_TEST
#define TESTCASE_NAME(testcase_name) \
    testcase_name##_TEST

// 使用宏定义掩盖复杂的测试样例封装过程，把 TEXT 中的测试案例放到单元测试中
#define MYTINYSTL_TEST_(testcase_name)                        \
class TESTCASE_NAME(testcase_name) : public TestCase {        \
public:                                                       \
    TESTCASE_NAME(testcase_name)(const char* case_name)       \
        : TestCase(case_name) {};                             \
    virtual void Run();                                       \
private:                                                      \
    static TestCase* const testcase_;                         \
};                                                            \
                                                              \
TestCase* const TESTCASE_NAME(testcase_name)                  \
    ::testcase_ = UnitTest::GetInstance()->RegisterTestCase(  \
        new TESTCASE_NAME(testcase_name)(#testcase_name));    \
void TESTCASE_NAME(testcase_name)::Run()

// 简单测试的宏定义
#define TEST(testcase_name) \
  MYTINYSTL_TEST_(testcase_name)

/*
Run()后边没有写实现，是为了用宏定义将测试用例放入到 Run 的实现里，例如：
TEST(AddTestDemo)
{
EXPECT_EQ(3, Add(1, 2));
EXPECT_EQ(2, Add(1, 1));
}
上述代码将 { EXPECT_EQ(3, Add(1, 2)); EXPECT_EQ(2, Add(1, 1)); } 接到 Run() 的后面
*/

预处理阶段，上述代码在TEST 处展开后，TEST 后面{...} 的内容将拼接到 Run() 后，成为Run() 的实现。

MYTINYSTL_TEST_(testcase_name) 展开后声明一个名为 testcase_name_TEST 的类（testcase_name 是形参），13行声明了一个静态指针常量成员，指向一个测试用例，16行对该静态成员进行定义，并将其加入到用例集合中。

参考

[1] MyTinySTL阅读笔记—概述_xiaoxiao涛的博客-CSDN博客_mytinystl源码分析

[2] Alinshans/MyTinySTL: Achieve a tiny STL in C++11 (github.com)

[3] Home · Alinshans/MyTinySTL Wiki (github.com)

[4] C语言宏高级用法 总结 - Rabbit_Dale - 博客园 (cnblogs.com)