C++笔记(SGI STL)

start

https://www.youtube.com/watch?v=18c3MTX0PK0&list=PLlrATfBNZ98dudnM48yfGUldqGD0S4FFb

找到了一位大佬的教学视频

面向对象编程是何意位？

面向对象编程，英文叫 OOP：Object-Oriented Programming

把程序里的东西看成一个个对象，每个对象有自己的数据和行为

好比是人的‘硬件’和‘软件’

c++里可以把这些封装成一个类，class

之前看php的时候也有这东西

类

class Person {
public:
    string name;
    int age;

    void sayHello() {
        cout << "你好，我叫 " << name << endl;
    }
};

Person作为一个类，描述了一个人应该有什么

对象

Person p1;
p1.name = "shark";
p1.age = 18;

p1.sayHello();

p1为具体的人

连起来就是这样

#include <iostream>
#include <string>
using namespace std;

class Person {
public:
    string name;
    int age;

    void sayHello() {
        cout << "你好，我叫 " << name << endl;
    }
};

int main() {
    Person p1;

    p1.name = "shark";
    p1.age = 18;

    p1.sayHello();

    return 0;
}

对的对的

有点熟悉但不那么熟悉的std

类和对像的关系

class 类 = 图纸 / 模板

object 对象 = 根据图纸造出来的具体东西

面向对象的三大特性

封装

把数据和操作数据的函数放在一起，并控制外部能不能直接访问

class Player {
private:
    int hp;

public:
    void setHp(int value) {
        if (value >= 0) {
            hp = value;
        }
    }

    int getHp() {
        return hp;
    }
};

这里：

1 2	`private: int hp;`

表示 hp 外部不能直接改

只能通过setHp(),getHp()访问

防止乱改数据

继承

一个类可以继承另一个类的属性和函数

比如：

class Animal {
public:
    void eat() {
        cout << "正在吃东西" << endl;
    }
};

class Dog : public Animal {
public:
    void bark() {
        cout << "汪汪" << endl;
    }
};

Dog 继承了 Animal。

所以：

1
2
3

Dog d;
d.eat();
d.bark();

输出：

1
2

正在吃东西
汪汪

意思是：

1
2
3

Dog 是 Animal 的一种
Dog 拥有 Animal 的能力
Dog 还可以有自己的能力

多态

同一个接口在不同对象中表现出不同的效果

class Animal {
public:
    virtual void speak() {
        cout << "动物叫" << endl;
    }
};

class Dog : public Animal {
public:
    void speak() override {
        cout << "汪汪" << endl;
    }
};

class Cat : public Animal {
public:
    void speak() override {
        cout << "喵喵" << endl;
    }
};

函数调用：

Animal* a1 = new Dog();
Animal* a2 = new Cat();

a1->speak();
a2->speak();

a1和a2会发出不同的叫声

小细节

note1

#include

iostrean是输出输入库

cont,cin,endl都是里面的

cout  // 输出到屏幕
cin   // 从键盘输入

#include <iostream>
using namespace std;

int main() {
    int age;

    cout << "请输入你的年龄：";
    cin >> age;

    cout << "你的年龄是：" << age << endl;

    return 0;
}

cout <<   // 输出
cin  >>   // 输入

string是字符串库

#include <iostream>
#include <string>
using namespace std;

int main() {
    string name = "shark";
    cout << name << endl;
    return 0;
}

就这样

基础

变量

#include <iostream>
using namespace std;

int main() {
    int age = 18;

    cout << age << endl;

    return 0;
}

不多说，c里面的老东西

数据类型（常见）

整数：`int`

1 2	`int age = 18; int score = 100;`

适合存整数：

小数：`double`

1 2	`double height = 1.75; double price = 9.99;`

适合存小数。

字符：`char`

1	`char grade = 'A';`

注意：char 用单引号。

1	`char c = 'x';`

不能这样：

1	`char c = "x"; // 错`

字符串：`string`

1	`string name = "shark";`

注意：string 用双引号。

1	`string s = "hello";`

依旧老东西

布尔值：`bool`

bool 只有两个值：

1 2	`true false`

比如：

1 2	`bool isAdmin = true; bool isDead = false;`

#include <iostream>
#include <string>
using namespace std;

int main() {
    string name = "shark";
    int age = 18;
    double height = 1.75;
    char grade = 'A';
    bool isStudent = true;

    cout << "名字：" << name << endl;
    cout << "年龄：" << age << endl;
    cout << "身高：" << height << endl;
    cout << "等级：" << grade << endl;
    cout << "是否学生：" << isStudent << endl;

    return 0;
}

