C++ 如何高效的使用 STL 容器？

1.引言

2.容器分类

3.直接将对象、数据写入容器存在哪些问题？

4.对象是如何复制的？

5.复制存在哪些问题？

6.如何避免复制？

7.其它高效应用

7.1.选择合适的容器

7.2.避免不必要的复制

7.3.使用适当的分配器

7.4.利用STL算法库

7.5.使用迭代器进行遍历

7.6.预留足够的空间

7.7.注意异常安全性

8.总结

1.引言

C++ Standard Template Library (STL) 提供了一系列高效、可复用的容器，这些容器对于数据结构的设计和实现至关重要。在现代软件开发中，数据结构的选择和使用直接影响着程序的性能和可扩展性。因此，理解如何在C++中高效地使用STL容器是至关重要的。使用 STL 时直接存放对本身，如果应当避免直接存对象，而是存放指向对象的指针，否则前者会导致对象复制成本高。

2.容器分类

STL提供了多种类型的容器，包括但不限于：

        序列容器：如vector、deque、list等，它们用于存储具有线性关系的数据元素。
        关联容器：如set、multiset、map、multimap等，它们根据特定的排序标准来存储元素。
        容器适配器：如stack、queue、priority_queue等，它们对底层容器进行封装，提供特定的功能接口。
        无序关联容器（C++11引入）：如unordered_set、unordered_multiset、unordered_map、unordered_multimap，它们不保证元素的排序，但提供了快速的元素查找。

3.直接将对象、数据写入容器存在哪些问题？

在STL中，当将一个对象添加到容器中时（例如，通过insert或push_back等方法），容器并不直接存储提供的对象，而是存储该对象的一个副本。这意味着，容器中的对象与原始提供的对象在内存中是分开的，它们是两个完全独立的实例。

同样，当从容器中获取一个对象时（例如，通过front或back等方法），获取的也是该对象的一个副本，而不是容器中的原始对象。这意味着，即使修改了获取到的对象，也不会影响到容器中的原始对象。

这种“复制进，复制出”的方式是STL的基本工作原理，这样做的好处是可以保护容器中的数据不被意外修改，提高了数据的安全性。但是，这也意味着在使用STL容器时，需要注意对象复制可能带来的性能开销，特别是对于大型对象或复制操作代价较高的对象。

假设我们有一个std::vector<int>，我们想要在其中存储一些整数。

std::vector<int> vec;
int a = 5;
vec.push_back(a);

在这个例子中，我们将整数a添加到了向量vec中。但是，实际上存储在vec中的并不是a本身，而是a的一个副本。这意味着，即使我们稍后修改了a的值，vec中的值也不会改变，因为它存储的是a的副本，而不是a本身。

a = 10;
std::cout << vec[0];  // 输出仍然是5，而不是10

同样，当我们从vec中获取一个元素时，我们获取的也是该元素的一个副本。

int b = vec[0];
b = 20;
std::cout << vec[0];  // 输出仍然是5，而不是20

在这个例子中，我们从vec中获取了第一个元素，并将其赋值给了b。然后我们修改了b的值，但这并不会影响vec中的元素，因为b是vec[0]的一个副本，而不是vec[0]本身。

4.对象是如何复制的？

在C++中，对象的复制通常通过复制构造函数和复制赋值运算符来完成。这两个函数是类的成员函数，用于创建类的新对象（复制构造函数）或将一个对象的值赋给另一个对象（复制赋值运算符）。

复制构造函数的典型声明如下：

class Widget {
public:Widget(const Widget&); // copy constructor...
};

这个函数接受一个同类型的对象作为参数，然后创建一个新的对象，其内容是参数对象的副本。

复制赋值运算符的典型声明如下：

class Widget {
public:Widget& operator=(const Widget&); // copy assignment operator...
};

这个函数接受一个同类型的对象作为参数，然后将调用对象的内容替换为参数对象的内容。

当在容器中插入或删除元素，或者使用某些算法（如排序、移除、旋转等）时，这些函数会被调用，以确保对象的正确复制。

