My stl implementation code in c++ can be found here: my_stl

一、STL 六大组件体系

组件 说明 示例
Allocators 内存分配器，管理对象生命周期 std::allocator
Containers 容器，存储数据 vector, list, map
Iterators 迭代器，统一访问接口 RandomAccessIterator, BidirectionalIterator
Algorithms 泛型算法 sort, find, copy
Adapters 容器适配器 stack, queue, priority_queue
Functors / Traits 函数对象、类型萃取工具 less, iterator_traits

二、项目分层设计

1️⃣ 基础层：类型萃取与工具

  • ccstl::type_traits: is_integral, remove_reference, enable_if
  • ccstl::utility: move, forward, swap, pair
  • ccstl::iterator: 定义迭代器类别与 iterator_traits

这些是 STL 元编程和模板推导的基础。

关于iterator：

Tag 是一种“类型标签”，用来标识迭代器能做什么。

| 标签 能力 典型容器 / 迭代器 |
|——|——|——|
| input_iterator_tag | 只读、单向前进 | istream_iterator |
| output_iterator_tag | 只写、单向前进 | ostream_iterator |
| forward_iterator_tag | 可读写、单向、多遍扫描 | forward_list |
| bidirectional_iterator_tag | 可读写、双向移动 | list, set, map |
| random_access_iterator_tag | 可读写、随机访问 | vector, deque, string |

那么为什么用「类型标签」而不是「枚举值」？

因为模板是编译期机制，我们希望：

在编译时根据迭代器类型选择不同算法版本。

iterator_traits 的作用

iterator_traits 是另一个关键组件，
它的作用是提取迭代器的属性（如 value_type, difference_type, iterator_category）。

一个Iterator的实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H

#include <cstddef>

namespace mystl {

struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag : public input_iterator_tag {};
struct bidirectional_iterator_tag : public forward_iterator_tag {};
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

// Base iterator template
template <typename Category, typename T, typename Distance = ptrdiff_t,
          typename Pointer = T*, typename Reference = T&>
struct iterator {
    using iterator_category = Category;
    using value_type = T;
    using difference_type = Distance;
    using pointer = Pointer;
    using reference = Reference;
};

// Iterator traits  template
template <typename Iterator>
struct iterator_traits {
    using iterator_category = typename Iterator::iterator_category;
    using value_type = typename Iterator::value_type;
    using difference_type = typename Iterator::difference_type;
    using pointer = typename Iterator::pointer;
    using reference = typename Iterator::reference;
};

// Specialization for pointer types
template <typename T>
struct iterator_traits<T*> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = T*;
    using reference = T&;
};

// Specialization for const pointer types
template <typename T>
struct iterator_traits<const T*> {
    using iterator_category = random_access_iterator_tag;
    using value_type = T;
    using difference_type = ptrdiff_t;
    using pointer = const T*;
    using reference = const T&;
};


// calculate the distance between two iterators
template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last) {
    using category = typename iterator_traits<InputIterator>::iterator_category;
    return distance_impl(first, last, category());
}

// position of the iterator
template <typename InputIterator, typename Distance>
void advance(InputIterator& it, Distance n, input_iterator_tag) {
    while (n--) ++it;
}


template <typename BidirectionalIterator, typename Distance>
void advance(BidirectionalIterator& it, Distance n, bidirectional_iterator_tag) {
    if (n >= 0) {
        while (n--) ++it;
    } else {
        while (n++) --it;
    }
}

template <typename RandomAccessIterator, typename Distance>
void advance(RandomAccessIterator& it, Distance n, random_access_iterator_tag) {
    it += n;
}

template <typename Iterator, typename Distance>
void advance(Iterator& it, Distance n) {
    using category = typename iterator_traits<Iterator>::iterator_category;
    advance(it, n, category());
}

// =================================================
// reverse iterator (iterator adapter)
// =================================================

template <typename Iterator>
class reverse_iterator {
protected:
    Iterator current; // the underlying iterator
public:
    using iterator_type = Iterator;
    using iterator_category = typename iterator_traits<Iterator>::iterator_category;
    using value_type = typename iterator_traits<Iterator>::value_type;
    using difference_type = typename iterator_traits<Iterator>::difference_type;
    using pointer = typename iterator_traits<Iterator>::pointer;
    using reference = typename iterator_traits<Iterator>::reference;

    reverse_iterator() : current() {}
    explicit reverse_iterator(Iterator it) : current(it) {}
    reverse_iterator(const reverse_iterator& other) : current(other.current) {}

    Iterator base() const {
        return current;
    }

    reference operator*() const {
        Iterator temp = current;
        return *--temp;
    }

    pointer operator->() const {
        return &(operator*());
    }

    reverse_iterator& operator++() {
        --current;
        return *this;
    }

    reverse_iterator operator++(int) {
        reverse_iterator temp = *this;
        --current;
        return temp;
    }