算了，不说了，都是c学过的

构造函数和析构函数

构造函数：对象出生时自动执行

析构函数：对象死亡时自动执行

自动生成的析构函数只会自动销毁成员变量本身，不会帮你释放你手动 new 出来的内存

如果不写析构函数，c++会自动给类加一个默认析构函数

1
2
3

char* data;
int* p;
Node* child;

这些裸指针如果指向 new 出来的内存，通常你就要考虑自己写析构函数

#include <iostream>
using namespace std;

class Buffer {
public:
    char* data;

    Buffer() {
        data = new char[16];
        cout << "申请内存" << endl;
    }

    ~Buffer() {
        delete[] data;
        cout << "释放内存" << endl;
    }
};

int main() {
    Buffer buf;

    return 0;
}

这样

c++对象生命周期

对象从出生到死亡会经历一系列函数调用

分配内存

↓

构造对象

↓

使用对象

↓

析构对象

↓

释放内存

例子

#include <iostream>
using namespace std;

class Node {
public:
    Node() {
        cout << "构造 Node" << endl;
    }

    ~Node() {
        cout << "析构 Node" << endl;
    }
};

int main() {
    Node n;

    return 0;
}

main 中Node n;自动调用构造函数Node()

main结束时n 离开作用域，自动调用析构函数~Node()

栈对象的生命周期

Node n;

就是这种

进入作用域
↓
创建 n
↓
调用构造函数
↓
使用 n
↓
离开作用域
↓
调用析构函数
↓
n 消失

#include <iostream>
using namespace std;

class Node {
public:
    Node() {
        cout << "Node 构造" << endl;
    }

    ~Node() {
        cout << "Node 析构" << endl;
    }
};

void test() {
    cout << "进入 test" << endl;

    Node n;

    cout << "离开 test 前" << endl;
}

int main() {
    cout << "main 开始" << endl;

    test();

    cout << "main 结束" << endl;

    return 0;
}

跑一个试试看

确实是函数结束后才调用析构

堆对象的生命周期

堆对象得用new创建

Node* p = new Node();

不会自动析构，必须用delete

#include <iostream>
using namespace std;

class Node {
public:
    Node() {
        cout << "Node 构造" << endl;
    }

    ~Node() {
        cout << "Node 析构" << endl;
    }
};

int main() {
    Node* p = new Node();

    cout << "正在使用 p" << endl;

    delete p;

    return 0;
}

拷贝构造函数

#include <iostream>
using namespace std;

class Node {
public:
    int value;

    Node(int v) {
        value = v;
        cout << "普通构造" << endl;
    }

    Node(const Node& other) {
        value = other.value;
        cout << "拷贝构造" << endl;
    }

    ~Node() {
        cout << "析构" << endl;
    }
};

int main() {
    Node a(123);

    Node b = a;

    return 0;
}

Node b = a;并非赋值，而是创建b并用a初始化它

Node ( const Node& other) 就是拷贝构造函数

Node a(1);
Node b(2);

b = a;

若b已经存在就调用赋值函数

Node& operator=(constNode& other)

Node n;
栈上创建对象，自动构造，离开作用域自动析构

Node* p = new Node();
堆上创建对象，new 时构造，delete 时析构

new Node()
分配内存 + 调用构造函数

delete p
调用析构函数 + 释放内存

operator new(sizeof(Node))
只分配内存，不构造对象

p->~Node()
只析构对象，不释放内存

operator delete(p)
只释放内存

C++ 对象生命周期 = 内存分配 + 构造 + 使用 + 析构 + 内存释放

模板

模板的作用是：

先写一份通用代码，具体类型由编译器在使用时确定。

例如：

template<class T>
T add(T a, T b) {
    return a + b;
}

调用：

1	`add(1, 2);`

编译器根据参数推导：

T = int

然后生成近似这样的函数：

1
2
3

int add(int a, int b) {
    return a + b;
}

函数函数函数

函数重载

函数重载是：

函数名相同，但参数列表不同，编译器根据实参选择最合适的版本。

例如：

void print(int x) {
    cout << "int\n";
}

void print(double x) {
    cout << "double\n";
}

void print(const char* x) {
    cout << "string\n";
}

调用：

1
2
3

print(10);       // print(int)
print(3.14);     // print(double)
print("hello");  // print(const char*)

before stl

class and struct