例如，如果有一个std::vector<Widget>，并且想在其中添加一个新的Widget对象，那么这个对象会被复制到向量中。这个复制过程就是通过调用Widget的复制构造函数来完成的。

std::vector<Widget> widgets;
Widget w;
widgets.push_back(w); // w is copied into the vector

同样，如果有两个Widget对象，并且想将一个对象的值赋给另一个对象，那么这个赋值过程就是通过调用Widget的复制赋值运算符来完成的。

Widget w1, w2;
w1 = w2; // w2 is copied into w1

如果不自己声明这些函数，编译器会为自动生成。对于内置类型（如int、指针等），复制过程更简单，只需要复制底层的位。

5.复制存在哪些问题？

在C++中，对象的复制可能会导致性能问题，特别是当对象的复制成本很高时。例如，如果一个对象包含大量的数据或者复杂的结构，那么复制这个对象可能会消耗大量的时间和内存。如果在容器中频繁地插入、删除或移动这种对象，那么这些操作可能会成为性能瓶颈。

例如，假设有一个Widget类，它包含一个大型的std::vector成员：

class Widget {
public:Widget(const Widget& other) : data(other.data) {} // copy constructorWidget& operator=(const Widget& other) { data = other.data; return *this; } // copy assignment operatorprivate:std::vector<int> data;
};

如果在一个std::vector<Widget>中频繁地插入或删除Widget对象，那么每次操作都会涉及到复制Widget对象中的data向量，这可能会消耗大量的时间和内存。

此外，如果有一个对象，其中“复制”有一个非常规的含义，那么将这样的对象放入容器可能会导致问题。例如，如果的对象包含一个指向动态分配内存的指针，并且的复制构造函数和复制赋值运算符执行深复制，那么每次复制对象时都会分配新的内存，这可能会导致内存泄漏或其他问题。

在存在继承的情况下，复制可能会导致切片问题。切片是指当将一个派生类对象赋值给一个基类对象时，派生类特有的部分会被切掉。例如：

class Base {
public:Base(const Base&) {} // copy constructorBase& operator=(const Base&) { return *this; } // copy assignment operator
};class Derived : public Base {
public:Derived(const Derived& other) : Base(other), data(other.data) {} // copy constructorDerived& operator=(const Derived& other) { Base::operator=(other); data = other.data; return *this; } // copy assignment operatorprivate:int data;
};std::vector<Base> bases;
Derived d;
bases.push_back(d); // d is sliced when copied into bases

在这个例子中，当Derived对象d被复制到bases向量中时，data成员将被切掉，因为Base类并不知道它的存在。这可能会导致意外的行为，因为bases向量中的对象并不完全等同于原始的Derived对象。

会导致哪些意外行为？

数据丢失：派生类Derived特有的数据成员data在复制过程中被切掉，这意味着在bases向量中的对象并不包含data成员。如果你期望通过bases向量中的对象访问data成员，那么将无法得到正确的结果，因为data成员已经不存在了。
行为改变：如果派生类Derived重写了基类Base的某个虚函数，那么在bases向量中的对象将无法调用派生类Derived的版本，而只能调用基类Base的版本。这可能会改变程序的行为，因为你可能期望调用的是派生类的函数，而实际上调用的却是基类的函数。
类型信息丢失：在复制过程中，对象的动态类型信息也会丢失。也就是说，即使原始对象是派生类Derived的实例，但在bases向量中的对象的类型只能被识别为基类Base。这意味着你无法通过dynamic_cast或typeid等运算符获取到正确的类型信息。

6.如何避免复制？

如果的对象复制成本高，或者需要避免切片问题，那么使用指针的容器而不是对象的容器是一个解决方案。复制指针的成本低，且不会发生切片问题。但是，指针的容器也有其自身的问题，比如管理内存的复杂性。

例如，可以创建一个std::vector，它包含Widget对象的指针，而不是Widget对象本身：

std::vector<Widget*> widgets;
Widget* w = new Widget();
widgets.push_back(w); // w is copied into the vector

在这个例子中，当将Widget对象添加到向量中时，实际上复制的是指针，而不是Widget对象本身。这样，无论Widget对象有多大，复制的成本都是固定的。

