当前位置：首页 > article >正文

STL(一)

article 2024/11/26 11:18:36

STL

六大组件

容器（containers）：各种数据结构，如 vector, list, deque, set, map 用来存放数据。从实现的角度来看，STL 容器是一种 class template
算法（algorithms）：各种常用的算法如 sort, search, copy, erase…从实现角度来看，STL 算法是一种 function template
1. std::find：查找某个元素
2. std::count：计算满足条件的元素个数
3. std::sort：对范围内的元素排序
4. std::reverse：反转元素顺序
5. std::accumulate：累加范围内元素
6. std::inner_product：计算内积
7. std::set_union：求并集
8. std::set_intersection：求交集
配置器（allocator）：负责空间配置与管理，从实现角度来看，配置器是一个实现了动态空间配置、空间管理、空间释放的 class template
仿函数（functors）：行为类似函数，可以作为算法的某种策略。从实现角度来看，仿函数是一种重载了 operator() 的 class 或class template
迭代器（iterators）：扮演容器与算法之间的胶合剂，是所谓的“泛型指针”。从实现角度来看，迭代器是一种将 operator *, operator ->, operator++, operator– 等指针相关操作予以重载的class template
适配器（adapters）：一种用来修饰容器或仿函数或迭代器接口的东西。例如 STL 提供的 queue 和 stack，虽然看似容器，其实只能算是一种容器适配器，因为它们的底部完全借助 deque，所有操作都由底层的 deque 供应

容器

是否需要在容器的任意位置插入新元素？ 如果需要，就选择序列容器否则选择关联容器
是否关心容器中元素是排序的？ 如果不关心则哈希容器是一个可行选择方案；否则你要避免哈希容器
当发生元素的插入和删除操作时候，避免移动容器中原来的元素是否重要？ 如果是就要避免选择序列容器
容器中数据布局是否需要和C保持兼容？ 如果是是只能选择 vector\
元素的查找速度是否是关键的考虑因素？ 如果是考虑哈希容器

对象切割：

对象切割现象：对象切割是指将一个派生类对象赋值或拷贝到基类对象时，派生类中特有的部分被切掉，只保留基类部分的数据和行为