c++里的 class 和 struct 基本一样，唯一不同的就是默认public或private

how to write a c++ class

c++里的class private类型只能通过public中的函数篡改

class 类名
{
private:
// 成员变量

public:
// 成员函数
};

class Log
{
private:
    int level;

public:
    void SetLevel(int newLevel)
    {
        level = newLevel;
    }

    void Write(const char* message)
    {
        std::cout << message << std::endl;
    }
};

这里：

1 2	`private: int level;`

外部不能直接访问

只能通过：

1	`log.SetLevel(1);`

来修改。

这就是封装

普通情况下，类外不能直接访问 <font style="color:#DF2A3F;">private</font>，只能通过 <font style="color:#DF2A3F;">public</font> 函数访问；类内部、friend、同类对象之间可以访问

static in c++

普通成员变量：

每个对象一份

static 成员变量：

整个类共享一份

普通成员函数：

有 this 指针，可以访问普通成员变量

static 成员函数：

没有 this 指针，只能直接访问 static 成员

static 成员不属于对象，属于类

SGI STL

要用到的源码从这里下

https://sgistl.github.io/download.html

我看的是v3.3的

终于把cherno的小视频看完了

六大组件

容器 Container

↓ 提供迭代器

迭代器 Iterator

↓ 传给算法（算法本身只负责做法，由迭代器与容器连接）

算法 Algorithm

空间配置器 Allocator ->为容器管理内存(空间配置器只分配内存，不执行构造函数)

仿函数 Functor->为算法提供操作规则，调整算法行为

适配器 Adapter->改造容器、迭代器或仿函数

SGI STL 中，空间配置器为容器提供内存支持，容器真正负责存放和组织数据；

算法本身不直接接触容器，而是通过迭代器访问和操作容器中的元素；

仿函数可以作为算法的操作规则，用来改变算法的行为；

适配器则是在已有容器、迭代器或仿函数的基础上，改变它们的接口或使用方式。

    		   allocator

       		       ↓

       	 	  container

           			 ↓

          		iterator

              		↓

algorithm ←→ 数据访问

↑

functor

↑

adapter

容器Container

container负责存储数据，组织数据，管理数据的生命周期

例如在vector中

vector v;

v.push_back(10);

v.push_back(20);

存储10，20

组织数据就是不同的容器用不同的数据结构，不存在一种数据结构能在所有操作上都最快

容器	底层结构	特点
`vector`	连续数组	随机访问快
`list`	双向链表	中间插入、删除快
`deque`	分段连续空间	头尾插入快
`set`	红黑树	元素自动排序、不重复
`map`	红黑树	保存键值对，按键排序
`hash_set`	哈希表	平均查找速度快
`hash_map`	哈希表	根据键快速查找值

容器会自动处理：

申请内存
构造对象
扩容
销毁对象
释放内存

即管理数据的生命周期

容器可以分为两类，序列式容器和关联式容器

序列式容器

元素主要按照插入顺序排列。

vector
list
deque
slist

关联式容器

元素按照键值组织，通常支持快速查找。

set
multiset
map
multimap

空间配置器Allocator

allocator主要用来申请跟释放内存

空间配置器主要管理内存空间，不一定负责对象构造

STL 里通常分成两步：

1 2	`1. allocate：申请原始内存 2. construct：在这块内存上构造对象`

销毁时也是两步：

1 2	`1. destroy：析构对象 2. deallocate：释放内存`

STL中会频繁申请，释放小内存如果用malloc和free的话就很低效

SGI STL中采用了两级配置器

一级配置器：处理大块内存

二级配置器：处理小块内存

一级配置器主要处理大于 128 字节的内存。

底层直接调用：

1
2
3

malloc()
free()
realloc()

二级配置器主要处理小于等于 128 字节的小块内存。

维护一个内存池和多个自由链表 free list。

迭代器Iterator

迭代器将容器跟算法连接，让算法不用考虑容器内数据如何存储

可以将迭代器视为指针的抽象

vector 底层是连续数组，list 底层是链表，存数据的方式完全不同，但对于同一种算法则可以通过迭代器操作

比如：

1 2	`find(first, last, value); sort(first, last);`

并不直接操作 vector 或 list，而是通过迭代器操作：

1 2	`find(v.begin(), v.end(), 3); find(l.begin(), l.end(), 3);`

这样算法就不需要知道容器的内部结构

迭代器的实现主要是在stl v3.3里的stl_iterator.h跟stl_iterator_base.h