然而，使用指针的容器也有其自身的问题。需要确保正确地管理内存，包括在适当的时候删除对象。如果忘记删除对象，就会导致内存泄漏。为了避免这种问题，可以使用智能指针，如std::shared_ptr或std::unique_ptr，它们会在不再需要对象时自动删除它。

std::vector<std::shared_ptr<Widget>> widgets;
std::shared_ptr<Widget> w = std::make_shared<Widget>();
widgets.push_back(w); // w is copied into the vector

在这个例子中，当shared_ptr被复制时，Widget对象不会被复制，而且当所有的shared_ptr都消失时，Widget对象会被自动删除。

尽管STL确实进行了很多复制操作，但它通常被设计为避免不必要的复制和对象创建。与C和C++的内置容器（如数组）相比，STL容器更加灵活和高效。它们只在需要时创建和复制对象，而且只有在明确要求时，它们才会使用默认构造函数。

7.其它高效应用

7.1.选择合适的容器

不同的容器有其特定的使用场景。例如，vector适用于随机访问和修改元素，而list则适用于在序列的任何位置进行快速的插入和删除操作。如果你需要保持元素的唯一性并且有序，那么set是一个不错的选择。而如果你需要存储键值对，并且希望基于键快速查找或修改值，那么map或unordered_map将是更好的选择。

每种容器都有其性能特点。例如，vector在尾部插入和删除元素时非常高效，但在中间插入或删除元素则可能导致大量的数据移动。相反，list在中间插入或删除元素时效率更高，但随机访问元素的成本则相对较高。了解这些性能特性可以帮助你根据应用需求选择最合适的容器。

7.2.避免不必要的复制

当处理大量数据时，不必要的复制可能会导致性能下降。为了避免这种情况，可以使用引用或指针来传递数据，或者使用移动语义（C++11引入）来避免复制成本。此外，当向容器中添加元素时，如果可能的话，应优先考虑使用emplace系列函数（如emplace_back），它们可以直接在容器中构造元素，而无需先构造再复制。

7.3.使用适当的分配器

STL容器允许你自定义内存分配器。在某些情况下，使用自定义的分配器可以显著提高性能。例如，你可以实现一个基于内存池的分配器来减少内存碎片并提高分配速度。

7.4.利用STL算法库

STL不仅提供了容器，还提供了一套丰富的算法库，包括排序、查找、复制、转换等操作。这些算法通常比手动实现的循环更高效，因为它们经过了优化并且可以利用容器的内部特性。例如，使用std::sort对vector进行排序通常比手动实现的排序算法要快得多。

7.5.使用迭代器进行遍历

STL容器通过迭代器提供了统一的遍历接口。迭代器可以看作是指向容器中元素的指针或引用。使用迭代器可以避免不必要的元素复制，并且可以与STL算法库无缝集成，从而提高代码的可读性和效率。

7.6.预留足够的空间

对于像vector这样的动态数组容器，如果事先知道将要存储的元素数量，可以使用reserve函数预留足够的空间。这样做可以避免在添加元素时频繁地重新分配内存和复制数据，从而提高性能。

7.7.注意异常安全性

当在容器中存储可能引发异常的元素时（如动态分配的对象），应确保代码的异常安全性。这通常意味着在可能引发异常的代码周围使用异常处理机制，并确保在异常发生时能够正确地清理资源。

8.总结

在使用C++标准模板库（STL）中的容器时，对象复制的常见情况和复制的实现方式是重要的考虑因素。对象的复制通常通过复制构造函数和复制赋值运算符来完成，这两个函数是类的成员函数，用于创建类的新对象或将一个对象的值赋给另一个对象。然而，对象的复制可能会导致性能问题，特别是当对象的复制成本很高时。此外，如果有一个对象，其中“复制”有一个非常规的含义，那么将这样的对象放入容器可能会导致问题。在存在继承的情况下，复制可能会导致切片问题。如果对象复制成本高，或者需要避免切片问题，那么使用指针的容器而不是对象的容器是一个解决方案。