在 C++ 中，如果一个容器存储的是 **基类对象**，无论你插入的是基类还是派生类对象，容器只能存储 **基类部分**`
这是因为基类和派生类的布局不同，基类无法为派生类的扩展部分预留空间

解决：

可以使用智能指针，而不是对象本身。这样，派生类的动态类型信息不会丢失：

vector<shared_ptr<Base>> container; // 存储智能指针

container.push_back(make_shared<Derived>()); // 插入派生类对象

for (const auto& obj : container) {
    obj->print(); // 调用动态类型的 print 函数
}

基类和子类的内存布局

基类 Base (包含虚函数):
+-------------------+
| vptr (虚函数表指针) | <- 指向Base的虚函数表
+-------------------+
| 成员变量1         | <- Base::member1
| 成员变量2         | <- Base::member2
| ...               |
| 成员变量N         | <- Base::memberN
+-------------------+

子类 Derived (继承自Base，并可能添加新的虚函数):
+-------------------+
| vptr (虚函数表指针) | <- 指向Derived的虚函数表
+-------------------+
| 基类部分          | <- 指向基类部分的指针
| +-----------------+ |
| | vptr (虚函数表指针) | | <- 实际上不会在子类中重复，但子类有自己的虚函数表指针
| +-----------------+ |
| | 成员变量1       | | <- Base::member1
| | 成员变量2       | | <- Base::member2
| | ...            | |
| | 成员变量N       | | <- Base::memberN
| +-----------------+ |
+-------------------+
| 新增成员变量1     | <- Derived::new_member1
| 新增成员变量2     | <- Derived::new_member2
| ...               |
| 新增成员变量M     | <- Derived::new_memberM
+-------------------+

虚函数表：

基类 Base:
+-------------------+
| vptr (指向Base的虚函数表) |
+-------------------+
| 成员变量1         |
| 成员变量2         |
| ...               |
| 成员变量N         |
+-------------------+

Base的虚函数表:
+-------------------+
| Base::virtualFunc1 |
| Base::virtualFunc2 |
| ...               |
| Base::virtualFuncM |
+-------------------+

子类 Derived:
+-------------------+
| vptr (指向Derived的虚函数表) |
+-------------------+
| 基类部分（Base的成员变量）  |
+-------------------+
| 新增成员变量1     |
| 新增成员变量2     |
| ...               |
| 新增成员变量N     |
+-------------------+

Derived的虚函数表:
+-------------------+
| Base::virtualFunc1 (或 Derived::virtualFunc1 如果被重写) |
| Base::virtualFunc2 (或 Derived::virtualFunc2 如果被重写) |
| ...               |
| Base::virtualFuncM (或 Derived::virtualFuncM 如果被重写) |
| Derived::newVirtualFunc1 |
| Derived::newVirtualFunc2 |
| ...               |
| Derived::newVirtualFuncN |
+-------------------+

当通过基类指针调用虚函数时，实际执行的是以下步骤

编译器生成的代码会查找基类指针所指向对象的vptr
通过vptr，代码访问虚函数表
从虚函数表中，代码取出相应虚函数的地址
调用该地址所指向的函数

由于子类对象的vptr指向的是子类的虚函数表，即使是通过基类指针进行的调用，也会找到子类虚函数表中相应的条目。如果子类重写了基类的虚函数，那么虚函数表中的条目将指向子类版本的函数

调用empty 而不是检查 size() 是否为 0

//对任意 c 容器，下面的代码本质上等价的
if (c.size() == 0) {}
if (c.empty()) {}

empty 对所有的标准容器都是常数时间操作，而对一些 list 实现，size 函数耗费线性时间。（比如 list 容器的 splice 函数）

区间成员函数优先于与之对应的单元素成员函数

什么是区间成员函数，什么是单元素成员函数

单元素操作：只处理一个元素，例如：

1. `insert`：插入单个元素
1. `erase`：删除单个元素

区间操作：可以一次性处理多个元素，例如：

1. `insert`：插入一段区间的元素
1. `erase`：删除一段区间的元素

std::vector<int> v;
v.insert(v.begin(), 10); // 在开头插入一个元素 10	单元素插入

std::vector<int> toInsert = {20, 30, 40};
v.insert(v.begin(), toInsert.begin(), toInsert.end()); // 在开头插入一段区间  区间插入

每次调用单元素操作时，都会产生函数调用开销（包括栈帧的创建和销毁）。区间操作只需调用一次函数，可以显著减少开销

避免多次内存操作，减少迭代和函数调用开销
区间操作代码更紧凑，更易于理解和维护
尤其是在需要处理大量数据时，区间操作更高效

如果容器中包含了通过 new 操作创建的指针，切记在容器对象析构前将指针 delete 掉

当 STL 容器中存储的是通过 new 动态分配的指针时，容器析构只会释放指针本身的内存（即指针所占的存储空间），而不会释放指针指向的对象内存。因此，需要手动释放指针指向的内存，否则会发生内存泄漏

q：为什么容器不会自动释放指针指向的内存？

eg：以 std::vector 为例，容器的析构函数会：

遍历存储的元素
调用每个元素的析构函数
释放存储容器元素所需的内存

如果容器存储的是指针（如 std::vector<int*>），析构时只会销毁指针本身（即存储指针的那段小内存），而不会自动销毁指针指向的对象（因为 C++ 不知道指针指向的对象是否需要释放）

vector<int*> v;

// 动态分配内存并存储指针
for (int i = 0; i < 5; ++i) {
    v.push_back(new int(i));
}

// 容器析构时，存储的指针被销毁，但指针指向的内存不会释放
return 0;

动态分配的 new int(i) 对象在程序运行期间分配在堆上；
当 v 退出作用域时，v 的析构函数只会销毁 v 内部的指针，但指针所指向的 int 对象并不会自动释放

解决：

用 std::unique_ptr 或 std::shared_ptr借助智能指针的自动析构功能，避免手动管理内存

通过 RAII（Resource Acquisition Is Initialization）技术，封装指针和其管理逻辑，利用对象的生命周期来管理动态分配的资源

class IntWrapper {
    int* ptr;
public:
    IntWrapper(int value) : ptr(new int(value)) {}
    ~IntWrapper() { delete ptr; }

    int get() const { return *ptr; }
};

int main() {
    vector<IntWrapper> v;

    for (int i = 0; i < 5; ++i) {
        v.emplace_back(i); // 使用 RAII 类管理动态对象
    }

    // 容器析构时，RAII 类会自动释放动态对象的内存
    return 0;

切勿对 STL 容器的线程安全性有不切实际的依赖

STL 容器在设计时并没有内置线程安全性，任何对其多线程操作都需要自行加以保护，否则可能会导致数据竞争（data race）或未定义行为

STL 容器在单线程环境中是安全的，但在多线程环境中，它们的线程安全性遵循以下规则：

只读操作是线程安全的：如果多个线程只对同一个容器执行只读操作（如 std::vector::at 或 std::set::find），那么这些操作是线程安全的，彼此之间不会产生冲突
如果一个线程对容器执行写操作（如插入、删除等），而另一个线程执行读操作或写操作，容器可能会变成不安全，可能导致未定义行为

**原因：**STL 容器内部没有锁或同步机制

性能考虑：锁的引入会导致性能下降，尤其是在单线程环境中，锁的开销可能远高于容器操作本身
灵活性要求：不同应用对线程安全的需求可能不同。STL 容器的无锁设计允许开发者根据具体场景自行选择合适的同步方式

void writer() {
    for (int i = 0; i < 1000; ++i) {
        vec.push_back(i); // 写操作
    }
}

void reader() {
    for (int i = 0; i < 1000; ++i) {
        if (!vec.empty()) {
            std::cout << vec[0] << "\n"; // 读操作
        }
    }
}

int main() {
    std::thread t1(writer);
    std::thread t2(reader);

    t1.join();
    t2.join();

数据竞争：

写线程（writer）可能会修改 std::vector 的内部数据结构（如分配内存或移动元素）
读线程（reader）在访问容器时，可能遇到部分写操作未完成的中间状态，导致未定义行为

解决方法：

使用互斥锁

void writer() {
    for (int i = 0; i < 1000; ++i) {
        std::lock_guard<std::mutex> lock(mtx); // 加锁保护
        vec.push_back(i);
    }
}

void reader() {
    for (int i = 0; i < 1000; ++i) {
        std::lock_guard<std::mutex> lock(mtx); // 加锁保护
        if (!vec.empty()) {
            std::cout << vec[0] << "\n";
        }
    }
}

使用 reserve 来避免不必要的重新分配

指的是在使用像 std::vector 这样的动态数组容器时，通过预先指定容器的容量，减少或者避免在后续元素插入过程中因容量不足而触发的内存重新分配操作。这样可以提升程序的性能，特别是在对容器频繁添加大量元素时

内存重新分配：

std::vector 是一个动态数组。当向其添加元素时，如果当前容量不足以容纳新元素，std::vector 会触发以下过程：

分配一块更大的内存空间（通常是当前容量的两倍，具体增长策略可能因实现而异）
将现有元素从旧内存移动到新内存
释放旧内存

时间开销：每次重新分配时，所有已有元素必须逐一移动到新内存

空间开销：旧内存的释放与新内存的分配都需要额外的系统开销

效率低下：如果频繁触发重新分配，性能会显著降低

reserve作用：

std::vector提供了一个成员函数reserve`，用于预分配一定的容量（capacity），以减少或避免重新分配的发生