stl_iterator_base.h：定义迭代器的类型系统·类型萃取以及算法分派机制。

stl_iterator.h：在基础机制之上实现各种具体的迭代器适配器。

五种迭代器标签，结构体里无成员变量，用类型表示迭代器能力

迭代器	能力
输入迭代器	读取、向前移动
输出迭代器	写入、向前移动
前向迭代器	可以多次向前遍历
双向迭代器	可以 `++` 和 `--`
随机访问迭代器	可以 `+n`、`-n`、下标访问

后面的distance() advance()会根据这些tag选择不同的函数

iterator模板，规定迭代器必须提供哪些信息

这个 iterator 只是提供五种类型信息：

iterator_category
value_type
difference_type
pointer
reference

调用函数模板时，编译器根据你传入的实参类型，自动推导模板参数 T 是什么。

例如：

template<class T>
void func(T x) {
}

int a = 10;
func(a);

编译器看到传入的是 int，于是推导：

T = int

最终相当于调用：

1	`func<int>(a);`

traits(特性萃取）

迭代器类型
   ↓
提供五种关联类型
   ↓
iterator_traits 统一提取
   ↓
取出 iterator_category
   ↓
生成标签对象
   ↓
函数重载选择对应算法

两个例子：

distance(first, last)：计算两个迭代器之间相隔多少个元素。
advance(iterator, n)：让迭代器向前或向后移动 n 个位置

给定一个类型，让编译器在编译期获取这个类型的相关信息，并根据这些信息选择不同代码实现

类型 T

↓

traits

↓

提取 T 的各种特征

自定义迭代器可以提供内部类型
原生指针不能提供内部类型

intarr[] = {1, 2, 3};

针不是类，内部没有：

1
2
3

value_type
iterator_category
difference_type

为了解决这个问题，STL 增加了一层包装：

iterator_traits

不再直接查询：

Iterator::value_type

而是统一查询：

iterator_traits::value_type

iterator_traits主模板，stl_iterator_base.h：108～115

类型	含义
`iterator_category`	迭代器能力类别
`value_type`	指向的元素类型
`difference_type`	两个迭代器之间距离的类型
`pointer`	指向元素的指针类型
`reference`	解引用后得到的引用类型

从迭代器类型内部提取出五种关联类型

普通指针偏特化：stl_interator_base.h::117~125

查询：

1	`iterator_traits<int*>`

会匹配：

1	`iterator_traits<_Tp*>`

c++函数模板自动推导

这里是const指针偏特化

type_traits

type_traits在type_traits.h里

它们表示两种编译期结果：

__true_type → 该特性成立
__false_type → 该特性不成立

type_traits.h::61~86的是_type_traits的主模板

对于任意未知类型 _Tp，默认采取保守判断：

默认构造是否简单             false
拷贝构造是否简单             false
赋值操作是否简单             false
析构是否简单                 false
是否是 POD 类型              false

对于基础类型(int,bool,char…..)采用全特化

(__STL_TEMPLATE_NULL就相当于templete<>)

这样在处理例如int数组时可以用更简单的复制方式，不用调用析构函数

__type_traits<_Tp*> 是指针类型的偏特化，可以匹配 int*、char*、Test* 等指针。

例如：

1	`__type_traits<Test*>`

会推导出：

1	`_Tp = Test`

它判断的是 Test* 指针本身，而不是 Test 类。指针只保存地址，复制时只需复制地址，也不需要特殊析构，所以属于简单类型。

但 Test 类本身可能仍需要拷贝构造和析构。

c++ SGI STL

#c++ #SGI STL

C++笔记(SGI STL)

https://ghostshark-pro.github.io/2026/07/17/C++笔记(SGI STL)/

Author

shark

Posted

2026年7月17日

License

ustc_编译原理 Previous

how2heap分析-_2.23 Next

C++笔记(SGI STL)

start

面向对象编程是何意位？

类

对象

类和对像的关系

面向对象的三大特性

封装

继承

多态

小细节

note1

基础

变量

数据类型（常见）

整数：int

小数：double

字符：char

字符串：string

布尔值：bool

构造函数和析构函数

c++对象生命周期

例子

栈对象的生命周期

堆对象的生命周期

拷贝构造函数

模板

函数重载

before stl

class and struct

how to write a c++ class

static in c++

SGI STL

六大组件

容器Container

空间配置器Allocator

迭代器Iterator

traits(特性萃取）

type_traits

整数：`int`

小数：`double`

字符：`char`

字符串：`string`

布尔值：`bool`