# sybstl

**Repository Path**: syb4750/sybstl

## Basic Information

- **Project Name**: sybstl
- **Description**: C++STL实现
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-08-18
- **Last Updated**: 2025-08-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# SYBSTL
STL是标准模板库，HP版本是STL实现版本的始祖，SGI版本继承HP版本，被GCC采用。
![stl](/picture/stl.png)

## 配置器 allocator
负责空间配置与管理。
主要分为两级分配器：一级分配器（malloc_alloc）和二级分配器（default_alloc）。  
一级分配器直接调用`malloc/free`，用于分配大于128字节的内存。   
二级分配器采用内存池+自由链表的方式实现，用于分配小块内存。  

### 二级分配器的核心设计
(1) 内存池（Memory Pool）
+ 预分配大块内存：通过malloc申请一大块内存作为备用池。
+ 按需切割：将大块内存切割成固定大小的小块，供自由链表使用。

(2) 自由链表（Free List）
+ 16 个链表：分别管理 8、16、24、...、128 字节的小块内存。
+ 每个链表节点：
```cpp
union obj {
    union obj* free_list_link; // 指向下一个空闲块
    char client_data[1];       // 用户数据区
};
```
+ 利用联合体（union）节省空间：空闲时存储指针，分配后存储用户数据。

## 迭代器 iterator
一种抽象的设计概念，它提供了一种方法，使之能够依序寻访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。  
迭代器包括只读迭代器、只写迭代器、读写迭代器、双向迭代器、随机迭代器  
+ traits编程技法
所有迭代器都有五种相应型别：value, difference, reference, point, iterator_category  
type_traits 的核心是通过模板特化针对不同类型生成不同的结果。

## 容器 containers
### 序列式容器
#### vector
+ 成员变量：三个普通指针

重载了`[]`操作符，使能够像数组一样使用。  
容量不够时，先申请两倍大小的内存，然后将现有数据拷贝到新内存中，释放原空间。  
存储空间是连续的，不能删除某一元素，只能覆盖，插入操作可能导致原有的迭代器失效。

#### list
+ 成员变量：一个尾节点指针
+ 迭代器成员：一个指向节点的指针

list是一个环状双向链表，成员变量指向尾端的一个空白节点，满足“前闭后开”的原则。  
list迭代器是双向迭代器，不能使用算法中的`sort`函数

#### deque
+ 成员变量：头节点迭代器，尾节点迭代器，一个二级指针，目前map的大小。
+ 迭代器成员：三个普通指针，一个二级指针

由一段一段的定量连续线性空间构成。与vector的最大差异，一在于允许于常数时间内对两端元素进行插入和删除操作。二是deque没有所谓容量的概念，因为它是动态的以分段连续空间组合而成。 

一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务，便是在这些分段的定量连续空间上，维护其整体连续的假象。  

虽然deque提供随机迭代器，但是访问的时间复杂度高于vector，对deque进行的排序操作，为了最高效率，可将deque先完整复制到一个vector身上，排序后再复制回deque。

默认缓冲区大小为512字节。

#### slist
+ 一个头节点
+ 迭代器成员：一个指向节点的指针

单向链表，insert或erase困难。

### 关联式容器
#### RB-tree
RB-tree是一种二叉搜索树，且满足以下规则：
+ 每个节点不是红色就是黑色
+ 根节点为黑色
+ 如果节点为红，其子节点必须为黑
+ 任一节点至NULL的任何路径，所含之黑节点数必须相同

#### set
set的key和value相同，不能通过迭代器改变set的元素值。会根据key自动排序。
进行`insert`或`erase`操作后，操作之前的其他所有迭代器依然有效。

#### multiset
允许键值重复的set。

#### map
map会根据key自动排序，可以修改元素的value。
进行`insert`或`erase`操作后，操作之前的其他所有迭代器依然有效。

#### multimap
允许键值重复的map。