void reserve(size_type new_cap);

只有动态分配内存的容器（如 std::vector 和 std::deque）支持 reserve

使用”swap技巧”除去多余的容量

通过临时对象和 std::swap 操作来优化动态容器（如 std::vector 或 std::string）的内存占用的方法，利用 C++ 容器的特性，强制释放容器多余的内存，以减少不必要的内存浪费

std::vector<int> vec;
    vec.reserve(100); // 预分配 100 个元素空间
    for (int i = 0; i < 100; ++i) {
        vec.push_back(i);
    }
    std::cout << "Before clear: size = " << vec.size() << ", capacity = " << vec.capacity() << std::endl;

    vec.clear(); // 清空所有元素
    std::cout << "After clear: size = " << vec.size() << ", capacity = " << vec.capacity() << std::endl;

/*
	Before clear: size = 100, capacity = 100
	After clear: size = 0, capacity = 100
*/

匿名对象 std::vector<int>(vec); 的生命周期只持续到该语句结束。这意味着一旦这个表达式结束，这个匿名对象就会被销毁

通过使用 std::vector<int>(vec).swap(vec);

临时对象与 vec 交换数据，原来的 vec 对象被赋予临时对象的内存，大小和容量被重新调整，临时对象在离开作用域时销毁，其占用的多余内存被释放。