    reverse_iterator& operator--() {
        ++current;
        return *this;
    }

    reverse_iterator operator--(int) {
        reverse_iterator temp = *this;
        ++current;
        return temp;
    }

    reverse_iterator operator+(difference_type n) const {
        return reverse_iterator(current - n);
    }
    reverse_iterator& operator+=(difference_type n) {
        current -= n;
        return *this;
    }
    reverse_iterator operator-(difference_type n) const {
        return reverse_iterator(current + n);
    }
    reverse_iterator& operator-=(difference_type n) {
        current += n;
        return *this;
    }

    reference operator[](difference_type n) const {
        return *(*this + n);
    }

    bool operator==(const reverse_iterator& other) const {
        return current == other.current;
    }
    bool operator!=(const reverse_iterator& other) const {
        return current != other.current;
    }
    bool operator<(const reverse_iterator& other) const {
        return current > other.current;
    }
};


} // namespace mystl

#endif // MY_ITERATOR_H

这里的 “using difference_type = std::ptrdiff_t;”， std::ptrdiff_t 是 C++ 标准库 里定义的一种带符号整数类型， 它的作用是：用来表示两个指针之间的距离（差值）。
那为什么 allocator 或 iterator 要定义它？
在 STL 中，difference_type 是所有容器、迭代器、分配器中必须提供的一个标准类型别名，用来表示：
两个迭代器之间的距离（或索引差值）

为什么不直接用 int 或 long 呢？
因为：
指针差值的大小依赖于平台（32位或64位系统）；
std::ptrdiff_t 是由标准库定义的「正确」类型，会自动匹配平台大小；
它是 STL 概念里固定要求的类型名（兼容性好）。

2️⃣ 内存层：Allocator

目标：实现简单版的 allocator<T>

  • allocate, deallocate
  • construct, destroy

MyAllocator的简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#ifndef MY_ALLOCATOR_H
#define MY_ALLOCATOR_H

// include necessary headers
#include <cstddef>

namespace mystl{

template <class T>
class MyAllocator {
public:
    // Define value_type as T
    using size_type = std::size_t;
    // Define difference_type as a signed integral type
    using difference_type = std::ptrdiff_t;

    using value_type = T;
    using pointer = value_type*;
    using const_pointer = const value_type*;
    using reference = T&;

    MyAllocator() = default;
    template <class U>
    MyAllocator(const MyAllocator<U>&) noexcept {}

    static pointer allocate(size_type n) {
        return operator new(n * sizeof(value_type));
    }

    // Deallocate
    static void deallocate(pointer p, size_type) noexcept{
        ::operator delete(p);
    }

    //construct
    tmeplate <class... Args>
    static void construct(pointer p, Args&&... args) {
        ::new (p) value_type(std::forward<Args>(args)...);
    }

    //deconstruct
    static void destroy(pointer p) noexcept {
        p->~T();
    }
};

// Allocators for different types are equal
template <class T, class U>
bool operator==(const MyAllocator<T>&, const MyAllocator<U>& ) noexcept {
    return true;
}

template <class T, class U>
bool operator!=(const MyAllocator<T>&, const MyAllocator<U>& ) noexcept {
    return false;
}

} // namespace mystl


#endif // MY_ALLOCATOR_H

那这行代码干了什么？ “::new ((void*)p) T(std::forward(args)…);”

一步步来看：
1️⃣ (void*)p
把指针 p 转换成 void*，告诉编译器这是一个内存地址。
2️⃣ ::new ((void*)p)
在地址 p 上“原地构造”一个对象，不分配新内存。
3️⃣ T(std::forward(args)…)
调用 T 的构造函数，把参数原封不动地转发进去。
最终效果是：
“在指针 p 所指的那块内存上，用参数 args… 构造一个类型为 T 的对象。”

可选TODO：实现一个内存池（如 SGI STL 的 “second level allocator”）

3️⃣ 容器层：核心数据结构

vector

list

deque

stack & queue

rbtree

map & set

hashtable

[‘unordered_map & unordered_set`](https://puxuan.cc/2025/10/31/cpp cpp-stl-unordered-map-set/)

heap, priority_queue , multiset, multimap

4️⃣ 算法层

实现通用算法模板：

  • copy, fill, find, swap, equal, lexicographical_compare(TODO)
  • 排序算法（sort, stable_sort）
  • 搜索算法（lower_bound, upper_bound, binary_search）

这里会用到 SFINAE、iterator traits 来区分不同迭代器类别（随机访问 vs 输入输出）。

我自己的实现在这里可以找到：my_stl_algorithm

5️⃣ 适配层与接口一致性

模仿 std:: 的接口规范，比如：

1
2
3
4
ccstl::vector<int> v = {1,2,3};
v.push_back(4);
auto it = v.begin();
std::sort(v.begin(), v.end());

所有容器都应支持：

  • begin(), end()
  • size(), empty()
  • operator[]（若适用）