#### hashtable
SGI采用开链法完成hash table  
hashtable的迭代器没有后退操作，也没有所谓的逆向迭代器。 
以质数来设计表格大小，提前将28个质数计算好，并提供一个函数计算最接近并大于n的质数。 
STL提供了所有内置类型的hash函数，但并不能支持所有类型，针对某些自定义类型，应当自主撰写函数对象模板全特化版本  

#### hash_set
封装了hashtable的操作，不允许键值重复，默认hashtable的大小为100（采用质数193）。  
用户自定义类型需要自行提供hash函数。

#### hash_multiset
允许键值重复的hash_set。

#### hash_map
封装了hashtable的操作，拥有实值和键值，默认hashtable的大小为100（采用质数193）。  
用户自定义类型需要自行提供hash函数。

#### hash_multimap
允许键值重复的hash_map。

## 算法 algorithm
所有的泛型算法的前两个参数都是一对迭代器，习惯采用前闭后开区间表示法[first, last)。 
许多STL算法不只支持一个版本。这一类算法的某个版本采用缺省运算行为，另一个版本提供额外参数，接受外界传入一个仿函数，以便采用其他策略。  
质变算法通常提供两个版本，一个是就地更改操作对象；另一个是拷贝版，常以_copy作为函数结尾，将操作对象的内容复制一份副本，然后在副本上进行修改并返回该副本。  
质变算法运算过程中会更改区间内迭代器所指的元素内容。如拷贝（copy）、互换（swap）、替换（replace）、填写（fill）、删除（remove）、排列组合（permutation）、分割（partition）、随机重排（random shuffling）、排序（sort）等。  
非质变运算过程中不会更改区间内迭代器所指的元素内容。如查找（find）、匹配（search）、计数（count）、寻访（for_each）、比较（equal,mismatch）、寻找极值（max,min）等。  

### 查找算法(13个)：判断容器中是否包含某个值
+ adjacent_find：在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的ForwardIterator。否则返回last。重载版本使用输入的二元操作符代替相等的判断。
+ binary_search：在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。
+ count：利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。
+ count_if：利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。
+ equal_range：功能类似equal，返回一对iterator，第一个表示lower_bound，第二个表示upper_bound。
+ find：利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个InputIterator。
+ find_end：在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个ForwardIterator，否则返回输入的"另外一对"的第一个ForwardIterator。重载版本使用用户输入的操作符代替等于操作。
+ find_first_of：在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。
+ find_if：使用输入的函数代替等于操作符执行find。
+ lower_bound：返回一个ForwardIterator，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。
+ upper_bound：返回一个ForwardIterator，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。
+ search：给出两个范围，返回一个ForwardIterator，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向last1。重载版本使用自定义的比较操作。
+ search_n：在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。

### 排序和通用算法(14个)：提供元素排序策略
+ inplace_merge：合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序。
+ merge：合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。
+ nth_element：将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作。
+ partial_sort：对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。
+ partial_sort_copy：与partial_sort类似，不过将经过排序的序列复制到另一个容器。
+ partition：对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前。
+ random_shuffle：对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。
+ reverse：将指定范围内元素重新反序排序。
+ reverse_copy：与reverse类似，不过将结果写入另一个容器。
+ rotate：将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素。
+ rotate_copy：与rotate类似，不过将结果写入另一个容器。
+ sort：以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。
+ stable_sort：与sort类似，不过保留相等元素之间的顺序关系。
+ stable_partition：与partition类似，不过不保证保留容器中的相对顺序。

### 删除和替换算法(15个)
+ copy：复制序列
+ copy_backward：与copy相同，不过元素是以相反顺序被拷贝。
+ iter_swap：交换两个ForwardIterator的值。
+ remove：删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove_if函数。
+ remove_copy：将所有不匹配元素复制到一个制定容器，返回OutputIterator指向被拷贝的末元素的下一个位置。
+ remove_if：删除指定范围内输入操作结果为true的所有元素。
+ remove_copy_if：将所有不匹配元素拷贝到一个指定容器。
+ replace：将指定范围内所有等于vold的元素都用vnew代替。
+ replace_copy：与replace类似，不过将结果写入另一个容器。
+ replace_if：将指定范围内所有操作结果为true的元素用新值代替。
+ replace_copy_if：与replace_if，不过将结果写入另一个容器。
+ swap：交换存储在两个对象中的值。
+ swap_range：将指定范围内的元素与另一个序列元素值进行交换。
+ unique：清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作。
+ unique_copy：与unique类似，不过把结果输出到另一个容器。