为包含指针的关联容器指定比较类型

解决在关联容器（如 std::set 或 std::map）中存储指针时，默认比较方式可能带来的问题

关联容器的比较规则：

C++ 的关联容器（如 std::set 和 std::map）是基于平衡二叉搜索树（如红黑树）实现的
为了维持元素的有序性，它们依赖于比较函数（通常是 operator<）
比较函数默认为 std::less<T>，等价于 operator<

std::set<int> s = {3, 1, 4};
for (int val : s) {
    std::cout << val << " "; // 输出：1 3 4
}

std::set<int*> s = {pa, pb, pc};
for (auto ptr : s) {
    std::cout << *ptr << " "; // 输出结果未必是按值排序
}
因为 std::set<int*> 默认比较 pa、pb、pc 的地址值，而不是它们指向的内容
    

int a = 10, b = 10;
int* pa = &a, *pb = &b;

std::set<int*> s = {pa, pb}; // 默认认为它们是不同的，因为地址不同
std::cout << s.size(); // 输出：2，但预期可能是 1

解决：

通过自定义比较器，可以明确指定如何比较指针，使容器的行为更符合语义需求

struct Compare {
    bool operator()(const int* lhs, const int* rhs) const {
        return *lhs < *rhs; // 比较指针指向的内容
    }
};

struct Compare {
    bool operator()(const int* lhs, const int* rhs) const {
        return *lhs < *rhs; // 比较指针指向的内容
    }
};


/*使用智能指针*/
struct Compare {
    bool operator()(const std::shared_ptr<int>& lhs, const std::shared_ptr<int>& rhs) const {
        return *lhs < *rhs;
    }
};

auto a = std::make_shared<int>(30);
auto b = std::make_shared<int>(10);
auto c = std::make_shared<int>(20);

std::set<std::shared_ptr<int>, Compare> s = {a, b, c};
for (const auto& ptr : s) {
    std::cout << *ptr << " "; // 输出：10 20 30
}

总是让比较函数在等值情况下返回 false

C++ 的标准库（如 std::sort、std::set 和 std::map）对比较函数的要求是它必须满足严格弱序，即比较函数 comp(a, b) 应满足以下规则

反对称性：comp(a, b) == true 意味着 comp(b, a) == false
传递性：如果 comp(a, b) == true 且 comp(b, c) == true，则 comp(a, c) == true
不反身性：对于任何 a，comp(a, a) 必须返回 false

如果比较函数在等值情况下返回 true，将导致容器或算法的行为不符合预期，甚至会出现逻辑错误或崩溃

struct BadCompare {
    bool operator()(int a, int b) const {
        return a <= b; // 错误：等值情况下返回 true
    }
};

std::set<int, BadCompare> s;
s.insert(10);
s.insert(10); // 插入等值的元素

std::cout << s.size() << std::endl; // 可能输出 2，而不是预期的 1
return 0;

比较函数必须确保在等值情况下返回 false，即严格使用 < 或 > 的逻辑来比较

struct GoodCompare {
    bool operator()(int a, int b) const {
        return a < b; // 等值情况下返回 false
    }
};

永远使用 a < b 或 a > b 这样的比较逻辑，确保等值时返回 false
避免使用 <= 或 >=，因为这些可能在等值时返回 true

22 切勿直接修改 set 或 multiset 中的键