### 排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合
+ next_permutation：取出当前范围内的排列，并重新排序为下一个排列。重载版本使用自定义的比较操作。
+ prev_permutation：取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。 

### 算术算法(4个)
+ accumulate：iterator对标识的序列段元素之和，加到一个由val指定初始值上。重载版本不再做加法，而是传进来的二元操作符被应用到元素上。
+ partial_sum：创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。
+ inner_product： 对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。
+ adjacent_difference：创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。

### 生成和异变算法(6个)
+ fill：将输入值赋给标志范围内的所有元素。
+ fill_n：将输入值赋给first到first+n范围内的所有元素。
+ for_each：用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。该函数不得修改序列中的元素。
+ generate：连续调用输入的函数来填充指定的范围。
+ generate_n：与generate函数类似，填充从指定iterator开始n个元素。
+ transform：将输入的操作作用与指定范围内的每个元素，并产生一个新的序列。重载版本将操作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定容器。

### 关系算法(8个)
+ equal：如果两个序列在标志范围内元素都相等，返回true。重载版本使用输入的操作符代替默认的等于操作符。
+ includes：判断第一个指定范围内的所有元素是否都被第二个范围包含，使用底层元素的<操作符，成功返回true。重载版本使用用户输入的函数。
+ lexicographical_compare：比较两个序列。重载版本使用用户自定义比较操作。
+ max：返回两个元素中较大一个。重载版本使用自定义比较操作。
+ max_element：返回一个ForwardIterator，指出序列中最大的元素。重载版本使用自定义比较操作。
+ min：返回两个元素中较小一个。重载版本使用自定义比较操作。
+ min_element：返回一个ForwardIterator，指出序列中最小的元素。重载版本使用自定义比较操作。
+ mismatch：并行比较两个序列，指出第一个不匹配的位置，返回一对iterator，标志第一个不匹配元素位置。如果都匹配，返回每个容器的last。重载版本使用自定义的比较操作。 

### 集合算法(4个)
+ set_union：构造一个有序序列，包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。
+ set_intersection：构造一个有序序列，其中元素在两个序列中都存在。重载版本使用自定义的比较操作。
+ set_difference：构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。
+ set_symmetric_difference：构造一个有序序列，该序列取两个序列的对称差集(并集-交集)。 

### 堆算法(4个)
+ make_heap：把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。
+ pop_heap：并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop_back进行真正的删除。重载版本使用自定义的比较操作。
+ push_heap：假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作。
+ sort_heap：对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作。


## 仿函数 functor
重载了函数调用符号的类或结构，常作为算法函数的参数实现自定义功能。  
STL仿函数的以操作数的个数划分，可分为一元和二元仿函数；以功能划分，可分为算术运算、关系运算、逻辑运算三大类。


## 适配器 adapter
### 容器适配器
#### stack
+ 成员变量：其他容器

只要能在尾部添加和删除数据的结构就能封装成stack，STL默认用deque为stack的底部结构。  
stack没有迭代器，不提供访问功能。

#### queue
+ 成员变量：其他容器

只要能在尾部添加数据和头部删除数据的结构就能封装成queue，STL默认用deque为queue的底部结构。  
queue没有迭代器，不提供访问功能。

### priority_queue
+ 成员变量：底层容器，元素大小比较标准

priority_queue允许用户以任何次序将元素推入容器内，但先取出优先级最高的元素，底层用heap实现。heap是完成二叉树，可以用数组来存储。  
priority_queue没有迭代器，不提供访问功能。

### 迭代器适配器
insert iterators, reverse iterators, iostream iterators.

### 函数适配器
系结(bind), 否定(negate), 组合(compose)