有序容器特性：std::set 和 std::multiset 是基于 红黑树 实现的有序关联容器。它们的元素会根据指定的比较规则（如 < 或自定义比较函数）保持有序
键值不可变：在 std::set 和 std::multiset 中，元素的键既是其值（不像 std::map 有键和值之分）。为了维护有序性，这些容器要求插入的元素不能被修改，否则会破坏有序性并导致未定义行为
直接修改元素可能会改变其排序位置，但红黑树无法感知到这一点
导致容器的逻辑结构与物理存储不匹配，从而破坏容器的行为

eg：

auto it = mySet.find(3);
if (it != mySet.end()) {
    // 错误操作：直接修改 set 中的元素
    // *it = 10; // 编译错误，因为 *it 是 const
    int *ptr = const_cast<int*>(&(*it)); // 强制去掉 const 性质（危险！）
    *ptr = 10;  // 修改键值，未定义行为
}

// 打印 set
for (int val : mySet) {
    std::cout << val << " ";
}

// 在标准 C++ 中，*it 是 const，因此无法直接修改
// 修改后的 std::set 可能会打印出非有序的数据，或在后续操作中触发未定义行为

正确做法：

auto it = mySet.find(3);
if (it != mySet.end()) {
    int newValue = 10;  // 新值
    mySet.erase(it);    // 删除旧值
    mySet.insert(newValue);  // 插入新值
}

23 考虑用排序的vector替代关联容器

标准库提供了关联容器（如 std::set、std::map）和顺序容器（如 std::vector）。在某些场景下，使用一个排序的 std::vector 来替代关联容器可以提高性能，同时满足需求

关联容器（如 std::set 或 std::map）基于 红黑树，会自动维护有序性，这种自动维护有序性的机制带来了额外的内存占用和指针跳转的开销，这些指针跳转会导致缓存不命中，降低性能
std::vector 使用连续的内存存储，访问和遍历时缓存友好，
对于小规模数据，排序后的 std::vector 通过二分查找实现查找操作，性能非常接近关联容器的 O(logn)，甚至在实际运行中可能更快

std::set<int> mySet = {10, 20, 5, 30};
mySet.insert(15);  // 插入新元素，自动保持有序


std::vector<int> myVector = {10, 20, 5, 30};
// 排序（如果元素静态，可以省略）
std::sort(myVector.begin(), myVector.end());
// 插入新元素并保持有序
int newElement = 15;
auto it = std::lower_bound(myVector.begin(), myVector.end(), newElement);
myVector.insert(it, newElement);  // 使用二分查找找到插入点

29 对于逐个字符的输入请考虑使用 istreambuf_iterator

当我们需要逐个字符读取输入流的数据时，istreambuf_iterator 是一个高效且简单的选择。它比使用常规方法（如 std::istream::get 或 std::getline）更直接，尤其是在需要精细控制字符输入的场景

istreambuf_iterator 是一种标准库迭代器，专门用来直接从流缓冲区读取数据
它通过流的 缓冲区 (streambuf) 工作，而不是通过标准的提取操作符 (>>) 或者其他高级接口
它可以逐个字符地从流中提取数据，包括空白字符（如空格、换行符）

32 如果确实需要删除元素，则需要在 remove 这一类算法之后调用 erase

std::remove 和类似的算法（如 std::remove_if）是非真正删除元素的算法。它们并不会实际从容器中删除元素，而是通过调整元素顺序，将不需要的元素“移到末尾”，并返回一个指向新逻辑末尾的迭代器。要真正从容器中移除这些元素，还需要配合容器的 erase 方法使用

std::remove 的工作原理：

将不需要的元素覆盖（或跳过）；
保留需要的元素，并将其重新排列到前面；
返回一个新的迭代器，指向未被覆盖区域的起始位置（即新的逻辑末尾）

eg：

std::vector<int> vec = {1, 2, 3, 4, 5, 3, 6};

// 将所有值为 3 的元素移到末尾
auto it = std::remove(vec.begin(), vec.end(), 3);
// 打印容器内容
for (int x : vec) {
    std::cout << x << " ";
}
std::cout << std::endl;

// 打印新逻辑末尾
std::cout << "New end: " << *it << std::endl;

1 2 4 5 6 3 6 
New end: 3

std::remove 重新排列了容器的内容，将所有不为 3 的元素放在前面

物理大小未变，3 仍然存在于容器末尾

查看全文

http://www.kler.cn/a/409862.html