012 《folly::Vector 权威指南: 深度探索与实践》
🌟🌟🌟本文案由Gemini 2.0 Flash Thinking Experimental 01-21创作,用来辅助学习知识。🌟🌟🌟
书籍大纲
1. chapter 1: 向量 (Vector) 容器概览
1.1 什么是向量 (Vector)?:动态数组的概念 (What is Vector? Concept of Dynamic Array)
在计算机科学的浩瀚世界中,容器 (Container) 是一个 фундаментальный (fundamental) 概念,它提供了一种组织和存储数据集合的有效方式。在众多容器类型中,向量 (Vector) 以其灵活性和高效性脱颖而出,成为程序员工具箱中不可或缺的利器。
简单来说,向量是一种动态数组 (Dynamic Array)。要理解“动态数组”的含义,我们首先需要回顾一下传统的静态数组 (Static Array)。静态数组在声明时需要预先指定固定的大小,一旦分配,数组的大小就无法更改。这种固定大小的特性在某些场景下非常方便,但在需要处理大小可变的数据集合时则显得捉襟见肘。
向量作为动态数组,则克服了静态数组的局限性。动态 的关键在于,向量的大小可以在程序运行过程中动态地增长或缩小,以适应数据量的变化。这就像一个可以伸缩的容器,根据需要自动调整自身的大小,从而更加灵活高效地管理数据。
我们可以将向量想象成一个可以自动扩容的箱子。
① 初始状态:当你创建一个向量时,它可能拥有一个初始的容量 (Capacity),就好比箱子的初始大小。
② 元素添加:当你向向量中添加元素时,就像往箱子里放东西。只要箱子还能容纳,就可以继续放入。
③ 自动扩容:当箱子即将装满,无法容纳新的元素时,向量会自动“扩容”,分配一块更大的内存空间,并将原有元素复制到新的空间中,然后再将新元素添加进去。这个过程对于用户来说是透明的,无需手动干预。
④ 高效访问:由于向量在内存中是连续存储的,就像数组一样,因此可以通过索引 (Index)
动态数组的概念之所以重要,是因为它在灵活性和性能之间找到了一个良好的平衡点。它既具备数组快速访问的优点,又克服了数组大小固定的缺点,使得程序能够更加高效地处理动态变化的数据。
⚝ 总结向量的关键特性:
▮▮▮▮⚝ 动态大小 (Dynamic Size): 向量的大小可以在运行时动态调整。
▮▮▮▮⚝ 连续存储 (Contiguous Storage): 向量中的元素在内存中是连续存储的,类似于数组。
▮▮▮▮⚝ 随机访问 (Random Access): 支持通过索引
▮▮▮▮⚝ 自动内存管理 (Automatic Memory Management): 向量负责内存的自动分配和释放,无需手动管理。
理解了向量作为动态数组的概念,就为我们深入学习 folly::Vector
打下了坚实的基础。在接下来的章节中,我们将逐步探索 folly::Vector
的各种功能和应用,揭示其在高性能编程中的强大威力。
1.2 向量 (Vector) 的优势与应用场景 (Advantages and Application Scenarios of Vector)
向量 (Vector) 作为一种常用的动态数组容器,其广泛应用并非偶然,而是源于其自身所具备的诸多优势。理解这些优势以及向量适用的应用场景,能够帮助我们更好地选择和使用向量,从而编写出更加高效、可靠的程序。
向量的主要优势:
① 动态扩容,灵活高效: 这是向量最核心的优势。无需预先指定固定大小,可以根据实际需求动态地添加或删除元素,有效管理可变大小的数据集合。 这种动态性极大地提高了内存利用率,避免了静态数组可能造成的空间浪费或溢出问题。
② 高效的随机访问: 由于向量内部元素是连续存储的,因此可以通过索引在
③ 尾部操作高效: 在向量的尾部添加 ( push_back
, emplace_back
) 和删除 ( pop_back
) 元素通常具有较高的效率,平均时间复杂度为
④ 易于使用,API 丰富: 向量提供了丰富的 API,例如元素的添加、删除、访问、查找、排序等,使得开发者可以方便地对数据进行各种操作。 现代 C++ 库 (如 std::vector
和 folly::Vector
) 更是提供了大量便捷的功能,进一步简化了开发流程。
⑤ 与算法的良好兼容性: 向量与标准库算法 (如 std::algorithm
) 具有良好的兼容性,可以方便地结合各种算法对向量中的数据进行处理,例如排序、查找、转换等。 这极大地提高了开发效率和代码的可复用性。
向量的典型应用场景:
① 存储和处理动态数据集合: 这是向量最常见的应用场景。例如,在网络编程中接收和处理客户端发送的数据包,在图形处理中存储顶点坐标,在科学计算中存储实验数据等。 这些场景中的数据量往往是动态变化的,使用向量可以灵活高效地管理这些数据。
② 作为其他数据结构的底层实现: 向量可以作为其他更复杂数据结构的底层实现,例如栈 (Stack)、队列 (Queue) 等。 利用向量的动态数组特性,可以方便地实现这些数据结构的功能。
③ 需要频繁随机访问元素的场景: 当程序需要频繁地通过索引访问数据元素时,向量是理想的选择。 例如,在游戏开发中,需要快速访问游戏场景中的物体信息;在数据库系统中,需要快速检索数据记录等。
④ 缓存 (Cache) 的实现: 向量可以用于实现简单的缓存机制。 将最近访问的数据存储在向量中,可以利用向量的快速访问能力提高数据访问速度。
⑤ 图形和图像处理: 在图形和图像处理领域,向量常用于存储像素数据、顶点数据、颜色信息等。 例如,可以使用向量来表示图像的像素矩阵,或者存储三维模型的顶点坐标。
⑥ 日志记录: 向量可以用于存储日志信息。 随着程序运行,日志信息不断增加,向量可以动态地扩展容量以容纳新的日志条目。
⑦ 算法实现: 在算法实现中,向量常用于存储中间结果或作为算法的辅助数据结构。 例如,在排序算法中,可以使用向量来存储待排序的元素;在图算法中,可以使用向量来存储邻接表。
总而言之,向量以其动态性、高效性和易用性,在各种应用场景中都发挥着重要作用。 掌握向量的优势和适用场景,能够帮助我们更好地利用这一强大的工具,提升程序的设计和开发效率。
1.3 folly::Vector 相较于 std::vector 的特点 (Features of folly::Vector Compared to std::vector)
在 C++ 标准库中,std::vector
已经是一个功能强大且广泛使用的动态数组容器。 然而,Facebook 开源的 folly
库提供的 folly::Vector
在某些方面对其进行了增强和优化,尤其是在性能和特定场景下的适用性方面。 理解 folly::Vector
相较于 std::vector
的特点,有助于我们根据实际需求选择更合适的容器。
folly::Vector
的主要特点和优势:
① 针对性能优化的内存分配策略: folly::Vector
在内存分配策略上进行了一些优化,旨在提高性能,尤其是在频繁插入和删除元素的场景下。 虽然具体的分配策略可能因 folly
版本而异,但其目标通常是减少内存分配和释放的开销,以及减少内存碎片。
② 移动语义 (Move Semantics) 的增强: folly::Vector
更加强调移动语义的应用,在某些操作中可能更有效地利用移动语义来避免不必要的拷贝,从而提升性能。 移动语义是 C++11 引入的重要特性,它允许资源的高效转移,尤其是在处理大型对象时。
③ 异常安全 (Exception Safety) 的考量: folly::Vector
在设计上更加注重异常安全性。 在某些操作中,folly::Vector
可能会提供更强的异常安全保证,例如强异常安全 (Strong Exception Safety) 或基本异常安全 (Basic Exception Safety)。 异常安全是指在程序发生异常时,容器能够保持其状态的完整性,避免资源泄漏或数据损坏。
④ 与 folly
库的集成: folly::Vector
作为 folly
库的一部分,与 folly
库的其他组件 (例如 folly::StringPiece
, folly::Optional
等) 具有更好的集成性。 如果你的项目已经使用了 folly
库,那么使用 folly::Vector
可以更好地融入整个 folly
生态系统。
⑤ 可能包含额外的功能或扩展: folly::Vector
可能会在 std::vector
的基础上提供一些额外的功能或扩展,以满足特定场景的需求。 这些扩展可能包括一些特殊的 API 或针对特定用例的优化。 需要查阅 folly
的官方文档以获取最准确的信息。
folly::Vector
与 std::vector
的适用场景对比:
⚝ std::vector
:
▮▮▮▮⚝ 通用场景: std::vector
是 C++ 标准库的一部分,具有良好的通用性和跨平台性,适用于绝大多数需要动态数组的场景。
▮▮▮▮⚝ 对性能要求不是极致的场景: 对于性能要求不是非常苛刻的应用,std::vector
通常能够满足需求,并且其稳定性和可靠性经过了广泛的验证。
▮▮▮▮⚝ 需要与其他标准库组件良好兼容的场景: std::vector
与 C++ 标准库的其他组件 (例如算法、迭代器、IO 流等) 具有天然的兼容性。
⚝ folly::Vector
:
▮▮▮▮⚝ 高性能要求的场景: 如果你的应用对性能有较高要求,尤其是在频繁进行插入、删除或移动操作的场景下,可以考虑 folly::Vector
,它可能在某些情况下提供更好的性能。
▮▮▮▮⚝ 已经使用 folly
库的项目: 如果你的项目已经使用了 folly
库,那么使用 folly::Vector
可以更好地融入 folly
生态系统,并可能获得更好的兼容性和协同效应。
▮▮▮▮⚝ 需要利用 folly::Vector
特有功能的场景: 如果 folly::Vector
提供了 std::vector
所不具备的特定功能或优化,并且这些功能或优化对你的应用至关重要,那么可以选择 folly::Vector
。
▮▮▮▮⚝ 对异常安全有更高要求的场景: 在某些对异常安全有严格要求的场景下,可以评估 folly::Vector
是否提供了更强的异常安全保证。
总结:
std::vector
是一个成熟、稳定、通用的动态数组容器,适用于绝大多数场景。 folly::Vector
则是在 std::vector
的基础上进行了一些性能优化和功能增强,尤其在高性能和特定场景下可能更具优势。 选择使用哪个容器,需要根据具体的应用场景、性能需求、项目依赖以及对 folly
库的熟悉程度等因素进行综合考虑。 在很多情况下,std::vector
已经足够优秀,而 folly::Vector
则为追求极致性能或需要 folly
特有功能的开发者提供了额外的选择。
1.4 开发环境搭建与 folly 库的引入 (Setting up Development Environment and Introducing folly Library)
要开始使用 folly::Vector
,首先需要搭建合适的开发环境并引入 folly
库。 本节将指导读者完成环境准备、folly
库的获取与编译,以及如何在项目中使用 folly::Vector
。
1.4.1 环境准备:编译器、构建工具 (Environment Preparation: Compiler, Build Tools)
开发 C++ 项目,特别是使用 folly
库的项目,需要准备以下基本开发环境:
① C++ 编译器 (C++ Compiler):
⚝ folly
库通常需要较新版本的 C++ 编译器来支持其使用的 C++ 特性。 推荐使用支持 C++14 或更高标准的编译器,例如:
▮▮▮▮⚝ GCC (GNU Compiler Collection): 建议使用 GCC 5.0 或更高版本。 在 Linux 系统中,通常可以使用包管理器 (如 apt
, yum
, dnf
等) 安装。 例如,在 Ubuntu 上可以使用 sudo apt-get install g++
安装。
▮▮▮▮⚝ Clang (LLVM Compiler Infrastructure): Clang 是另一个流行的 C++ 编译器,也具有良好的 C++ 标准支持。 建议使用 Clang 3.8 或更高版本。 在 macOS 和 Linux 系统中,可以使用包管理器安装。 例如,在 macOS 上可以使用 brew install llvm
安装。
▮▮▮▮⚝ Visual C++ (MSVC): 如果你在 Windows 平台上开发,可以使用 Visual Studio 提供的 MSVC 编译器。 建议使用 Visual Studio 2015 或更高版本。
⚝ 检查编译器版本: 安装完成后,可以通过命令行检查编译器版本,例如:
▮▮▮▮⚝ g++ --version
▮▮▮▮⚝ clang++ --version
▮▮▮▮⚝ cl
(在 Visual Studio 开发人员命令提示符中)
② 构建工具 (Build Tools):
⚝ CMake (Cross-Platform Make): folly
库使用 CMake 作为其构建系统。 CMake 是一个跨平台的构建工具,可以生成各种构建系统 (例如 Makefile, Ninja, Visual Studio 项目等) 的构建文件。 强烈推荐使用 CMake 来构建 folly
库和你的项目。 可以从 CMake 官网 (https://cmake.org/) 下载并安装。 或者使用包管理器安装,例如在 Ubuntu 上使用 sudo apt-get install cmake
。
⚝ Make 或 Ninja (可选): CMake 可以生成 Makefile (用于 make
构建工具) 或 Ninja 构建文件 (用于 ninja
构建工具)。 make
是传统的构建工具,而 ninja
则以其快速的构建速度而著称。 通常情况下,CMake 会自动处理这些构建工具的调用,你只需要安装 CMake 即可。 如果需要更快的构建速度,可以考虑安装 ninja
(例如在 Ubuntu 上使用 sudo apt-get install ninja-build
),并让 CMake 生成 Ninja 构建文件。
③ 其他依赖库 (Dependencies):
⚝ folly
库依赖于一些其他的开源库,例如 Boost, OpenSSL, zlib, libevent 等。 在编译 folly
库之前,需要确保这些依赖库已经安装。 folly
的官方文档通常会提供详细的依赖库列表和安装指南。 在 Linux 系统中,可以使用包管理器安装这些依赖库。 例如,在 Ubuntu 上,可以使用 sudo apt-get install libboost-dev libssl-dev zlib1g-dev libevent-dev libdouble-conversion-dev libgflags-dev libglog-dev liblz4-dev libsodium-dev
安装一些常见的依赖库。 具体的依赖库列表和安装命令请参考 folly
官方文档。
总结环境准备步骤:
- 安装 C++ 编译器 (GCC, Clang, MSVC)。
- 安装 CMake 构建工具。
- 安装
folly
的依赖库 (Boost, OpenSSL, zlib, libevent 等)。 具体依赖库列表请参考folly
官方文档。 - 验证编译器和 CMake 是否安装成功 (通过命令行检查版本)。
完成以上环境准备步骤后,就可以开始获取和编译 folly
库了。
1.4.2 folly 库的获取与编译 (Obtaining and Compiling folly Library)
获取和编译 folly
库通常涉及以下步骤:
① 获取 folly
源代码:
⚝ folly
库的源代码托管在 GitHub 上: https://github.com/facebook/folly
⚝ 可以使用 git
命令克隆 folly
仓库到本地:
1 | git clone https://github.com/facebook/folly.git |
2 | cd folly |
⚝ 可以选择特定的 folly
版本 (分支或标签) 进行克隆。 通常建议使用最新的稳定版本。 例如,要克隆 folly
的 v2024.01.22.00
版本,可以使用:
1 | git clone -b v2024.01.22.00 https://github.com/facebook/folly.git |
2 | cd folly |
② 创建构建目录:
⚝ 建议在 folly
源代码目录之外创建一个单独的构建目录 (build directory),用于存放编译生成的文件。 这可以保持源代码目录的整洁。 例如,在 folly
源代码目录下创建 build
目录:
1 | mkdir build |
2 | cd build |
③ 使用 CMake 配置构建:
⚝ 在构建目录中,使用 CMake 命令配置构建。 CMake 需要指定 folly
源代码的路径。 通常使用 cmake <folly_source_path>
命令,其中 <folly_source_path>
是 folly
源代码目录的路径。 由于我们已经在 folly/build
目录中,并且假设 folly
源代码目录在 folly
目录本身,因此可以使用 cmake ..
命令:
1 | cmake .. |
⚝ CMake 会检测系统环境、编译器、依赖库等,并生成构建系统所需的构建文件 (例如 Makefile 或 Ninja 文件)。
⚝ CMake 构建选项: CMake 提供了许多选项来配置构建过程。 常用的选项包括:
▮▮▮▮⚝ -DCMAKE_BUILD_TYPE=<build_type>
: 设置构建类型,例如 Debug
, Release
, RelWithDebInfo
等。 Release
类型用于生成优化后的发布版本,Debug
类型用于生成包含调试信息的调试版本。 例如,使用 cmake -DCMAKE_BUILD_TYPE=Release ..
生成 Release 版本。
▮▮▮▮⚝ -DCMAKE_INSTALL_PREFIX=<install_path>
: 设置安装路径。 编译完成后,可以使用 make install
命令将 folly
库安装到指定的路径。 例如,使用 cmake -DCMAKE_INSTALL_PREFIX=/usr/local ..
将安装路径设置为 /usr/local
。
▮▮▮▮⚝ -GNinja
: 指定使用 Ninja 构建工具。 例如,使用 cmake -GNinja ..
生成 Ninja 构建文件。
④ 编译 folly
库:
⚝ 配置完成后,使用构建命令编译 folly
库。 如果 CMake 生成的是 Makefile,则使用 make
命令;如果生成的是 Ninja 文件,则使用 ninja
命令。 通常情况下,直接使用 make
命令即可:
1 | make -j$(nproc) # 使用多核并行编译,加快编译速度 |
-j$(nproc)
选项告诉 make
命令使用多核并行编译,其中 $(nproc)
表示当前系统的 CPU 核心数。 可以根据实际情况调整并行编译的线程数。 例如,使用 make -j8
表示使用 8 个线程并行编译。
⚝ 编译过程可能需要一些时间,具体时间取决于你的硬件配置和 folly
库的大小。
⑤ 安装 folly
库 (可选):
⚝ 编译完成后,可以选择将 folly
库安装到系统目录或自定义目录。 如果之前在 CMake 配置时使用了 -DCMAKE_INSTALL_PREFIX
选项指定了安装路径,则可以使用 make install
命令进行安装:
1 | sudo make install # 可能需要管理员权限 |
⚝ make install
命令会将 folly
的头文件、库文件等复制到指定的安装路径。 安装完成后,就可以在你的项目中使用 folly
库了。
⚝ 如果不执行 make install
,也可以直接在构建目录中使用编译生成的 folly
库,但这可能需要更复杂的配置。 通常建议执行 make install
将 folly
库安装到系统目录或自定义目录,以便在项目中使用。
总结 folly
库的获取与编译步骤:
- 克隆
folly
源代码 (使用git clone
)。 - 创建构建目录 (例如
mkdir build; cd build
)。 - 使用 CMake 配置构建 (例如
cmake ..
或cmake -DCMAKE_BUILD_TYPE=Release ..
)。 - 编译
folly
库 (例如make -j$(nproc)
)。 - 安装
folly
库 (可选) (例如sudo make install
)。
完成以上步骤后,你就成功地获取并编译了 folly
库。 接下来,我们将介绍如何在项目中使用 folly::Vector
。
1.4.3 在项目中使用 folly::Vector (Using folly::Vector in Projects)
在项目中使用 folly::Vector
,需要确保项目能够找到 folly
库的头文件和库文件。 这通常涉及到以下几个方面:
① 包含 folly
头文件:
⚝ 在你的 C++ 源文件中,使用 #include <folly/Vector.h>
包含 folly::Vector
的头文件。 例如:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3}; |
5 | for (int x : vec) { |
6 | std::cout << x << " "; |
7 | } |
8 | std::cout << std::endl; |
9 | return 0; |
10 | } |
⚝ 头文件搜索路径: 编译器需要能够找到 folly
的头文件。 如果 folly
库安装到了系统目录 (例如 /usr/local/include
),编译器通常能够自动找到。 如果 folly
库安装到了自定义目录,或者没有安装,你需要显式地指定头文件搜索路径。 这可以通过编译器的 -I
选项来完成。 例如,如果 folly
头文件位于 /path/to/folly/include
目录,则可以在编译命令中添加 -I/path/to/folly/include
。
② 链接 folly
库:
⚝ 在编译和链接项目时,需要链接 folly
库。 folly
库通常会被编译成一个或多个静态库或动态库文件 (例如 libfolly.a
或 libfolly.so
)。
⚝ 库文件搜索路径: 链接器需要能够找到 folly
的库文件。 如果 folly
库安装到了系统目录 (例如 /usr/local/lib
),链接器通常能够自动找到。 如果 folly
库安装到了自定义目录,或者没有安装,你需要显式地指定库文件搜索路径。 这可以通过链接器的 -L
选项来完成。 例如,如果 folly
库文件位于 /path/to/folly/lib
目录,则可以在链接命令中添加 -L/path/to/folly/lib
。
⚝ 链接库文件: 使用链接器的 -l
选项指定要链接的库文件。 folly
库通常会被链接为 folly
库。 例如,在链接命令中添加 -lfolly
。 注意: 实际需要链接的库文件可能不止 folly
一个,还需要根据 folly
的依赖关系链接其他库 (例如 Boost 库、OpenSSL 库等)。 具体的链接库列表请参考 folly
的文档或 CMake 生成的构建配置。
③ 使用 CMake 管理项目 (推荐):
⚝ 强烈推荐使用 CMake 来管理你的 C++ 项目,特别是当项目依赖于 folly
库时。 CMake 可以方便地管理项目的构建过程、依赖关系、头文件搜索路径、库文件搜索路径、链接库等。
⚝ CMakeLists.txt
示例: 在你的项目根目录下创建一个 CMakeLists.txt
文件,内容示例如下:
1 | cmake_minimum_required(VERSION 3.10) |
2 | project(MyProject) |
3 | set(CMAKE_CXX_STANDARD 14) # 或者更高版本,例如 17, 20 |
4 | # 查找 folly 库 |
5 | find_package(Folly REQUIRED) |
6 | # 添加可执行文件 |
7 | add_executable(my_executable main.cpp) |
8 | # 链接 folly 库 |
9 | target_link_libraries(my_executable PRIVATE Folly::folly) |
▮▮▮▮⚝ cmake_minimum_required(VERSION 3.10)
: 指定 CMake 的最低版本要求。
▮▮▮▮⚝ project(MyProject)
: 设置项目名称。
▮▮▮▮⚝ set(CMAKE_CXX_STANDARD 14)
: 设置 C++ 标准版本。 folly
通常需要 C++14 或更高版本。
▮▮▮▮⚝ find_package(Folly REQUIRED)
: 使用 CMake 的 find_package
命令查找 Folly
库。 CMake 会根据预定义的搜索路径或用户指定的路径查找 Folly
库的配置信息 (通常是 FollyConfig.cmake
文件)。 REQUIRED
关键字表示如果找不到 Folly
库,CMake 配置将失败。 前提是 folly
库在编译安装时生成了 CMake 配置文件,并且 CMake 能够找到该配置文件。 这通常是 folly
官方推荐的安装方式。
▮▮▮▮⚝ add_executable(my_executable main.cpp)
: 添加可执行文件目标,目标名称为 my_executable
,源文件为 main.cpp
。
▮▮▮▮⚝ target_link_libraries(my_executable PRIVATE Folly::folly)
: 链接 Folly
库。 Folly::folly
是 Folly
库在 CMake 中定义的 target name。 PRIVATE
关键字表示 folly
库是 my_executable
的私有依赖,不会传递给其他依赖于 my_executable
的目标。
⚝ 构建项目: 在项目根目录下创建 build
目录,并使用 CMake 配置和构建项目:
1 | mkdir build |
2 | cd build |
3 | cmake .. # 假设 CMakeLists.txt 在项目根目录 |
4 | make -j$(nproc) |
构建成功后,可执行文件 my_executable
会在 build
目录中生成。
总结在项目中使用 folly::Vector
的步骤:
- 在源文件中包含
folly/Vector.h
头文件。 - 使用 CMake 管理项目 (推荐),并在
CMakeLists.txt
中使用find_package(Folly REQUIRED)
查找folly
库,并使用target_link_libraries
链接Folly::folly
。 - 如果未使用 CMake,则需要在编译和链接命令中手动指定
folly
的头文件搜索路径 (-I
选项)、库文件搜索路径 (-L
选项) 和链接库文件 (-l
选项)。 并确保链接所有folly
及其依赖库。
通过以上步骤,你就可以在你的 C++ 项目中成功地使用 folly::Vector
容器了。 在接下来的章节中,我们将深入学习 folly::Vector
的各种功能和用法。
END_OF_CHAPTER
2. chapter 2: folly::Vector 基础操作:快速上手
2.1 向量 (Vector) 的创建与初始化 (Creation and Initialization of Vector)
folly::Vector
作为 folly
库中提供的动态数组容器,其创建和初始化方式多样且灵活,能够满足不同场景下的需求。本节将详细介绍 folly::Vector
的各种创建与初始化方法,帮助读者快速上手。
① 默认构造函数 (Default Constructor)
默认构造函数创建一个空的 folly::Vector
,不包含任何元素。这是最基本的创建方式,适用于先创建向量,再逐步添加元素的场景。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; // 创建一个空的 folly::Vector<int> |
5 | std::cout << "Initial size: " << vec.size() << std::endl; // 输出初始大小:0 |
6 | return 0; |
7 | } |
② 填充构造函数 (Fill Constructor)
填充构造函数允许在创建 folly::Vector
的同时,指定向量的大小和初始值。这在需要创建具有固定大小并用相同值初始化的向量时非常有用。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec(5, 10); // 创建一个包含 5 个元素,每个元素初始化为 10 的 folly::Vector<int> |
5 | std::cout << "Size: " << vec.size() << std::endl; // 输出大小:5 |
6 | for (int val : vec) { |
7 | std::cout << val << " "; // 输出向量元素:10 10 10 10 10 |
8 | } |
9 | std::cout << std::endl; |
10 | return 0; |
11 | } |
③ 范围构造函数 (Range Constructor)
范围构造函数允许使用迭代器指定一个范围,用该范围内的元素初始化 folly::Vector
。这在需要从现有容器或数组创建 folly::Vector
时非常方便。
1 | |
2 | |
3 | |
4 | int main() { |
5 | std::vector<int> stdVec = {1, 2, 3, 4, 5}; |
6 | folly::Vector<int> follyVec(stdVec.begin(), stdVec.end()); // 使用 std::vector 的范围初始化 folly::Vector |
7 | std::cout << "Size: " << follyVec.size() << std::endl; // 输出大小:5 |
8 | for (int val : follyVec) { |
9 | std::cout << val << " "; // 输出向量元素:1 2 3 4 5 |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
④ 列表初始化 (List Initialization)
C++11 引入的列表初始化方式,可以简洁地创建并初始化 folly::Vector
。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3, 4, 5}; // 使用列表初始化创建 folly::Vector |
5 | std::cout << "Size: " << vec.size() << std::endl; // 输出大小:5 |
6 | for (int val : vec) { |
7 | std::cout << val << " "; // 输出向量元素:1 2 3 4 5 |
8 | } |
9 | std::cout << std::endl; |
10 | return 0; |
11 | } |
⑤ 拷贝构造函数 (Copy Constructor) 和 移动构造函数 (Move Constructor)
folly::Vector
支持拷贝构造和移动构造,允许通过已有的 folly::Vector
对象创建新的 folly::Vector
。移动构造在源对象是右值时被调用,可以避免深拷贝,提高性能。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {1, 2, 3}; |
5 | folly::Vector<int> vec2 = vec1; // 拷贝构造 |
6 | folly::Vector<int> vec3 = std::move(vec1); // 移动构造,vec1 变为 empty |
7 | std::cout << "vec2 size: " << vec2.size() << std::endl; // 输出 vec2 大小:3 |
8 | std::cout << "vec3 size: " << vec3.size() << std::endl; // 输出 vec3 大小:3 |
9 | std::cout << "vec1 size after move: " << vec1.size() << std::endl; // 输出 vec1 大小:0 (移动后可能为空,具体实现依赖于 folly 版本) |
10 | return 0; |
11 | } |
⑥ 使用 reserve()
预分配空间
虽然不是直接的初始化方式,但 reserve()
方法可以在创建 folly::Vector
后,预先分配一定的内存空间。这在预知向量大致大小时,可以减少后续元素添加时的内存重新分配次数,提高性能。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | vec.reserve(100); // 预分配 100 个 int 的空间 |
6 | std::cout << "Initial capacity: " << vec.capacity() << std::endl; // 输出初始容量:>= 100 |
7 | std::cout << "Initial size: " << vec.size() << std::endl; // 输出初始大小:0 |
8 | for (int i = 0; i < 100; ++i) { |
9 | vec.push_back(i); // 添加 100 个元素,通常不会触发多次 reallocate |
10 | } |
11 | std::cout << "Final size: " << vec.size() << std::endl; // 输出最终大小:100 |
12 | std::cout << "Final capacity: " << vec.capacity() << std::endl; // 输出最终容量:>= 100 |
13 | return 0; |
14 | } |
总结
folly::Vector
提供了多种灵活的创建和初始化方式,开发者可以根据实际需求选择最合适的方法。理解这些初始化方式是高效使用 folly::Vector
的基础。在性能敏感的场景中,合理使用 reserve()
预分配空间可以进一步提升程序效率。
2.2 元素的添加与移除:push_back, emplace_back, pop_back, insert, erase (Adding and Removing Elements: push_back, emplace_back, pop_back, insert, erase)
folly::Vector
作为动态数组,其核心功能之一就是能够方便地添加和移除元素。本节将详细介绍 folly::Vector
提供的元素添加和移除操作,包括 push_back
, emplace_back
, pop_back
, insert
, 和 erase
等方法,并通过代码示例演示其用法和区别。
① push_back(value)
:在向量尾部添加元素
push_back()
是最常用的在向量尾部添加元素的方法。它接受一个元素值作为参数,并在向量的末尾创建一个该值的副本。如果向量的容量不足,push_back()
会自动重新分配内存。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | vec.push_back(10); |
6 | vec.push_back(20); |
7 | vec.push_back(30); |
8 | std::cout << "Vector elements after push_back: "; |
9 | for (int val : vec) { |
10 | std::cout << val << " "; // 输出:10 20 30 |
11 | } |
12 | std::cout << std::endl; |
13 | return 0; |
14 | } |
② emplace_back(args...)
:在向量尾部直接构造元素
emplace_back()
与 push_back()
类似,也是在向量尾部添加元素。但 emplace_back()
的优势在于它直接在向量的末尾构造元素,而不是拷贝或移动已存在的元素。这对于存储复杂对象或移动成本较高的对象时,可以提高性能。emplace_back()
接受构造元素所需的参数,并将这些参数传递给元素的构造函数。
1 | |
2 | |
3 | class MyClass { |
4 | public: |
5 | MyClass(int val) : value(val) { |
6 | std::cout << "MyClass constructor called for value: " << value << std::endl; |
7 | } |
8 | int value; |
9 | }; |
10 | int main() { |
11 | folly::Vector<MyClass> vec; |
12 | vec.emplace_back(10); // 直接在 vector 内部构造 MyClass 对象,避免拷贝或移动 |
13 | vec.emplace_back(20); |
14 | std::cout << "Vector elements values: "; |
15 | for (const auto& obj : vec) { |
16 | std::cout << obj.value << " "; // 输出:10 20 |
17 | } |
18 | std::cout << std::endl; |
19 | return 0; |
20 | } |
③ pop_back()
:移除向量尾部元素
pop_back()
方法移除向量的最后一个元素。它不返回被移除元素的值,只是简单地减少向量的大小。调用 pop_back()
前,需要确保向量非空,否则会导致未定义行为。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | vec.pop_back(); // 移除最后一个元素 30 |
6 | std::cout << "Vector elements after pop_back: "; |
7 | for (int val : vec) { |
8 | std::cout << val << " "; // 输出:10 20 |
9 | } |
10 | std::cout << std::endl; |
11 | std::cout << "Vector size after pop_back: " << vec.size() << std::endl; // 输出大小:2 |
12 | return 0; |
13 | } |
④ insert(position, value)
和 insert(position, count, value)
和 insert(position, first, last)
:在指定位置插入元素
insert()
方法允许在向量的任意指定位置插入一个或多个元素。它有多种重载形式:
⚝ insert(position, value)
: 在 position
指向的位置之前插入一个元素 value
。
⚝ insert(position, count, value)
: 在 position
指向的位置之前插入 count
个值为 value
的元素。
⚝ insert(position, first, last)
: 在 position
指向的位置之前插入范围 [first, last)
内的元素。
insert()
操作通常比 push_back()
开销更大,因为插入位置之后的所有元素都需要向后移动。
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {10, 20, 30}; |
6 | // 在第二个位置(索引为 1)插入元素 15 |
7 | vec.insert(vec.begin() + 1, 15); |
8 | std::cout << "Vector after insert(position, value): "; |
9 | for (int val : vec) { |
10 | std::cout << val << " "; // 输出:10 15 20 30 |
11 | } |
12 | std::cout << std::endl; |
13 | // 在第二个位置(索引为 1)插入 2 个元素 5 |
14 | vec.insert(vec.begin() + 1, 2, 5); |
15 | std::cout << "Vector after insert(position, count, value): "; |
16 | for (int val : vec) { |
17 | std::cout << val << " "; // 输出:10 5 5 15 20 30 |
18 | } |
19 | std::cout << std::endl; |
20 | std::vector<int> anotherVec = {100, 200}; |
21 | // 在向量末尾插入另一个 vector 的元素 |
22 | vec.insert(vec.end(), anotherVec.begin(), anotherVec.end()); |
23 | std::cout << "Vector after insert(position, first, last): "; |
24 | for (int val : vec) { |
25 | std::cout << val << " "; // 输出:10 5 5 15 20 30 100 200 |
26 | } |
27 | std::cout << std::endl; |
28 | return 0; |
29 | } |
⑤ erase(position)
和 erase(first, last)
:移除指定位置或范围的元素
erase()
方法用于移除向量中指定位置或范围的元素。它也有两种重载形式:
⚝ erase(position)
: 移除 position
指向的元素,返回指向被移除元素之后元素的迭代器。
⚝ erase(first, last)
: 移除范围 [first, last)
内的元素,返回指向被移除范围之后元素的迭代器。
erase()
操作同样可能导致元素移动,因此在向量中间位置移除元素的开销相对较大。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40, 50}; |
5 | // 移除第三个元素(索引为 2) |
6 | vec.erase(vec.begin() + 2); |
7 | std::cout << "Vector after erase(position): "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; // 输出:10 20 40 50 |
10 | } |
11 | std::cout << std::endl; |
12 | // 移除前两个元素 |
13 | vec.erase(vec.begin(), vec.begin() + 2); |
14 | std::cout << "Vector after erase(first, last): "; |
15 | for (int val : vec) { |
16 | std::cout << val << " "; // 输出:40 50 |
17 | } |
18 | std::cout << std::endl; |
19 | return 0; |
20 | } |
总结
folly::Vector
提供了丰富的元素添加和移除方法,push_back
和 emplace_back
用于在尾部高效添加元素,pop_back
用于移除尾部元素,而 insert
和 erase
则提供了在任意位置操作元素的能力。在实际应用中,应根据具体场景选择合适的方法,以达到最佳的性能和代码可读性。例如,如果只需要在向量尾部操作,push_back
和 pop_back
通常是首选。如果需要在中间位置频繁插入或删除元素,可能需要考虑其他更适合的容器,如 folly::fbvector
或 std::list
等,或者优化算法以减少中间位置的增删操作。
2.3 元素的访问与修改:下标访问,at(), front(), back() (Accessing and Modifying Elements: Subscript Access, at(), front(), back())
访问和修改向量中的元素是使用 folly::Vector
的基本操作。folly::Vector
提供了多种方式来访问和修改元素,包括下标访问、at()
方法、front()
方法和 back()
方法。本节将详细介绍这些方法,并分析它们的适用场景和安全性。
① 下标访问 []
(Subscript Operator)
下标运算符 []
提供了最直接、最快速的元素访问方式。通过下标,可以直接访问向量中指定索引位置的元素。需要注意的是,下标访问不做边界检查。如果访问越界,即索引值超出向量的有效范围,会导致未定义行为,可能引发程序崩溃或数据错误。因此,在使用下标访问时,务必确保索引的有效性。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | // 访问元素 |
6 | std::cout << "Element at index 0: " << vec[0] << std::endl; // 输出:10 |
7 | std::cout << "Element at index 1: " << vec[1] << std::endl; // 输出:20 |
8 | std::cout << "Element at index 2: " << vec[2] << std::endl; // 输出:30 |
9 | // 修改元素 |
10 | vec[1] = 25; |
11 | std::cout << "Element at index 1 after modification: " << vec[1] << std::endl; // 输出:25 |
12 | // 越界访问 (未定义行为,可能崩溃) |
13 | // std::cout << vec[3] << std::endl; // 潜在的越界访问 |
14 | return 0; |
15 | } |
② at(index)
方法
at()
方法也用于访问向量中指定索引位置的元素,与下标访问 []
的主要区别在于,at()
方法会进行边界检查。如果索引 index
超出向量的有效范围,at()
方法会抛出一个 std::out_of_range
异常。这使得 at()
方法比下标访问更安全,尤其是在不确定索引是否有效的情况下。
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {10, 20, 30}; |
6 | // 访问元素 |
7 | std::cout << "Element at index 0 using at(): " << vec.at(0) << std::endl; // 输出:10 |
8 | // 修改元素 |
9 | vec.at(1) = 25; |
10 | std::cout << "Element at index 1 using at() after modification: " << vec.at(1) << std::endl; // 输出:25 |
11 | // 越界访问,抛出 std::out_of_range 异常 |
12 | try { |
13 | std::cout << vec.at(3) << std::endl; |
14 | } catch (const std::out_of_range& e) { |
15 | std::cerr << "Out of range exception caught: " << e.what() << std::endl; // 输出异常信息 |
16 | } |
17 | return 0; |
18 | } |
③ front()
方法
front()
方法返回向量中第一个元素的引用。调用 front()
前,需要确保向量非空,否则会导致未定义行为。通过 front()
返回的引用,可以访问和修改向量的第一个元素。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | // 访问第一个元素 |
6 | std::cout << "First element using front(): " << vec.front() << std::endl; // 输出:10 |
7 | // 修改第一个元素 |
8 | vec.front() = 5; |
9 | std::cout << "First element using front() after modification: " << vec.front() << std::endl; // 输出:5 |
10 | // 空向量调用 front() (未定义行为,可能崩溃) |
11 | // folly::Vector<int> emptyVec; |
12 | // std::cout << emptyVec.front() << std::endl; // 潜在的未定义行为 |
13 | return 0; |
14 | } |
④ back()
方法
back()
方法返回向量中最后一个元素的引用。与 front()
类似,调用 back()
前也需要确保向量非空,否则会导致未定义行为。通过 back()
返回的引用,可以访问和修改向量的最后一个元素。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | // 访问最后一个元素 |
6 | std::cout << "Last element using back(): " << vec.back() << std::endl; // 输出:30 |
7 | // 修改最后一个元素 |
8 | vec.back() = 35; |
9 | std::cout << "Last element using back() after modification: " << vec.back() << std::endl; // 输出:35 |
10 | // 空向量调用 back() (未定义行为,可能崩溃) |
11 | // folly::Vector<int> emptyVec; |
12 | // std::cout << emptyVec.back() << std::endl; // 潜在的未定义行为 |
13 | return 0; |
14 | } |
方法选择建议
⚝ 下标访问 []
: 效率最高,但不进行边界检查,适用于性能敏感且能保证索引有效性的场景。
⚝ at()
方法: 安全性高,进行边界检查,当索引可能越界时,应优先使用 at()
并进行异常处理。
⚝ front()
和 back()
方法: 用于快速访问向量的首尾元素,但需注意在空向量上调用会导致未定义行为,使用前应检查向量是否为空。
在实际开发中,应根据具体需求权衡性能和安全性,选择合适的元素访问和修改方式。对于可能出现越界访问的场景,推荐使用 at()
方法进行安全访问。
2.4 向量 (Vector) 的大小与容量:size(), capacity(), empty(), reserve(), shrink_to_fit() (Size and Capacity of Vector: size(), capacity(), empty(), reserve(), shrink_to_fit())
理解 folly::Vector
的大小 (size) 和容量 (capacity) 是高效使用向量的关键。size
指的是向量当前包含的元素个数,而 capacity
指的是向量已分配的内存空间可以容纳的元素个数。本节将详细介绍 folly::Vector
提供的与大小和容量相关的操作,包括 size()
, capacity()
, empty()
, reserve()
, 和 shrink_to_fit()
方法。
① size()
方法:获取向量的大小
size()
方法返回向量当前包含的元素个数,即向量的长度。这是一个常量时间复杂度
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; |
5 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:4 |
6 | return 0; |
7 | } |
② capacity()
方法:获取向量的容量
capacity()
方法返回向量当前已分配的内存空间可以容纳的元素个数。容量通常大于等于大小。当向向量添加元素且大小超过容量时,向量会自动重新分配更大的内存空间,容量会增加。重新分配内存可能涉及元素的拷贝或移动,有一定的性能开销。capacity()
也是一个常量时间复杂度
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; |
5 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:4 |
6 | std::cout << "Vector capacity: " << vec.capacity() << std::endl; // 输出:>= 4 (具体值取决于实现) |
7 | for (int i = 0; i < 10; ++i) { |
8 | vec.push_back(i); |
9 | } |
10 | std::cout << "Vector size after push_back: " << vec.size() << std::endl; // 输出:14 |
11 | std::cout << "Vector capacity after push_back: " << vec.capacity() << std::endl; // 输出:>= 14 (容量可能增加) |
12 | return 0; |
13 | } |
③ empty()
方法:检查向量是否为空
empty()
方法返回一个布尔值,用于判断向量是否为空。如果向量的大小为 0,则返回 true
,否则返回 false
。empty()
方法等价于检查 size() == 0
,但通常 empty()
更简洁易读,且可能在某些实现上略有性能优势。empty()
也是常量时间复杂度
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20}; |
5 | folly::Vector<int> vec2; |
6 | std::cout << "vec1 is empty: " << std::boolalpha << vec1.empty() << std::endl; // 输出:false |
7 | std::cout << "vec2 is empty: " << std::boolalpha << vec2.empty() << std::endl; // 输出:true |
8 | return 0; |
9 | } |
④ reserve(n)
方法:预分配容量
reserve(n)
方法用于请求向量至少分配能容纳 n
个元素的内存空间。如果 n
大于当前容量,reserve()
会重新分配内存,使容量至少达到 n
。如果 n
小于或等于当前容量,reserve()
可能不做任何操作。reserve()
不会改变向量的大小,只影响容量。
预先使用 reserve()
可以减少向量在添加元素时因容量不足而导致的多次内存重新分配,从而提高性能,尤其是在预知向量大致大小时。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Initial capacity: " << vec.capacity() << std::endl; // 输出:0 (或初始容量) |
6 | vec.reserve(100); // 预分配 100 个元素的空间 |
7 | std::cout << "Capacity after reserve(100): " << vec.capacity() << std::endl; // 输出:>= 100 |
8 | std::cout << "Size after reserve(100): " << vec.size() << std::endl; // 输出:0 (size 不变) |
9 | for (int i = 0; i < 100; ++i) { |
10 | vec.push_back(i); // 添加元素,通常不会触发多次 reallocate |
11 | } |
12 | std::cout << "Final capacity: " << vec.capacity() << std::endl; // 输出:>= 100 |
13 | std::cout << "Final size: " << vec.size() << std::endl; // 输出:100 |
14 | return 0; |
15 | } |
⑤ shrink_to_fit()
方法:缩小容量以匹配大小
shrink_to_fit()
方法尝试释放向量中多余的容量,将容量缩小到与大小尽可能匹配。调用 shrink_to_fit()
后,capacity()
返回的值可能会减小,但不能保证一定减小,具体的行为取决于实现。shrink_to_fit()
主要用于在向量不再需要添加更多元素时,回收不必要的内存空间。
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | vec.reserve(100); // 预分配 100 个元素的空间 |
6 | std::cout << "Capacity after reserve(100): " << vec.capacity() << std::endl; // 输出:>= 100 |
7 | for (int i = 0; i < 10; ++i) { |
8 | vec.push_back(i); |
9 | } |
10 | std::cout << "Size after push_back: " << vec.size() << std::endl; // 输出:10 |
11 | std::cout << "Capacity before shrink_to_fit(): " << vec.capacity() << std::endl; // 输出:>= 100 |
12 | vec.shrink_to_fit(); // 尝试缩小容量 |
13 | std::cout << "Capacity after shrink_to_fit(): " << vec.capacity() << std::endl; // 输出:可能减小到 >= 10 |
14 | std::cout << "Size after shrink_to_fit(): " << vec.size() << std::endl; // 输出:10 (size 不变) |
15 | return 0; |
16 | } |
总结
理解 folly::Vector
的大小和容量,以及 size()
, capacity()
, empty()
, reserve()
, shrink_to_fit()
等方法,对于编写高效且内存友好的 C++ 代码至关重要。合理使用 reserve()
预分配空间可以提升性能,而 shrink_to_fit()
则可以在适当的时候回收内存。在实际应用中,应根据具体场景灵活运用这些方法,以优化程序的性能和资源利用率。
END_OF_CHAPTER
3. chapter 3: folly::Vector 进阶应用:深入理解
3.1 迭代器 (Iterator) 的使用:遍历向量 (Vector Traversal using Iterators)
迭代器 (Iterator) 是 C++ 标准库中一个 фундаментальный (fundamental) 的概念,它提供了一种统一的方式来遍历各种容器(Container)中的元素。可以将迭代器视为指向容器中元素的指针,但它比指针更加抽象和安全。folly::Vector
作为一种容器,自然也支持迭代器,并且迭代器的使用是深入理解和高效操作 folly::Vector
的关键。
① 迭代器的基本概念
迭代器是一种行为类似指针的对象,它被设计用来遍历和访问容器中的元素序列,而无需暴露容器的内部表示。通过迭代器,我们可以执行以下操作:
⚝ 访问元素:获取迭代器当前指向的元素的值。
⚝ 移动:将迭代器移动到容器中的下一个或上一个元素。
⚝ 比较:检查两个迭代器是否指向同一个位置或容器的末尾。
C++ 标准库和 folly
库定义了多种类型的迭代器,以支持不同类型的遍历和访问需求。对于 folly::Vector
,我们主要关注以下几种迭代器:
⚝ iterator
: 正向迭代器,用于以只读或读写方式访问元素。在 folly::Vector
中,通常是 folly::Vector::iterator
类型。
⚝ const_iterator
: 常量正向迭代器,用于以只读方式访问元素。在 folly::Vector
中,通常是 folly::Vector::const_iterator
类型。
⚝ reverse_iterator
: 反向迭代器,用于以只读或读写方式反向遍历元素。在 folly::Vector
中,通常是 folly::Vector::reverse_iterator
类型。
⚝ const_reverse_iterator
: 常量反向迭代器,用于以只读方式反向遍历元素。在 folly::Vector
中,通常是 folly::Vector::const_reverse_iterator
类型。
② folly::Vector
的迭代器类型
folly::Vector
提供了与 std::vector
类似的迭代器接口,方便用户进行元素遍历。以下是 folly::Vector
中常用的迭代器相关方法:
⚝ begin()
/ cbegin()
: 返回指向向量 (Vector) 第一个元素的迭代器。begin()
返回 iterator
,cbegin()
返回 const_iterator
。
⚝ end()
/ cend()
: 返回指向向量 (Vector) 尾后位置 (one-past-the-end) 的迭代器。end()
返回 iterator
,cend()
返回 const_iterator
。
⚝ rbegin()
/ crbegin()
: 返回指向向量 (Vector) 最后一个元素的反向迭代器。rbegin()
返回 reverse_iterator
,crbegin()
返回 const_reverse_iterator
。
⚝ rend()
/ crend()
: 返回指向向量 (Vector) 第一个元素之前的位置的反向迭代器。rend()
返回 reverse_iterator
,crend()
返回 const_reverse_iterator
。
③ 使用迭代器遍历 folly::Vector
使用迭代器遍历 folly::Vector
是非常常见的操作。以下代码示例展示了如何使用不同类型的迭代器遍历 folly::Vector
:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3, 4, 5}; |
5 | std::cout << "正向迭代遍历 (Forward Iteration):" << std::endl; |
6 | for (auto it = vec.begin(); it != vec.end(); ++it) { |
7 | std::cout << *it << " "; |
8 | } |
9 | std::cout << std::endl; |
10 | std::cout << "常量正向迭代遍历 (Const Forward Iteration):" << std::endl; |
11 | for (auto it = vec.cbegin(); it != vec.cend(); ++it) { |
12 | std::cout << *it << " "; |
13 | } |
14 | std::cout << std::endl; |
15 | std::cout << "反向迭代遍历 (Reverse Iteration):" << std::endl; |
16 | for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) { |
17 | std::cout << *rit << " "; |
18 | } |
19 | std::cout << std::endl; |
20 | std::cout << "常量反向迭代遍历 (Const Reverse Iteration):" << std::endl; |
21 | for (auto rit = vec.crbegin(); rit != vec.crend(); ++rit) { |
22 | std::cout << *rit << " "; |
23 | } |
24 | std::cout << std::endl; |
25 | return 0; |
26 | } |
代码解释:
⚝ 正向迭代: 使用 vec.begin()
获取指向第一个元素的迭代器,vec.end()
获取指向尾后位置的迭代器。循环条件是迭代器 it
不等于 vec.end()
,每次循环递增迭代器 ++it
,使用解引用运算符 *it
访问当前元素。
⚝ 常量正向迭代: 与正向迭代类似,但使用 vec.cbegin()
和 vec.cend()
获取常量迭代器,保证在遍历过程中不会修改元素。
⚝ 反向迭代: 使用 vec.rbegin()
获取指向最后一个元素的反向迭代器,vec.rend()
获取指向第一个元素之前位置的反向迭代器。循环条件是反向迭代器 rit
不等于 vec.rend()
,每次循环递增反向迭代器 ++rit
,使用解引用运算符 *rit
访问当前元素。
⚝ 常量反向迭代: 与反向迭代类似,但使用 vec.crbegin()
和 vec.crend()
获取常量反向迭代器,保证在反向遍历过程中不会修改元素。
④ 基于范围的 for 循环 (Range-based for loop)
C++11 引入了基于范围的 for 循环,它简化了容器的遍历操作,使得代码更加简洁易读。基于范围的 for 循环底层也是使用迭代器实现的。以下代码示例展示了如何使用基于范围的 for 循环遍历 folly::Vector
:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3, 4, 5}; |
5 | std::cout << "基于范围的 for 循环遍历 (Range-based for loop):" << std::endl; |
6 | for (int val : vec) { |
7 | std::cout << val << " "; |
8 | } |
9 | std::cout << std::endl; |
10 | std::cout << "基于范围的 for 循环遍历 (引用修改元素):" << std::endl; |
11 | for (int& val : vec) { |
12 | val *= 2; // 修改元素的值 |
13 | std::cout << val << " "; |
14 | } |
15 | std::cout << std::endl; |
16 | std::cout << "遍历修改后的向量 (Vector):" << std::endl; |
17 | for (int val : vec) { |
18 | std::cout << val << " "; |
19 | } |
20 | std::cout << std::endl; |
21 | return 0; |
22 | } |
代码解释:
⚝ for (int val : vec)
: 这是一种只读遍历方式,val
会被赋值为向量 (Vector) 中的每个元素的值,但不会修改原始向量 (Vector) 中的元素。
⚝ for (int& val : vec)
: 这是一种读写遍历方式,val
是向量 (Vector) 中每个元素的引用,可以直接修改原始向量 (Vector) 中的元素。
⑤ 迭代器失效 (Iterator Invalidation)
迭代器失效是一个重要的概念,尤其在使用动态容器如 folly::Vector
时需要特别注意。当容器的内部结构发生变化时,之前获得的迭代器可能会失效,导致未定义行为。对于 folly::Vector
,以下操作可能会导致迭代器失效:
⚝ 插入元素 (insert
, push_back
, emplace_back
等): 在向量 (Vector) 中间或尾部插入元素,如果引起向量 (Vector) 重新分配内存,则所有迭代器、指针和引用都可能失效。如果在尾部插入元素没有引起重新分配内存,则只有指向插入点之后元素的迭代器、指针和引用会失效。
⚝ 删除元素 (erase
, pop_back
等): 删除元素会导致被删除元素之后的所有元素的移动,因此指向被删除元素以及之后元素的迭代器、指针和引用都会失效。
⚝ resize()
: 改变向量 (Vector) 大小可能会导致内存重新分配,从而使迭代器失效。
⚝ clear()
: 清空向量 (Vector) 会使所有迭代器失效。
最佳实践:
⚝ 尽量避免在迭代器遍历过程中修改向量 (Vector) 的大小或结构。
⚝ 如果需要在遍历过程中修改向量 (Vector),需要仔细考虑迭代器失效的影响,并采取相应的措施,例如在修改后重新获取迭代器。
⚝ 使用基于范围的 for 循环时,要特别注意循环体内对容器的操作,避免潜在的迭代器失效问题。
理解和正确使用迭代器是高效操作 folly::Vector
的基础。掌握不同类型的迭代器,了解迭代器失效的场景,并遵循最佳实践,可以编写出更健壮、更高效的代码。
3.2 范围 (Range) 构造与操作 (Range Construction and Operations)
范围 (Range) 是 C++20 引入的一个重要概念,它提供了一种更抽象、更灵活的方式来处理数据序列。范围可以看作是一对迭代器,表示一个序列的起始和结束位置。folly::Vector
可以与范围一起使用,进行更便捷的构造和操作。
① 范围的概念
一个范围 (Range) 通常由一对迭代器 [begin, end)
定义,其中 begin
指向序列的起始位置,end
指向序列的尾后位置。范围的概念不仅仅局限于容器,任何可以用迭代器表示的序列都可以被视为一个范围。
C++20 标准库提供了 <ranges>
头文件,其中定义了许多与范围相关的概念 (Concepts)、视图 (Views) 和算法 (Algorithms)。范围库旨在提供更简洁、更高效、更可组合的方式来处理数据序列。
② folly::Vector
的范围构造
folly::Vector
可以使用范围进行构造,这意味着我们可以使用任何符合范围概念的对象来初始化 folly::Vector
。常见的范围来源包括:
⚝ 其他容器的迭代器范围: 例如,可以使用 std::vector
或其他 folly::Vector
的迭代器范围来构造新的 folly::Vector
。
⚝ C 数组: C 数组可以退化为指针,指针可以作为迭代器,因此可以使用 C 数组的范围来构造 folly::Vector
。
⚝ 初始化列表: 初始化列表本身就可以看作是一个范围。
以下代码示例展示了 folly::Vector
的范围构造:
1 | |
2 | |
3 | |
4 | int main() { |
5 | std::vector<int> stdVec = {1, 2, 3, 4, 5}; |
6 | folly::Vector<int> follyVec1(stdVec.begin(), stdVec.end()); // 使用 std::vector 的迭代器范围构造 |
7 | folly::Vector<int> follyVec2(follyVec1.cbegin(), follyVec1.cend()); // 使用 folly::Vector 的迭代器范围构造 |
8 | int arr[] = {6, 7, 8, 9, 10}; |
9 | folly::Vector<int> follyVec3(arr, arr + sizeof(arr) / sizeof(arr[0])); // 使用 C 数组的范围构造 |
10 | folly::Vector<int> follyVec4 = {11, 12, 13}; // 使用初始化列表构造 (本身就是一种范围) |
11 | std::cout << "follyVec1: "; |
12 | for (int val : follyVec1) std::cout << val << " "; |
13 | std::cout << std::endl; |
14 | std::cout << "follyVec2: "; |
15 | for (int val : follyVec2) std::cout << val << " "; |
16 | std::cout << std::endl; |
17 | std::cout << "follyVec3: "; |
18 | for (int val : follyVec3) std::cout << val << " "; |
19 | std::cout << std::endl; |
20 | std::cout << "follyVec4: "; |
21 | for (int val : follyVec4) std::cout << val << " "; |
22 | std::cout << std::endl; |
23 | return 0; |
24 | } |
代码解释:
⚝ folly::Vector<int> follyVec1(stdVec.begin(), stdVec.end());
: 使用 std::vector
stdVec
的迭代器范围 [stdVec.begin(), stdVec.end())
构造 follyVec1
。
⚝ folly::Vector<int> follyVec2(follyVec1.cbegin(), follyVec1.cend());
: 使用 folly::Vector
follyVec1
的常量迭代器范围 [follyVec1.cbegin(), follyVec1.cend())
构造 follyVec2
。
⚝ folly::Vector<int> follyVec3(arr, arr + sizeof(arr) / sizeof(arr[0]));
: 使用 C 数组 arr
的范围 [arr, arr + size)
构造 follyVec3
,其中 size
是数组的大小。
⚝ folly::Vector<int> follyVec4 = {11, 12, 13};
: 使用初始化列表直接构造 follyVec4
。
③ 范围操作与算法
C++ 标准库 <algorithm>
头文件中提供了大量的算法,可以用于操作各种范围,包括 folly::Vector
。这些算法通常接受一对迭代器作为参数,表示要操作的范围。
以下是一些常用的范围操作算法示例:
⚝ std::copy
: 将一个范围的元素复制到另一个范围。
⚝ std::transform
: 将一个范围的元素经过某种变换后复制到另一个范围。
⚝ std::for_each
: 对一个范围的每个元素执行某个操作。
⚝ std::find
: 在一个范围中查找特定元素。
⚝ std::sort
: 对一个范围的元素进行排序。
1 | |
2 | |
3 | |
4 | |
5 | int main() { |
6 | folly::Vector<int> srcVec = {1, 2, 3, 4, 5}; |
7 | folly::Vector<int> destVec(srcVec.size()); // 预分配目标向量 (Vector) 的空间 |
8 | // 使用 std::copy 将 srcVec 的元素复制到 destVec |
9 | std::copy(srcVec.begin(), srcVec.end(), destVec.begin()); |
10 | std::cout << "std::copy: destVec = "; |
11 | for (int val : destVec) std::cout << val << " "; |
12 | std::cout << std::endl; |
13 | folly::Vector<int> transformedVec(srcVec.size()); |
14 | // 使用 std::transform 将 srcVec 的元素平方后复制到 transformedVec |
15 | std::transform(srcVec.begin(), srcVec.end(), transformedVec.begin(), [](int x){ return x * x; }); |
16 | std::cout << "std::transform: transformedVec = "; |
17 | for (int val : transformedVec) std::cout << val << " "; |
18 | std::cout << std::endl; |
19 | // 使用 std::for_each 打印 srcVec 的元素 |
20 | std::cout << "std::for_each: srcVec elements = "; |
21 | std::for_each(srcVec.begin(), srcVec.end(), [](int x){ std::cout << x << " "; }); |
22 | std::cout << std::endl; |
23 | // 使用 std::find 在 srcVec 中查找元素 3 |
24 | auto it = std::find(srcVec.begin(), srcVec.end(), 3); |
25 | if (it != srcVec.end()) { |
26 | std::cout << "std::find: Element 3 found at position: " << std::distance(srcVec.begin(), it) << std::endl; |
27 | } else { |
28 | std::cout << "std::find: Element 3 not found" << std::endl; |
29 | } |
30 | folly::Vector<int> sortedVec = {5, 2, 1, 4, 3}; |
31 | // 使用 std::sort 对 sortedVec 进行排序 |
32 | std::sort(sortedVec.begin(), sortedVec.end()); |
33 | std::cout << "std::sort: sortedVec = "; |
34 | for (int val : sortedVec) std::cout << val << " "; |
35 | std::cout << std::endl; |
36 | return 0; |
37 | } |
代码解释:
⚝ std::copy(srcVec.begin(), srcVec.end(), destVec.begin());
: 将 srcVec
的范围 [srcVec.begin(), srcVec.end())
的元素复制到 destVec
的范围,目标范围的起始位置是 destVec.begin()
。
⚝ std::transform(srcVec.begin(), srcVec.end(), transformedVec.begin(), [](int x){ return x * x; });
: 将 srcVec
的范围的元素经过 lambda 表达式 [](int x){ return x * x; }
的变换(平方)后,复制到 transformedVec
的范围。
⚝ std::for_each(srcVec.begin(), srcVec.end(), [](int x){ std::cout << x << " "; });
: 对 srcVec
的范围的每个元素执行 lambda 表达式 [](int x){ std::cout << x << " "; }
,即打印元素。
⚝ std::find(srcVec.begin(), srcVec.end(), 3);
: 在 srcVec
的范围中查找元素 3
,返回指向找到元素的迭代器,如果未找到则返回 srcVec.end()
。
⚝ std::sort(sortedVec.begin(), sortedVec.end());
: 对 sortedVec
的范围进行升序排序。
④ C++20 范围库 (Ranges Library)
C++20 引入了 <ranges>
库,提供了更高级的范围抽象和操作方式。虽然 folly::Vector
本身不是 C++20 范围库的一部分,但它可以与范围库提供的视图 (Views) 和算法 (Algorithms) 协同工作。
C++20 范围库的核心概念包括:
⚝ 视图 (Views): 视图是轻量级的范围适配器,可以对现有范围进行转换、过滤、组合等操作,而无需复制数据。例如,std::views::transform
, std::views::filter
, std::views::take
, std::views::drop
等。
⚝ 范围算法 (Range Algorithms): 范围算法是 <algorithm>
头文件中算法的范围版本,它们接受范围作为参数,而不是迭代器对。例如,std::ranges::copy
, std::ranges::transform
, std::ranges::sort
等。
使用 C++20 范围库可以编写更简洁、更易读、更高效的代码来处理 folly::Vector
和其他容器。
示例 (需要 C++20 支持):
1 | |
2 | |
3 | |
4 | |
5 | int main() { |
6 | folly::Vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; |
7 | // 使用 C++20 范围视图和算法 |
8 | auto even_squares = vec | std::views::filter([](int n){ return n % 2 == 0; }) |
9 | | std::views::transform([](int n){ return n * n; }); |
10 | std::cout << "Even squares using C++20 ranges: "; |
11 | for (int val : even_squares) { |
12 | std::cout << val << " "; |
13 | } |
14 | std::cout << std::endl; |
15 | std::vector<int> result_vec; |
16 | std::ranges::copy(even_squares, std::back_inserter(result_vec)); // 复制到 std::vector |
17 | std::cout << "Result vector after range copy: "; |
18 | for (int val : result_vec) { |
19 | std::cout << val << " "; |
20 | } |
21 | std::cout << std::endl; |
22 | return 0; |
23 | } |
代码解释:
⚝ vec | std::views::filter(...) | std::views::transform(...)
: 使用管道操作符 |
将 vec
转换为一个范围视图,首先使用 std::views::filter
过滤出偶数,然后使用 std::views::transform
将偶数平方。整个过程是惰性求值的,只有在迭代 even_squares
时才会实际计算。
⚝ std::ranges::copy(even_squares, std::back_inserter(result_vec));
: 使用 std::ranges::copy
将范围视图 even_squares
的元素复制到 std::vector
result_vec
中。std::back_inserter
用于在 result_vec
尾部插入元素。
范围构造和操作为 folly::Vector
提供了更强大的灵活性和表达能力。结合 C++ 标准库的算法和 C++20 范围库,可以更高效、更简洁地处理 folly::Vector
中的数据。
3.3 移动语义 (Move Semantics) 与 folly::Vector:性能优化 (Move Semantics and folly::Vector: Performance Optimization)
移动语义 (Move Semantics) 是 C++11 引入的核心特性之一,旨在提高程序性能,尤其是在处理大型对象时。移动语义允许资源(例如动态分配的内存)的所有权在对象之间高效转移,而无需进行深拷贝 (Deep Copy)。folly::Vector
充分利用了移动语义,从而在很多场景下实现了显著的性能提升。
① 深拷贝与浅拷贝 (Deep Copy vs. Shallow Copy) 的问题
在传统的 C++ 中,对象拷贝通常是通过拷贝构造函数 (Copy Constructor) 和拷贝赋值运算符 (Copy Assignment Operator) 来实现的。默认情况下,这些操作执行的是深拷贝,即会复制对象的所有成员,包括动态分配的资源。
对于包含大量动态分配资源的类(例如 folly::Vector
),深拷贝的代价非常高昂,因为它需要分配新的内存,并将原有数据完整复制过去。在某些情况下,这种深拷贝是不必要的,例如:
⚝ 临时对象: 当拷贝源是一个临时对象时,临时对象在拷贝后立即销毁,此时进行深拷贝会造成不必要的资源浪费。
⚝ 移动操作: 有时我们只是想将资源的所有权从一个对象转移到另一个对象,而不是真正复制资源。
② 移动语义的引入
移动语义正是为了解决深拷贝带来的性能问题而引入的。移动语义的核心思想是:对于不再需要的对象(例如临时对象),可以将其拥有的资源“移动”给目标对象,而不是进行昂贵的深拷贝。
移动语义主要通过以下机制实现:
⚝ 移动构造函数 (Move Constructor): 用于从一个右值引用 (Rvalue Reference) 对象构造新对象。移动构造函数通常会将源对象的资源“窃取”过来,并将源对象置于有效但未指定的状态。
⚝ 移动赋值运算符 (Move Assignment Operator): 用于将一个右值引用对象赋值给已存在的对象。移动赋值运算符也会将源对象的资源“移动”给目标对象,并销毁目标对象原有的资源。
⚝ 右值引用 (Rvalue Reference): C++11 引入了右值引用 &&
,用于区分左值 (Lvalue) 和右值 (Rvalue)。右值引用可以绑定到临时对象或即将销毁的对象,从而可以安全地“移动”其资源。
⚝ std::move
: std::move
是一个类型转换函数,可以将一个左值转换为右值引用,从而可以触发移动操作。需要注意的是,std::move
本身并不执行移动操作,它只是将左值转换为右值引用,是否执行移动操作取决于后续的操作(例如是否调用了移动构造函数或移动赋值运算符)。
③ folly::Vector
对移动语义的支持
folly::Vector
实现了移动构造函数和移动赋值运算符,充分利用了移动语义来提高性能。当涉及到 folly::Vector
的移动操作时,例如:
⚝ 移动构造: folly::Vector<T> v2 = std::move(v1);
// 从 v1 移动构造 v2
⚝ 移动赋值: v2 = std::move(v1);
// 将 v1 移动赋值给 v2
⚝ 函数返回值: 当函数返回 folly::Vector<T>
对象时,如果返回的是局部变量,编译器通常会进行返回值优化 (Return Value Optimization, RVO) 或移动构造,避免深拷贝。
⚝ emplace_back
和 push_back
: 当使用 emplace_back
或 push_back
添加元素时,如果元素类型支持移动构造,且传入的是右值,则会优先调用移动构造函数,而不是拷贝构造函数。
在这些情况下,folly::Vector
的移动操作通常只需要进行浅拷贝,即复制一些指针和大小信息,而无需复制底层的数据缓冲区。这大大提高了性能,尤其是在向量 (Vector) 存储大量元素时。
④ 移动语义的性能优势示例
以下代码示例对比了拷贝构造和移动构造的性能差异,展示了移动语义的优势:
1 | |
2 | |
3 | |
4 | |
5 | using namespace std::chrono; |
6 | int main() { |
7 | size_t size = 1000000; // 向量 (Vector) 大小 |
8 | folly::Vector<int> vec1(size); |
9 | std::iota(vec1.begin(), vec1.end(), 0); // 初始化向量 (Vector) |
10 | // 拷贝构造 |
11 | auto start_copy = high_resolution_clock::now(); |
12 | folly::Vector<int> vec2 = vec1; // 拷贝构造 |
13 | auto end_copy = high_resolution_clock::now(); |
14 | auto duration_copy = duration_cast<milliseconds>(end_copy - start_copy); |
15 | // 移动构造 |
16 | auto start_move = high_resolution_clock::now(); |
17 | folly::Vector<int> vec3 = std::move(vec1); // 移动构造 |
18 | auto end_move = high_resolution_clock::now(); |
19 | auto duration_move = duration_cast<milliseconds>(end_move - start_move); |
20 | std::cout << "向量 (Vector) 大小: " << size << std::endl; |
21 | std::cout << "拷贝构造耗时: " << duration_copy.count() << " 毫秒" << std::endl; |
22 | std::cout << "移动构造耗时: " << duration_move.count() << " 毫秒" << std::endl; |
23 | return 0; |
24 | } |
代码解释:
⚝ 代码创建了一个包含一百万个整数的 folly::Vector
vec1
。
⚝ 拷贝构造: folly::Vector<int> vec2 = vec1;
执行深拷贝,需要分配新的内存并复制所有元素。
⚝ 移动构造: folly::Vector<int> vec3 = std::move(vec1);
执行移动构造,只需要转移 vec1
的内部资源所有权,无需复制元素。
⚝ 代码分别测量了拷贝构造和移动构造的耗时,并输出结果。
运行结果分析 (结果可能因环境而异):
通常情况下,移动构造的耗时会远小于拷贝构造,尤其是在向量 (Vector) 存储大量元素时。这是因为移动构造避免了昂贵的深拷贝操作,只需要进行浅拷贝和资源转移。
⑤ 移动语义的应用场景
移动语义在以下场景中尤其重要,可以显著提高性能:
⚝ 返回大型对象: 函数返回大型对象(例如 folly::Vector
)时,使用移动语义可以避免不必要的拷贝。
⚝ 容器元素的插入和删除: 使用 emplace_back
, push_back
, insert
, erase
等操作时,移动语义可以减少元素的拷贝次数。
⚝ 排序和算法: 在排序和使用其他算法时,如果元素类型支持移动语义,算法可以利用移动操作来提高效率。
⚝ 资源管理: 移动语义可以用于实现高效的资源管理,例如智能指针 (Smart Pointer) 和 RAII (Resource Acquisition Is Initialization)。
最佳实践:
⚝ 尽可能使自定义类型支持移动语义,即实现移动构造函数和移动赋值运算符。
⚝ 在需要转移资源所有权时,使用 std::move
将左值转换为右值引用,触发移动操作。
⚝ 了解编译器的返回值优化 (RVO) 和命名返回值优化 (NRVO),可以进一步减少拷贝操作。
⚝ 在设计类时,考虑移动语义,避免不必要的深拷贝,提高程序性能。
移动语义是现代 C++ 中不可或缺的特性,它为性能优化提供了强大的工具。理解和应用移动语义,可以编写出更高效、更快速的 folly::Vector
代码。
3.4 自定义类型与 folly::Vector:对象存储 (Custom Types and folly::Vector: Object Storage)
folly::Vector
不仅可以存储内置类型(如 int
, float
等),还可以存储自定义类型的对象,例如类 (Class) 或结构体 (Struct) 的实例。将自定义类型的对象存储在 folly::Vector
中,可以方便地管理和操作复杂的数据结构。
① 自定义类型存储的基本要求
当将自定义类型的对象存储在 folly::Vector
中时,需要确保自定义类型满足一定的要求,以便 folly::Vector
能够正确地管理和操作这些对象。主要的要求包括:
⚝ 可拷贝构造 (CopyConstructible) 或 可移动构造 (MoveConstructible): folly::Vector
在插入、复制、移动等操作时,可能需要拷贝或移动容器中的元素。因此,存储在 folly::Vector
中的类型必须是可拷贝构造或可移动构造的。通常情况下,最好同时提供拷贝构造函数和移动构造函数,以获得最佳性能。
⚝ 可赋值 (CopyAssignable) 或 可移动赋值 (MoveAssignable): 类似于构造,folly::Vector
在赋值操作时,可能需要对容器中的元素进行赋值。因此,存储的类型需要是可赋值或可移动赋值的。同样,最好同时提供拷贝赋值运算符和移动赋值运算符。
⚝ 可析构 (Destructible): 当 folly::Vector
销毁或元素被移除时,需要正确地析构容器中的元素。因此,存储的类型必须是可析构的,即需要提供析构函数 (Destructor)。
对于简单的自定义类型,编译器通常会自动生成默认的拷贝构造函数、移动构造函数、拷贝赋值运算符、移动赋值运算符和析构函数。但对于复杂的自定义类型,特别是包含动态分配资源的类型,通常需要显式地定义这些特殊成员函数,以确保资源管理的正确性和效率。
② 存储自定义类的示例
以下代码示例展示了如何创建一个自定义类 Person
,并将其对象存储在 folly::Vector
中:
1 | |
2 | |
3 | |
4 | class Person { |
5 | public: |
6 | std::string name; |
7 | int age; |
8 | // 默认构造函数 |
9 | Person() : name("Unknown"), age(0) { |
10 | std::cout << "Person 默认构造函数被调用" << std::endl; |
11 | } |
12 | // 拷贝构造函数 |
13 | Person(const Person& other) : name(other.name), age(other.age) { |
14 | std::cout << "Person 拷贝构造函数被调用" << std::endl; |
15 | } |
16 | // 移动构造函数 |
17 | Person(Person&& other) noexcept : name(std::move(other.name)), age(other.age) { |
18 | std::cout << "Person 移动构造函数被调用" << std::endl; |
19 | } |
20 | // 析构函数 |
21 | ~Person() { |
22 | std::cout << "Person 析构函数被调用,name: " << name << std::endl; |
23 | } |
24 | void print() const { |
25 | std::cout << "Name: " << name << ", Age: " << age << std::endl; |
26 | } |
27 | }; |
28 | int main() { |
29 | folly::Vector<Person> people; |
30 | std::cout << "添加 Person 对象到向量 (Vector):" << std::endl; |
31 | people.emplace_back(); // 默认构造 |
32 | people.emplace_back("Alice", 30); // 使用构造函数参数 |
33 | Person bob("Bob", 25); |
34 | people.push_back(bob); // 拷贝构造 |
35 | people.push_back(std::move(bob)); // 移动构造 (bob 对象之后处于有效但不确定状态) |
36 | std::cout << "\n遍历向量 (Vector) 中的 Person 对象:" << std::endl; |
37 | for (const auto& person : people) { |
38 | person.print(); |
39 | } |
40 | std::cout << "\n程序结束" << std::endl; |
41 | return 0; |
42 | } |
代码解释:
⚝ Person
类: 定义了一个简单的 Person
类,包含 name
(姓名) 和 age
(年龄) 两个成员变量,并显式定义了默认构造函数、拷贝构造函数、移动构造函数和析构函数,并在构造和析构函数中添加了输出语句,以便观察对象的生命周期。
⚝ folly::Vector<Person> people;
: 创建了一个存储 Person
对象的 folly::Vector
。
⚝ people.emplace_back();
: 使用 emplace_back()
默认构造一个 Person
对象并添加到向量 (Vector) 尾部。
⚝ people.emplace_back("Alice", 30);
: 使用 emplace_back()
和构造函数参数,直接在向量 (Vector) 内部构造 Person
对象。
⚝ people.push_back(bob);
: 使用 push_back()
添加 bob
对象,会调用 Person
的拷贝构造函数。
⚝ people.push_back(std::move(bob));
: 使用 push_back()
和 std::move()
添加 bob
对象,会调用 Person
的移动构造函数。
⚝ 遍历: 使用基于范围的 for 循环遍历 people
向量 (Vector),并调用 person.print()
打印每个 Person
对象的信息。
运行结果分析 (观察构造和析构函数的调用):
通过观察程序的输出,可以清晰地看到不同操作下构造函数和析构函数的调用情况,从而理解 folly::Vector
如何管理自定义类型的对象,以及拷贝构造和移动构造的区别。
③ 对象切片 (Object Slicing) 问题
当存储具有继承关系的类对象时,需要注意对象切片 (Object Slicing) 问题。对象切片发生在将派生类 (Derived Class) 对象赋值给基类 (Base Class) 对象时,派生类对象特有的部分会被“切掉”,只保留基类部分。
如果将派生类对象以基类类型存储在 folly::Vector
中,就会发生对象切片,导致信息丢失。为了避免对象切片,可以使用指针或智能指针来存储对象,例如 folly::Vector<Person*>
, folly::Vector<std::unique_ptr<Person>>
, folly::Vector<std::shared_ptr<Person>>
。
示例 (对象切片):
1 | |
2 | |
3 | |
4 | class Animal { |
5 | public: |
6 | std::string name; |
7 | Animal(std::string n) : name(n) {} |
8 | virtual void makeSound() const { std::cout << "Generic animal sound" << std::endl; } |
9 | }; |
10 | class Dog : public Animal { |
11 | public: |
12 | std::string breed; |
13 | Dog(std::string n, std::string b) : Animal(n), breed(b) {} |
14 | void makeSound() const override { std::cout << "Woof!" << std::endl; } |
15 | void printBreed() const { std::cout << "Breed: " << breed << std::endl; } |
16 | }; |
17 | int main() { |
18 | folly::Vector<Animal> animals; |
19 | Dog dog("Buddy", "Golden Retriever"); |
20 | animals.push_back(dog); // 对象切片发生! |
21 | std::cout << "存储在向量 (Vector) 中的动物:" << std::endl; |
22 | for (const auto& animal : animals) { |
23 | animal.makeSound(); // 调用的是基类 Animal 的 makeSound() |
24 | // animal.printBreed(); // 编译错误! Animal 类没有 printBreed() 方法 |
25 | } |
26 | return 0; |
27 | } |
代码解释:
⚝ Animal
和 Dog
类: Dog
类继承自 Animal
类,并重写了 makeSound()
方法,添加了 printBreed()
方法。
⚝ folly::Vector<Animal> animals;
: 创建了一个存储 Animal
对象的 folly::Vector
。
⚝ animals.push_back(dog);
: 将 Dog
对象 dog
添加到 animals
向量 (Vector) 中,由于向量 (Vector) 存储的是 Animal
类型,发生了对象切片,Dog
对象特有的 breed
成员被切掉。
⚝ 遍历: 遍历 animals
向量 (Vector),调用 animal.makeSound()
,由于对象切片,调用的是基类 Animal
的 makeSound()
方法,而不是派生类 Dog
的 makeSound()
方法。尝试调用 animal.printBreed()
会导致编译错误,因为 Animal
类没有 printBreed()
方法。
④ 使用指针或智能指针避免对象切片
为了避免对象切片,可以使用指针或智能指针来存储对象,实现多态 (Polymorphism) 行为。
示例 (使用指针避免对象切片):
1 | |
2 | |
3 | |
4 | // ... (Animal 和 Dog 类的定义与之前相同) ... |
5 | int main() { |
6 | folly::Vector<Animal*> animalPtrs; |
7 | Dog* dogPtr = new Dog("Buddy", "Golden Retriever"); |
8 | Animal* animalPtr = dogPtr; // 基类指针指向派生类对象 |
9 | animalPtrs.push_back(animalPtr); |
10 | std::cout << "存储在向量 (Vector) 中的动物 (使用指针):" << std::endl; |
11 | for (const auto* ptr : animalPtrs) { |
12 | ptr->makeSound(); // 调用的是派生类 Dog 的 makeSound() (多态) |
13 | Dog* dog_ptr = dynamic_cast<Dog*>(ptr); // 向下转型 |
14 | if (dog_ptr) { |
15 | dog_ptr->printBreed(); // 可以安全地调用 Dog 类的方法 |
16 | } |
17 | } |
18 | // 手动释放内存 (使用智能指针可以自动管理内存) |
19 | delete dogPtr; |
20 | return 0; |
21 | } |
代码解释:
⚝ folly::Vector<Animal*> animalPtrs;
: 创建了一个存储 Animal
指针的 folly::Vector
。
⚝ Animal* animalPtr = dogPtr;
: 基类指针 animalPtr
指向派生类对象 dogPtr
。
⚝ animalPtrs.push_back(animalPtr);
: 将基类指针 animalPtr
添加到 animalPtrs
向量 (Vector) 中。
⚝ 遍历: 遍历 animalPtrs
向量 (Vector),调用 ptr->makeSound()
,由于使用了指针,实现了多态,调用的是派生类 Dog
的 makeSound()
方法。
⚝ 向下转型: 使用 dynamic_cast<Dog*>(ptr)
将基类指针 ptr
向下转型为 Dog*
指针,如果转型成功(即指针指向的是 Dog
对象),则可以安全地调用 Dog
类特有的方法 printBreed()
。
⚝ 手动释放内存: 由于使用了裸指针,需要手动 delete dogPtr
释放内存。
使用智能指针 (例如 std::unique_ptr
, std::shared_ptr
) 可以自动管理内存,避免手动 delete
,并提高代码的安全性。
存储自定义类型对象到 folly::Vector
提供了强大的数据组织和管理能力。理解自定义类型存储的要求,注意对象切片问题,并合理使用指针或智能指针,可以充分发挥 folly::Vector
在复杂数据结构处理中的优势。
3.5 异常处理与 folly::Vector (Exception Handling and folly::Vector)
异常处理 (Exception Handling) 是 C++ 中处理运行时错误和异常情况的重要机制。folly::Vector
作为一种容器,在某些操作中可能会抛出异常。了解 folly::Vector
的异常安全性 (Exception Safety) 以及如何正确地进行异常处理,对于编写健壮的程序至关重要。
① folly::Vector
可能抛出的异常
folly::Vector
的操作在以下情况下可能会抛出异常:
⚝ 内存分配失败: 当 folly::Vector
需要分配更多内存来存储元素时(例如 push_back
, emplace_back
, reserve
, resize
等操作),如果系统内存不足,folly::Vector
会抛出 std::bad_alloc
异常。
⚝ 越界访问: 当使用 at()
方法访问超出有效索引范围的元素时,folly::Vector
会抛出 std::out_of_range
异常。需要注意的是,使用下标运算符 []
进行越界访问是未定义行为,不会抛出异常。
② folly::Vector
的异常安全性保证
folly::Vector
提供了不同级别的异常安全性保证,以确保在异常发生时,程序的状态仍然是可预测和可恢复的。folly::Vector
提供的异常安全性级别主要包括:
⚝ 基本保证 (Basic Guarantee): 如果操作抛出异常,程序不会崩溃,容器中的数据不会损坏,但容器的状态可能处于某种不确定但有效 (valid) 的状态。例如,在 push_back
操作中,如果内存分配失败抛出 std::bad_alloc
异常,folly::Vector
可能会保持之前的状态,但新元素可能没有被添加到容器中。
⚝ 强异常安全性保证 (Strong Exception Safety Guarantee): 如果操作抛出异常,操作要么完全成功,要么完全没有效果,程序的状态保持在操作之前的状态。对于 folly::Vector
的某些操作,例如单元素插入 (insert
, emplace
),可以提供强异常安全性保证(如果元素类型的拷贝构造函数或移动构造函数提供强异常安全性保证)。
⚝ 无异常保证 (No-throw Guarantee): 某些操作保证不会抛出任何异常。例如,folly::Vector
的析构函数、swap
操作、以及某些只读操作(如 size
, empty
, begin
, end
等)通常提供无异常保证。
③ 使用 try-catch
块处理异常
可以使用 try-catch
块来捕获和处理 folly::Vector
操作可能抛出的异常。以下代码示例展示了如何使用 try-catch
块处理 std::bad_alloc
和 std::out_of_range
异常:
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec; |
6 | try { |
7 | // 尝试分配大量内存,可能抛出 std::bad_alloc |
8 | vec.reserve(SIZE_MAX); // 尝试预分配最大可能的空间 |
9 | std::cout << "成功预分配大量内存 (实际上可能不会真正分配)" << std::endl; |
10 | } catch (const std::bad_alloc& e) { |
11 | std::cerr << "内存分配失败异常 (std::bad_alloc): " << e.what() << std::endl; |
12 | // 处理内存分配失败的情况,例如: |
13 | // 1. 释放已分配的资源 |
14 | // 2. 记录错误日志 |
15 | // 3. 尝试其他操作或退出程序 |
16 | } |
17 | try { |
18 | // 尝试越界访问,可能抛出 std::out_of_range |
19 | int val = vec.at(10); // 使用 at() 进行安全访问 |
20 | std::cout << "访问索引 10 的元素: " << val << std::endl; // 不会执行到这里 |
21 | } catch (const std::out_of_range& e) { |
22 | std::cerr << "越界访问异常 (std::out_of_range): " << e.what() << std::endl; |
23 | // 处理越界访问的情况,例如: |
24 | // 1. 检查索引是否有效 |
25 | // 2. 提供默认值或采取其他补救措施 |
26 | } |
27 | std::cout << "程序继续执行..." << std::endl; |
28 | return 0; |
29 | } |
代码解释:
⚝ try-catch
块: 使用 try
块包裹可能抛出异常的代码,使用 catch
块捕获特定类型的异常。
⚝ catch (const std::bad_alloc& e)
: 捕获 std::bad_alloc
异常,通常在内存分配失败时抛出。
⚝ catch (const std::out_of_range& e)
: 捕获 std::out_of_range
异常,通常在使用 at()
进行越界访问时抛出。
⚝ 异常处理代码: 在 catch
块中,可以编写相应的异常处理代码,例如打印错误信息、记录日志、释放资源、尝试恢复或安全退出程序。
④ 异常处理的最佳实践
⚝ 尽早捕获异常: 在异常发生后尽快捕获和处理异常,避免异常传播到更上层,导致程序状态不可控。
⚝ 只捕获需要处理的异常: catch
块应该只捕获程序能够处理的异常类型,对于无法处理的异常,应该让其继续传播,或者使用默认的异常处理机制。
⚝ 异常处理代码要简洁高效: catch
块中的代码应该尽可能简洁高效,避免在异常处理代码中再次抛出异常,导致嵌套异常。
⚝ 使用 RAII 管理资源: 使用 RAII (Resource Acquisition Is Initialization) 技术,例如智能指针,可以自动管理资源,即使在异常发生时也能确保资源被正确释放,避免资源泄漏。
⚝ 考虑异常安全性级别: 在设计程序时,需要考虑不同操作的异常安全性级别,并根据实际需求选择合适的异常处理策略。
⑤ noexcept
规范
C++11 引入了 noexcept
规范,用于声明函数是否会抛出异常。对于保证不抛出异常的函数,可以使用 noexcept
关键字进行标记。folly::Vector
的某些操作,例如移动构造函数、移动赋值运算符、析构函数等,通常会被声明为 noexcept
。
使用 noexcept
规范可以帮助编译器进行更好的优化,并提高程序的可靠性。在自定义类型中,如果某些操作确实保证不抛出异常,也应该使用 noexcept
进行标记。
异常处理是编写健壮 C++ 程序的重要组成部分。理解 folly::Vector
的异常安全性,掌握异常处理的基本方法,并遵循最佳实践,可以提高程序的稳定性和可靠性,更好地应对运行时错误和异常情况。
END_OF_CHAPTER
4. chapter 4: folly::Vector 高级特性与性能优化
4.1 内存分配策略与性能考量 (Memory Allocation Strategies and Performance Considerations)
folly::Vector
作为高性能的动态数组容器,其内存分配策略直接关系到程序的性能表现。理解其背后的机制,能够帮助我们更好地优化代码,避免潜在的性能瓶颈。本节将深入探讨 folly::Vector
的内存分配策略,并分析其对性能的影响。
① 动态内存分配 (Dynamic Memory Allocation) 的本质
folly::Vector
,如同 std::vector
,是一种动态数组,这意味着它在运行时根据需要分配和释放内存。与静态数组在编译时固定大小不同,动态数组可以灵活地调整大小以适应数据量的变化。这种灵活性是通过堆内存 (heap memory) 的动态分配来实现的。
② folly::Vector
的内存增长策略
当向 folly::Vector
中添加元素,而当前分配的内存空间不足时,folly::Vector
会自动进行内存重新分配。这种重新分配通常遵循以下步骤:
⚝ 分配更大的内存块 (Allocate a larger memory block):folly::Vector
会请求分配一块更大的内存空间,通常是当前容量 (capacity) 的倍数增长。常见的增长因子是 1.5 或 2,具体实现可能有所不同。
⚝ 数据拷贝 (Data Copying):将原有内存块中的所有元素拷贝到新分配的内存块中。这是一个开销较大的操作,特别是当向量 (Vector) 存储大量元素时。
⚝ 释放旧内存 (Release old memory):释放之前分配的内存块。
③ 内存分配策略对性能的影响
动态内存分配虽然提供了灵活性,但也引入了性能开销。频繁的内存重新分配和数据拷贝是性能损耗的主要来源。
⚝ 时间开销 (Time Overhead):每次内存重新分配都需要时间来寻找合适的内存块、进行数据拷贝和释放旧内存。当向量 (Vector) 频繁增长时,这些时间开销会累积,影响程序的整体性能。
⚝ 空间碎片 (Memory Fragmentation):频繁的内存分配和释放可能导致内存碎片,即堆内存中存在许多小的、不连续的空闲块,难以满足大块内存的分配请求,即使总的空闲内存足够。虽然现代内存分配器 (memory allocator) 已经尽可能地减少碎片,但在某些高负载场景下,碎片仍然可能成为问题。
④ folly::Vector
的优势与考量
folly::Vector
在内存分配策略上,通常会进行一些优化,例如:
⚝ 更高效的内存分配器 (More efficient memory allocator):folly
库可能会使用自定义的内存分配器,例如 jemalloc 或 tcmalloc,这些分配器在某些场景下比标准库的分配器更高效,能够减少内存分配和释放的开销,并降低碎片产生的可能性。
⚝ 容量预留 (Capacity Reservation):folly::Vector
提供了 reserve()
方法,允许用户预先分配足够的内存空间,从而减少甚至避免后续的内存重新分配。这是一种重要的性能优化手段,将在 4.2 节详细讨论。
⑤ 性能考量总结
理解 folly::Vector
的内存分配策略,关键在于认识到动态内存分配的潜在性能开销。为了优化性能,我们需要:
⚝ 减少内存重新分配的次数:通过预分配足够的容量 (capacity) 来避免频繁的内存增长。
⚝ 选择合适的内存分配器:在性能敏感的应用中,可以考虑使用更高效的内存分配器。
⚝ 避免不必要的拷贝:使用移动语义 (move semantics) 来减少数据拷贝的开销,这将在 3.3 节详细介绍。
通过合理的内存管理策略,我们可以充分发挥 folly::Vector
的性能优势,构建高效稳定的应用程序。
4.2 预分配 (Pre-allocation) 与容量规划 (Capacity Planning)
为了优化 folly::Vector
的性能,尤其是在处理大量数据或频繁操作的场景下,预分配 (Pre-allocation) 和 容量规划 (Capacity Planning) 是至关重要的技术。本节将深入探讨这两种方法,并提供实用的指导。
① 预分配 (Pre-allocation) 的概念与作用
预分配是指在向 folly::Vector
添加元素之前,预先为其分配足够的内存空间。folly::Vector
提供了 reserve(size_type n)
方法来实现预分配,其中 n
指定了预期的容量 (capacity)。
作用:
⚝ 减少内存重新分配 (Reduce Reallocations):预分配可以显著减少甚至消除因容量不足而导致的内存重新分配和数据拷贝操作,从而提高性能。
⚝ 提高效率 (Improve Efficiency):避免了频繁的内存操作,程序运行效率更高,尤其是在循环中大量添加元素时效果更明显。
示例代码:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | // 预分配 1000 个元素的空间 |
6 | vec.reserve(1000); |
7 | // 添加 1000 个元素,不会发生多次重新分配 |
8 | for (int i = 0; i < 1000; ++i) { |
9 | vec.push_back(i); |
10 | } |
11 | std::cout << "Vector size: " << vec.size() << std::endl; |
12 | std::cout << "Vector capacity: " << vec.capacity() << std::endl; |
13 | return 0; |
14 | } |
在这个例子中,vec.reserve(1000)
预先分配了能容纳 1000 个 int
元素的空间。后续的 push_back
操作可以直接在已分配的内存中进行,避免了多次内存重新分配。
② 容量规划 (Capacity Planning) 的重要性
容量规划是指在程序设计阶段,根据应用场景和数据规模,合理估算 folly::Vector
所需的最大容量,并进行预分配。
重要性:
⚝ 性能优化 (Performance Optimization):合理的容量规划是性能优化的基础。过小的预分配量仍然可能导致重新分配,而过大的预分配量则可能浪费内存。
⚝ 资源管理 (Resource Management):准确的容量规划有助于更好地管理内存资源,避免内存浪费或内存不足的风险。
③ 容量规划的方法与技巧
进行容量规划需要综合考虑以下因素:
⚝ 数据规模预估 (Data Size Estimation):根据应用场景,预估 folly::Vector
可能存储的最大元素数量。例如,在处理网络请求时,可以根据请求量和数据包大小来估算。
⚝ 增长趋势分析 (Growth Trend Analysis):如果数据规模是动态变化的,需要分析其增长趋势。例如,如果数据量呈线性增长,可以预留一定的增长空间。
⚝ 经验值与测试 (Empirical Values and Testing):在实际开发中,可以根据经验值或通过性能测试来确定最佳的预分配容量。
实用技巧:
⚝ 保守估计,适度预留 (Conservative Estimation with Moderate Reservation):在不确定数据规模的情况下,可以进行保守估计,并适度预留一些额外的空间,以应对突发的数据增长。
⚝ 分阶段预分配 (Phased Pre-allocation):对于数据规模分阶段增长的应用,可以考虑分阶段进行预分配。例如,先预分配一个初始容量,当容量不足时,再进行扩容。
⚝ 使用 shrink_to_fit()
释放多余容量 (Release Excess Capacity with shrink_to_fit()
):如果 folly::Vector
的容量远大于实际元素数量,可以使用 shrink_to_fit()
方法来释放多余的内存空间,降低内存占用。但需要注意,shrink_to_fit()
可能会导致重新分配,因此应谨慎使用。
④ 预分配与容量规划的最佳实践
⚝ 在循环前预分配 (Pre-allocate before Loops):如果需要在循环中向 folly::Vector
添加大量元素,务必在循环开始前进行预分配。
⚝ 根据实际场景选择合适的预分配量 (Choose Appropriate Pre-allocation Size based on Scenarios):预分配量应根据实际应用场景和数据规模来确定,避免过度预分配或预分配不足。
⚝ 结合性能测试进行调优 (Optimize with Performance Testing):通过性能测试来验证容量规划的合理性,并根据测试结果进行调优。
合理的预分配和容量规划是提升 folly::Vector
性能的关键步骤。通过精心的设计和实践,我们可以充分利用 folly::Vector
的优势,构建高效的应用系统。
4.3 向量 (Vector) 的拷贝与赋值:深拷贝与浅拷贝 (Copy and Assignment of Vector: Deep Copy and Shallow Copy)
在 C++ 中,对象的拷贝和赋值是基本操作。对于容器 folly::Vector
而言,理解 深拷贝 (Deep Copy) 和 浅拷贝 (Shallow Copy) 的区别至关重要,这关系到数据的正确性和程序的健壮性。本节将深入解析 folly::Vector
的拷贝与赋值行为,并探讨深拷贝与浅拷贝的应用场景。
① 浅拷贝 (Shallow Copy) 的概念
浅拷贝是指在对象拷贝或赋值时,只复制对象本身的数据成员的值,而不复制对象所管理的资源。对于 folly::Vector
而言,浅拷贝意味着只复制向量 (Vector) 的大小 (size)、容量 (capacity) 以及指向底层数据数组的指针,而不会复制底层数组中的元素。
特点:
⚝ 共享资源 (Shared Resources):拷贝后的对象与原始对象共享同一份底层数据。
⚝ 效率高 (High Efficiency):由于只复制少量数据成员,浅拷贝速度很快。
⚝ 潜在风险 (Potential Risks):当原始对象或拷贝对象之一修改底层数据时,会影响到另一个对象,可能导致数据错误或悬挂指针 (dangling pointer) 等问题。
folly::Vector
的默认拷贝与赋值是浅拷贝。
示例代码:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {1, 2, 3}; |
5 | folly::Vector<int> vec2 = vec1; // 浅拷贝 |
6 | std::cout << "vec1 data address: " << vec1.data() << std::endl; |
7 | std::cout << "vec2 data address: " << vec2.data() << std::endl; |
8 | vec2[0] = 100; // 修改 vec2 的元素 |
9 | std::cout << "vec1[0]: " << vec1[0] << std::endl; // vec1[0] 也被修改了,因为共享数据 |
10 | std::cout << "vec2[0]: " << vec2[0] << std::endl; |
11 | return 0; |
12 | } |
在这个例子中,vec2 = vec1
执行的是浅拷贝。vec1
和 vec2
指向同一块内存区域。修改 vec2
的元素,vec1
的元素也会受到影响。
② 深拷贝 (Deep Copy) 的概念
深拷贝是指在对象拷贝或赋值时,不仅复制对象本身的数据成员的值,还会复制对象所管理的资源。对于 folly::Vector
而言,深拷贝意味着不仅复制向量 (Vector) 的大小、容量和指针,还会创建一个新的底层数据数组,并将原始向量 (Vector) 中的所有元素复制到新的数组中。
特点:
⚝ 独立资源 (Independent Resources):拷贝后的对象拥有独立的底层数据,与原始对象互不影响。
⚝ 效率相对较低 (Relatively Lower Efficiency):由于需要复制所有元素,深拷贝速度相对较慢,特别是当向量 (Vector) 存储大量元素或复杂对象时。
⚝ 数据安全 (Data Safety):深拷贝保证了数据独立性,避免了浅拷贝可能导致的数据共享和修改问题。
③ 如何实现 folly::Vector
的深拷贝
folly::Vector
默认提供的是浅拷贝。如果需要深拷贝,通常需要手动实现,或者使用一些辅助方法。
方法一:手动拷贝元素
1 | folly::Vector<int> vec1 = {1, 2, 3}; |
2 | folly::Vector<int> vec2; |
3 | vec2.reserve(vec1.size()); // 预分配空间,提高效率 |
4 | for (const auto& elem : vec1) { |
5 | vec2.push_back(elem); // 逐个元素拷贝 |
6 | } |
方法二:使用拷贝构造函数 (Copy Constructor) 或拷贝赋值运算符 (Copy Assignment Operator) (对于自定义类型)
如果 folly::Vector
存储的是自定义类型的对象,且该类型提供了深拷贝的拷贝构造函数或拷贝赋值运算符,那么 folly::Vector
的拷贝和赋值操作也会自动进行深拷贝。
示例代码 (自定义类型深拷贝):
1 | |
2 | |
3 | class MyClass { |
4 | public: |
5 | int* data; |
6 | MyClass(int val) : data(new int(val)) {} |
7 | // 深拷贝构造函数 |
8 | MyClass(const MyClass& other) : data(new int(*other.data)) { |
9 | std::cout << "Deep copy constructor called" << std::endl; |
10 | } |
11 | // 深拷贝赋值运算符 |
12 | MyClass& operator=(const MyClass& other) { |
13 | if (this != &other) { |
14 | delete data; |
15 | data = new int(*other.data); |
16 | std::cout << "Deep copy assignment operator called" << std::endl; |
17 | } |
18 | return *this; |
19 | } |
20 | ~MyClass() { delete data; } |
21 | }; |
22 | int main() { |
23 | folly::Vector<MyClass> vec1; |
24 | vec1.emplace_back(1); |
25 | vec1.emplace_back(2); |
26 | folly::Vector<MyClass> vec2 = vec1; // 调用深拷贝构造函数 |
27 | folly::Vector<MyClass> vec3; |
28 | vec3 = vec1; // 调用深拷贝赋值运算符 |
29 | *vec2[0].data = 100; // 修改 vec2 的数据,不影响 vec1 |
30 | std::cout << "*vec1[0].data: " << *vec1[0].data << std::endl; |
31 | std::cout << "*vec2[0].data: " << *vec2[0].data << std::endl; |
32 | return 0; |
33 | } |
在这个例子中,MyClass
提供了深拷贝构造函数和赋值运算符。当 folly::Vector<MyClass>
进行拷贝和赋值时,会自动调用 MyClass
的深拷贝操作,实现 folly::Vector
的深拷贝。
④ 深拷贝与浅拷贝的应用场景
⚝ 浅拷贝的应用场景:
▮▮▮▮⚝ 临时拷贝 (Temporary Copy):当只需要临时使用向量 (Vector) 的数据,且不希望修改原始数据时,可以使用浅拷贝。
▮▮▮▮⚝ 只读访问 (Read-only Access):当多个对象需要共享同一份数据,且都只进行只读访问时,可以使用浅拷贝。
▮▮▮▮⚝ 性能敏感场景 (Performance-sensitive Scenarios):浅拷贝效率高,在性能要求较高的场景中可以优先考虑,但需要仔细评估潜在的风险。
⚝ 深拷贝的应用场景:
▮▮▮▮⚝ 数据隔离 (Data Isolation):当需要保证拷贝后的对象与原始对象的数据完全独立,互不影响时,必须使用深拷贝。
▮▮▮▮⚝ 持久化存储 (Persistent Storage):在将向量 (Vector) 数据持久化存储时,通常需要进行深拷贝,以确保数据的完整性和独立性。
▮▮▮▮⚝ 多线程编程 (Multi-threaded Programming):在多线程环境下,为了避免数据竞争和数据污染,通常需要对共享的向量 (Vector) 进行深拷贝。
⑤ 总结与最佳实践
理解 folly::Vector
的拷贝与赋值行为,并根据实际应用场景选择合适的拷贝方式,是编写安全、高效 C++ 代码的关键。
⚝ 默认情况下,folly::Vector
提供浅拷贝。
⚝ 需要深拷贝时,需要手动实现或依赖自定义类型的深拷贝支持。
⚝ 在选择拷贝方式时,需要权衡性能和数据安全的需求。
⚝ 对于存储复杂对象或需要数据隔离的场景,优先考虑深拷贝。
⚝ 在性能敏感且数据共享风险可控的场景,可以考虑浅拷贝。
4.4 多维向量 (Multi-dimensional Vector) 的实现与应用 (Implementation and Application of Multi-dimensional Vector)
folly::Vector
主要用于表示一维动态数组。然而,在许多应用场景中,我们需要处理多维数据,例如矩阵、图像、三维模型等。本节将介绍如何使用 folly::Vector
来实现 多维向量 (Multi-dimensional Vector),并探讨其应用。
① 二维向量 (Two-dimensional Vector) 的实现
二维向量,也称为矩阵,可以看作是向量 (Vector) 的向量 (Vector)。即,一个 folly::Vector
,其元素类型也是 folly::Vector
。
声明与初始化:
1 | folly::Vector<folly::Vector<int>> matrix; // 声明一个二维向量 |
2 | // 初始化一个 3x4 的二维向量,所有元素初始化为 0 |
3 | folly::Vector<folly::Vector<int>> matrix(3, folly::Vector<int>(4, 0)); |
访问元素:
使用双重下标访问二维向量的元素:matrix[row][col]
,其中 row
是行索引,col
是列索引。
示例代码:
1 | |
2 | |
3 | int main() { |
4 | // 初始化一个 2x3 的二维向量 |
5 | folly::Vector<folly::Vector<int>> matrix = { |
6 | {1, 2, 3}, |
7 | {4, 5, 6} |
8 | }; |
9 | // 遍历并打印二维向量 |
10 | for (size_t i = 0; i < matrix.size(); ++i) { |
11 | for (size_t j = 0; j < matrix[i].size(); ++j) { |
12 | std::cout << matrix[i][j] << " "; |
13 | } |
14 | std::cout << std::endl; |
15 | } |
16 | return 0; |
17 | } |
② 三维及更高维度向量的实现
类似地,可以扩展到三维、四维甚至更高维度的向量。例如,三维向量可以声明为 folly::Vector<folly::Vector<folly::Vector<int>>>
。
声明与初始化 (三维向量):
1 | folly::Vector<folly::Vector<folly::Vector<int>>> cube; // 声明一个三维向量 |
2 | // 初始化一个 2x3x4 的三维向量,所有元素初始化为 0 |
3 | folly::Vector<folly::Vector<folly::Vector<int>>> cube(2, folly::Vector<folly::Vector<int>>(3, folly::Vector<int>(4, 0))); |
访问元素 (三维向量):
使用三重下标访问三维向量的元素:cube[dim1][dim2][dim3]
。
③ 多维向量的应用场景
多维向量在各种领域都有广泛的应用:
⚝ 矩阵运算 (Matrix Operations):二维向量天然适合表示矩阵,可以用于实现线性代数中的各种矩阵运算,例如矩阵加法、矩阵乘法、矩阵转置等。
⚝ 图像处理 (Image Processing):图像可以看作是二维或三维数组,二维灰度图像可以用二维向量表示,三维彩色图像 (RGB) 可以用三维向量表示。图像处理算法,如滤波、边缘检测、特征提取等,都可以基于多维向量实现。
⚝ 游戏开发 (Game Development):游戏中的场景、模型、动画等数据通常以多维形式存储。例如,三维游戏场景可以用三维向量网格表示,模型可以用顶点坐标和三角形面片表示。
⚝ 科学计算 (Scientific Computing):科学计算中经常需要处理多维数据,例如有限元分析、流体动力学模拟、气候模型等。多维向量可以有效地存储和操作这些数据。
⚝ 数据分析 (Data Analysis):多维数据分析,例如多维数据透视、数据立方体 (data cube) 等,可以使用多维向量来组织和处理数据。
④ 多维向量的性能考量
使用 folly::Vector
实现多维向量,其性能与一维向量类似,主要受内存分配和数据访问的影响。
⚝ 内存分配 (Memory Allocation):多维向量的内存分配是分层进行的。例如,对于二维向量 folly::Vector<folly::Vector<int>> matrix
,首先分配外层向量的内存,然后为每个内层向量分配内存。这种分层分配可能导致内存不连续,影响缓存局部性 (cache locality)。
⚝ 数据访问 (Data Access):多维向量的数据访问需要多次下标运算,相对于一维向量,访问效率略有降低。
性能优化建议:
⚝ 连续内存布局 (Contiguous Memory Layout):对于性能敏感的应用,可以考虑使用一维向量模拟多维数组,并手动计算索引,以实现连续内存布局,提高缓存命中率。例如,对于matrix[i][j]
的索引为
⚝ 预分配 (Pre-allocation):与一维向量类似,多维向量也应尽可能进行预分配,减少内存重新分配的开销。
⑤ 总结与最佳实践
folly::Vector
可以灵活地用于实现多维向量,满足各种应用场景的需求。
⚝ 使用 folly::Vector<folly::Vector<...>>
嵌套结构可以方便地实现多维向量。
⚝ 多维向量在矩阵运算、图像处理、游戏开发、科学计算等领域有广泛应用。
⚝ 需要关注多维向量的内存分配和数据访问性能,并根据实际情况进行优化。
⚝ 对于性能敏感的应用,可以考虑使用一维向量模拟多维数组,以获得更好的性能。
4.5 folly::Vector 与算法 (Algorithm) 的结合应用 (Combined Application of folly::Vector and Algorithm)
folly::Vector
作为一种常用的容器,经常需要与各种算法结合使用,以完成复杂的数据处理任务。C++ 标准库 <algorithm>
头文件提供了丰富的通用算法,可以方便地应用于 folly::Vector
。本节将介绍 folly::Vector
与常用算法的结合应用,并展示一些实战代码示例。
① 常用算法概述
<algorithm>
头文件提供的算法可以大致分为以下几类:
⚝ 非修改性序列操作 (Non-modifying sequence operations):这类算法不修改序列中的元素,例如 for_each
(遍历)、find
(查找)、count
(计数)、equal
(比较)、mismatch
(不匹配) 等。
⚝ 修改性序列操作 (Modifying sequence operations):这类算法会修改序列中的元素,例如 copy
(拷贝)、move
(移动)、transform
(转换)、fill
(填充)、replace
(替换)、remove
(移除)、unique
(去重) 等。
⚝ 排序算法 (Sorting algorithms):这类算法用于对序列进行排序,例如 sort
(排序)、stable_sort
(稳定排序)、partial_sort
(部分排序)、nth_element
(第 n 个元素) 等。
⚝ 搜索算法 (Searching algorithms):这类算法用于在有序序列中查找元素,例如 binary_search
(二分查找)、lower_bound
(下界)、upper_bound
(上界)、equal_range
(相等范围) 等。
⚝ 数值算法 (Numeric algorithms):这类算法用于进行数值计算,例如 accumulate
(累加)、inner_product
(内积)、adjacent_difference
(相邻差分)、partial_sum
(部分和) 等 (通常在 <numeric>
头文件中)。
② folly::Vector
与算法的结合使用
<algorithm>
中的算法通常通过迭代器 (iterator) 来操作容器中的元素。folly::Vector
提供了迭代器,因此可以与 <algorithm>
中的大多数算法无缝结合。
基本用法:
大多数算法的函数签名类似如下形式:
1 | template<typename InputIterator, typename ...> |
2 | algorithm_name(InputIterator first, InputIterator last, ...); |
其中 first
和 last
是迭代器,表示要操作的序列范围,通常使用 folly::Vector
的 begin()
和 end()
方法获取迭代器。
示例代码 (使用 std::sort
排序):
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {5, 2, 8, 1, 9, 4}; |
6 | std::sort(vec.begin(), vec.end()); // 使用 std::sort 排序 |
7 | std::cout << "Sorted vector: "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
示例代码 (使用 std::find
查找元素):
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {5, 2, 8, 1, 9, 4}; |
6 | auto it = std::find(vec.begin(), vec.end(), 8); // 查找元素 8 |
7 | if (it != vec.end()) { |
8 | std::cout << "Element 8 found at index: " << std::distance(vec.begin(), it) << std::endl; |
9 | } else { |
10 | std::cout << "Element 8 not found" << std::endl; |
11 | } |
12 | return 0; |
13 | } |
示例代码 (使用 std::transform
转换元素):
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec1 = {1, 2, 3, 4, 5}; |
6 | folly::Vector<int> vec2(vec1.size()); // 目标向量预分配空间 |
7 | // 将 vec1 的元素平方后存入 vec2 |
8 | std::transform(vec1.begin(), vec1.end(), vec2.begin(), [](int x){ return x * x; }); |
9 | std::cout << "Transformed vector: "; |
10 | for (int val : vec2) { |
11 | std::cout << val << " "; |
12 | } |
13 | std::cout << std::endl; |
14 | return 0; |
15 | } |
③ 算法的性能考量
算法的性能通常取决于算法本身的时间复杂度以及容器的数据访问效率。对于 folly::Vector
,由于其底层是连续内存数组,数据访问效率较高,因此与算法结合使用时,通常能够获得较好的性能。
性能优化建议:
⚝ 选择合适的算法 (Choose Appropriate Algorithms):根据实际需求选择时间复杂度较低的算法。例如,在有序序列中查找元素,应使用 binary_search
等二分查找算法,而不是 find
等线性查找算法。
⚝ 避免不必要的数据拷贝 (Avoid Unnecessary Data Copies):一些算法可能需要拷贝容器中的元素。在性能敏感的场景中,应尽量选择避免数据拷贝的算法,或者使用移动语义 (move semantics) 来减少拷贝开销。
⚝ 利用并行算法 (Utilize Parallel Algorithms):C++17 标准引入了并行算法,可以利用多核处理器提高算法的执行效率。folly
库也提供了一些并行算法的实现,可以考虑在合适的场景下使用。
④ folly::Vector
与 Lambda 表达式
C++ Lambda 表达式可以方便地与算法结合使用,自定义算法的操作逻辑。例如,在 std::transform
示例中,我们使用 Lambda 表达式 [](int x){ return x * x; }
定义了元素转换的规则。
Lambda 表达式的优点:
⚝ 简洁 (Concise):Lambda 表达式可以简洁地定义函数对象,避免了编写独立的函数或函数对象类的繁琐。
⚝ 灵活 (Flexible):Lambda 表达式可以捕获 (capture) 上下文中的变量,使其能够访问外部数据,更加灵活。
⚝ 内联 (Inline):Lambda 表达式通常会被编译器内联 (inline),提高执行效率。
⑤ 总结与最佳实践
folly::Vector
与 <algorithm>
提供的算法结合使用,可以高效地完成各种数据处理任务。
⚝ folly::Vector
可以与 <algorithm>
中的大多数算法无缝结合。
⚝ 合理选择算法,并结合 Lambda 表达式,可以编写简洁、高效的代码。
⚝ 在性能敏感的场景中,需要关注算法的时间复杂度、数据拷贝开销以及并行化可能性。
⚝ 熟练掌握常用算法,并灵活运用 Lambda 表达式,是提升 C++ 编程能力的重要方面。
END_OF_CHAPTER
5. chapter 5: folly::Vector API 全面解析
5.1 构造函数 (Constructor) 与析构函数 (Destructor) 详解
folly::Vector
提供了多种构造函数,以支持在不同场景下创建向量 (Vector) 对象。本节将详细介绍这些构造函数以及析构函数 (Destructor) 的作用。
5.1.1 构造函数 (Constructor) 详解
folly::Vector
的构造函数允许用户以多种方式初始化向量 (Vector)。以下是常用的构造函数及其详细说明:
① 默认构造函数 (Default Constructor)
1 | folly::Vector<T> vec; |
⚝ 作用:创建一个空的 folly::Vector
对象,不包含任何元素。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Initial size: " << vec.size() << std::endl; // 输出:Initial size: 0 |
6 | return 0; |
7 | } |
② 填充构造函数 (Fill Constructor)
1 | folly::Vector<T> vec(size_type count, const T& value); |
⚝ 作用:创建一个包含 count
个元素,每个元素的值均为 value
的 folly::Vector
对象。
⚝ 参数:
▮▮▮▮⚝ count
: 指定向量 (Vector) 中元素的数量。
▮▮▮▮⚝ value
: 指定每个元素的初始值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec(5, 100); // 创建包含 5 个值为 100 的元素的向量 |
5 | std::cout << "Size: " << vec.size() << std::endl; // 输出:Size: 5 |
6 | for (int val : vec) { |
7 | std::cout << val << " "; // 输出:100 100 100 100 100 |
8 | } |
9 | std::cout << std::endl; |
10 | return 0; |
11 | } |
③ 范围构造函数 (Range Constructor)
1 | template <class InputIterator> |
2 | folly::Vector<T> vec(InputIterator first, InputIterator last); |
⚝ 作用:通过迭代器指定的范围 [first, last)
内的元素,创建一个新的 folly::Vector
对象。
⚝ 参数:
▮▮▮▮⚝ first
: 指向范围起始位置的输入迭代器。
▮▮▮▮⚝ last
: 指向范围结束位置的输入迭代器。
⚝ 示例:
1 | |
2 | |
3 | |
4 | int main() { |
5 | std::vector<int> stdVec = {1, 2, 3, 4, 5}; |
6 | folly::Vector<int> follyVec(stdVec.begin(), stdVec.end()); // 从 std::vector 创建 folly::Vector |
7 | std::cout << "Folly Vector elements: "; |
8 | for (int val : follyVec) { |
9 | std::cout << val << " "; // 输出:Folly Vector elements: 1 2 3 4 5 |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
④ 拷贝构造函数 (Copy Constructor)
1 | folly::Vector<T> vec(const folly::Vector& other); |
⚝ 作用:创建一个新的 folly::Vector
对象,作为现有 folly::Vector
对象 other
的副本。新向量 (Vector) 包含与 other
相同的元素。
⚝ 参数:
▮▮▮▮⚝ other
: 要复制的 folly::Vector
对象。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {1, 2, 3}; |
5 | folly::Vector<int> vec2 = vec1; // 使用拷贝构造函数 |
6 | std::cout << "vec2 elements: "; |
7 | for (int val : vec2) { |
8 | std::cout << val << " "; // 输出:vec2 elements: 1 2 3 |
9 | } |
10 | std::cout << std::endl; |
11 | return 0; |
12 | } |
⑤ 移动构造函数 (Move Constructor)
1 | folly::Vector<T> vec(folly::Vector&& other) noexcept; |
⚝ 作用:创建一个新的 folly::Vector
对象,通过移动语义获取现有 folly::Vector
对象 other
的资源。移动构造函数通常比拷贝构造函数更高效,因为它避免了深拷贝,而是直接转移了所有权。
⚝ 参数:
▮▮▮▮⚝ other
: 要移动的 folly::Vector
对象(右值引用)。
⚝ 示例:
1 | |
2 | |
3 | folly::Vector<int> createVector() { |
4 | folly::Vector<int> tempVec = {1, 2, 3, 4, 5}; |
5 | return tempVec; // 返回临时对象,触发移动构造 |
6 | } |
7 | int main() { |
8 | folly::Vector<int> vec = createVector(); // 使用移动构造函数 |
9 | std::cout << "vec elements after move: "; |
10 | for (int val : vec) { |
11 | std::cout << val << " "; // 输出:vec elements after move: 1 2 3 4 5 |
12 | } |
13 | std::cout << std::endl; |
14 | return 0; |
15 | } |
⑥ 初始化列表构造函数 (Initializer List Constructor) (C++11 及以上)
1 | folly::Vector<T> vec(std::initializer_list<T> il); |
⚝ 作用:使用初始化列表直接初始化 folly::Vector
对象。
⚝ 参数:
▮▮▮▮⚝ il
: 初始化列表。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; // 使用初始化列表构造 |
5 | std::cout << "Initialized vector: "; |
6 | for (int val : vec) { |
7 | std::cout << val << " "; // 输出:Initialized vector: 10 20 30 40 |
8 | } |
9 | std::cout << std::endl; |
10 | return 0; |
11 | } |
5.1.2 析构函数 (Destructor) 详解
1 | ~Vector(); |
⚝ 作用:析构函数在 folly::Vector
对象的生命周期结束时自动调用,负责释放向量 (Vector) 占用的内存资源。对于 folly::Vector
来说,析构函数主要负责:
▮▮▮▮⚝ 释放动态分配的存储元素的内存。
▮▮▮▮⚝ 调用向量 (Vector) 中每个元素的析构函数(如果元素是类对象)。
⚝ 特点:
▮▮▮▮⚝ 析构函数是隐式调用的,无需手动调用。
▮▮▮▮⚝ folly::Vector
的析构函数确保了内存安全和资源清理,避免内存泄漏。
⚝ 示例(无需显式代码,析构函数自动执行):
1 | |
2 | |
3 | void testVectorScope() { |
4 | folly::Vector<int> vec = {1, 2, 3}; |
5 | std::cout << "Vector created in scope." << std::endl; |
6 | // 当 vec 离开作用域时,析构函数自动调用 |
7 | } // vec 的析构函数在此处被调用 |
8 | int main() { |
9 | testVectorScope(); |
10 | std::cout << "Vector out of scope, destructor called." << std::endl; |
11 | return 0; |
12 | } |
总结
folly::Vector
提供了丰富的构造函数,以满足不同初始化需求。理解这些构造函数的使用方法对于有效地创建和管理向量 (Vector) 对象至关重要。析构函数则保证了当向量 (Vector) 不再使用时,其占用的资源能够被正确释放,避免资源泄漏。
5.2 元素访问 (Element Access) 相关 API 详解
folly::Vector
提供了多种 API 用于访问向量 (Vector) 中的元素。这些 API 允许用户安全且高效地读取和修改向量 (Vector) 内的元素。本节将详细介绍这些元素访问相关的 API。
5.2.1 operator[] 运算符
1 | reference operator[](size_type pos); |
2 | const_reference operator[](size_type pos) const; |
⚝ 作用:通过下标 pos
访问向量 (Vector) 中指定位置的元素。返回元素的引用。
⚝ 参数:
▮▮▮▮⚝ pos
: 要访问元素的下标(索引),从 0 开始。
⚝ 返回值:
▮▮▮▮⚝ reference
: 返回位置 pos
处元素的可修改引用(用于非 const
向量)。
▮▮▮▮⚝ const_reference
: 返回位置 pos
处元素的常量引用(用于 const
向量)。
⚝ 重要: operator[]
不进行边界检查。如果 pos
超出有效范围,行为是未定义的 (Undefined Behavior),可能导致程序崩溃或数据损坏。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | std::cout << "Element at index 1: " << vec[1] << std::endl; // 输出:Element at index 1: 20 |
6 | vec[0] = 100; // 修改索引 0 的元素 |
7 | std::cout << "Modified element at index 0: " << vec[0] << std::endl; // 输出:Modified element at index 0: 100 |
8 | // 注意:以下代码可能导致未定义行为,因为索引超出了范围 |
9 | // std::cout << vec[3] << std::endl; // 潜在的越界访问 |
10 | return 0; |
11 | } |
5.2.2 at() 方法
1 | reference at(size_type pos); |
2 | const_reference at(size_type pos) const; |
⚝ 作用:通过下标 pos
访问向量 (Vector) 中指定位置的元素。返回元素的引用。
⚝ 参数:
▮▮▮▮⚝ pos
: 要访问元素的下标(索引),从 0 开始。
⚝ 返回值:
▮▮▮▮⚝ reference
: 返回位置 pos
处元素的可修改引用(用于非 const
向量)。
▮▮▮▮⚝ const_reference
: 返回位置 pos
处元素的常量引用(用于 const
向量)。
⚝ 重要: at()
方法进行边界检查。如果 pos
超出有效范围,会抛出 std::out_of_range
异常。这使得 at()
比 operator[]
更安全,但性能略低,因为需要进行边界检查。
⚝ 示例:
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {10, 20, 30}; |
6 | std::cout << "Element at index 2: " << vec.at(2) << std::endl; // 输出:Element at index 2: 30 |
7 | try { |
8 | std::cout << vec.at(3) << std::endl; // 尝试访问越界索引 |
9 | } catch (const std::out_of_range& e) { |
10 | std::cerr << "Out of range exception caught: " << e.what() << std::endl; // 输出:Out of range exception caught: vector::at: __n (which is 3) >= __sz (which is 3) |
11 | } |
12 | return 0; |
13 | } |
5.2.3 front() 方法
1 | reference front(); |
2 | const_reference front() const; |
⚝ 作用:访问向量 (Vector) 中的第一个元素。
⚝ 返回值:
▮▮▮▮⚝ reference
: 返回第一个元素的可修改引用(用于非 const
向量)。
▮▮▮▮⚝ const_reference
: 返回第一个元素的常量引用(用于 const
向量)。
⚝ 重要: 调用 front()
之前,需要确保向量 (Vector) 不为空。如果向量 (Vector) 为空,调用 front()
的行为是未定义的。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | std::cout << "First element: " << vec.front() << std::endl; // 输出:First element: 10 |
6 | vec.front() = 5; // 修改第一个元素 |
7 | std::cout << "Modified first element: " << vec.front() << std::endl; // 输出:Modified first element: 5 |
8 | folly::Vector<int> emptyVec; |
9 | // 注意:以下代码可能导致未定义行为,因为向量为空 |
10 | // std::cout << emptyVec.front() << std::endl; // 在空向量上调用 front() |
11 | return 0; |
12 | } |
5.2.4 back() 方法
1 | reference back(); |
2 | const_reference back() const; |
⚝ 作用:访问向量 (Vector) 中的最后一个元素。
⚝ 返回值:
▮▮▮▮⚝ reference
: 返回最后一个元素的可修改引用(用于非 const
向量)。
▮▮▮▮⚝ const_reference
: 返回最后一个元素的常量引用(用于 const
向量)。
⚝ 重要: 调用 back()
之前,需要确保向量 (Vector) 不为空。如果向量 (Vector) 为空,调用 back()
的行为是未定义的。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | std::cout << "Last element: " << vec.back() << std::endl; // 输出:Last element: 30 |
6 | vec.back() = 300; // 修改最后一个元素 |
7 | std::cout << "Modified last element: " << vec.back() << std::endl; // 输出:Modified last element: 300 |
8 | folly::Vector<int> emptyVec; |
9 | // 注意:以下代码可能导致未定义行为,因为向量为空 |
10 | // std::cout << emptyVec.back() << std::endl; // 在空向量上调用 back() |
11 | return 0; |
12 | } |
5.2.5 data() 方法
1 | pointer data() noexcept; |
2 | const_pointer data() const noexcept; |
⚝ 作用:返回指向向量 (Vector) 内部用于存储元素的首元素的指针。如果向量 (Vector) 为空,则返回的指针可能是空指针,或者不应该被解引用。
⚝ 返回值:
▮▮▮▮⚝ pointer
: 指向首元素的裸指针(用于非 const
向量)。
▮▮▮▮⚝ const_pointer
: 指向首元素的常量裸指针(用于 const
向量)。
⚝ 应用场景: data()
方法主要用于需要直接访问底层数组的场景,例如与 C 风格的 API 交互,或者进行一些底层的内存操作。
⚝ 重要: 通过 data()
返回的指针访问元素时,需要自行负责边界检查。修改通过 data()
获取的内存可能会影响向量 (Vector) 的状态,需要谨慎使用。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | int* ptr = vec.data(); |
6 | std::cout << "First element via data(): " << *ptr << std::endl; // 输出:First element via data(): 10 |
7 | std::cout << "Second element via data(): " << *(ptr + 1) << std::endl; // 输出:Second element via data(): 20 |
8 | *ptr = 1000; // 修改第一个元素 |
9 | std::cout << "Modified first element via data(): " << vec[0] << std::endl; // 输出:Modified first element via data(): 1000 |
10 | folly::Vector<int> emptyVec; |
11 | int* emptyPtr = emptyVec.data(); |
12 | // 注意:对于空向量,返回的指针不应被解引用 |
13 | // std::cout << *emptyPtr << std::endl; // 潜在的错误,空指针解引用 |
14 | return 0; |
15 | } |
总结
folly::Vector
提供了多种元素访问 API,用户可以根据不同的需求和安全级别选择合适的 API。operator[]
快速但不安全,at()
安全但略慢,front()
和 back()
用于访问首尾元素,而 data()
则提供了底层数组的直接访问方式。在实际使用中,应根据具体情况权衡性能和安全性,选择最合适的元素访问方法。
5.3 修改器 (Modifier) 相关 API 详解
folly::Vector
提供了一系列修改器 (Modifier) API,用于向向量 (Vector) 中添加、删除、修改元素,以及改变向量 (Vector) 的结构。本节将详细介绍这些修改器 API。
5.3.1 push_back() 方法
1 | void push_back(const T& value); |
2 | void push_back(T&& value); |
⚝ 作用:在向量 (Vector) 的末尾添加一个新元素。提供了两个重载版本:
▮▮▮▮⚝ push_back(const T& value)
: 拷贝插入,将 value
拷贝到向量末尾。
▮▮▮▮⚝ push_back(T&& value)
: 移动插入,将 value
移动到向量末尾(如果 T
支持移动语义)。
⚝ 参数:
▮▮▮▮⚝ value
: 要添加到向量 (Vector) 末尾的元素值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | vec.push_back(10); // 拷贝插入 |
6 | vec.push_back(20); |
7 | vec.push_back(30); |
8 | std::cout << "Vector elements after push_back: "; |
9 | for (int val : vec) { |
10 | std::cout << val << " "; // 输出:Vector elements after push_back: 10 20 30 |
11 | } |
12 | std::cout << std::endl; |
13 | return 0; |
14 | } |
5.3.2 emplace_back() 方法
1 | template <class... Args> |
2 | void emplace_back(Args&&... args); |
⚝ 作用:在向量 (Vector) 的末尾就地构造一个新元素。与 push_back()
的区别在于,emplace_back()
直接在向量 (Vector) 内部构造元素,避免了额外的拷贝或移动操作,通常更高效,尤其是在元素类型是复杂对象时。
⚝ 参数:
▮▮▮▮⚝ args...
: 用于构造新元素的参数,会被完美转发 (perfect forwarding) 到元素类型的构造函数。
⚝ 示例:
1 | |
2 | |
3 | class MyClass { |
4 | public: |
5 | MyClass(int val) : value(val) { |
6 | std::cout << "MyClass constructor called for value: " << value << std::endl; |
7 | } |
8 | int value; |
9 | }; |
10 | int main() { |
11 | folly::Vector<MyClass> vec; |
12 | vec.emplace_back(10); // 就地构造 MyClass 对象,输出:MyClass constructor called for value: 10 |
13 | vec.emplace_back(20); // 就地构造 MyClass 对象,输出:MyClass constructor called for value: 20 |
14 | std::cout << "Vector elements (values): "; |
15 | for (const auto& obj : vec) { |
16 | std::cout << obj.value << " "; // 输出:Vector elements (values): 10 20 |
17 | } |
18 | std::cout << std::endl; |
19 | return 0; |
20 | } |
5.3.3 pop_back() 方法
1 | void pop_back(); |
⚝ 作用:移除向量 (Vector) 的最后一个元素。
⚝ 重要: 调用 pop_back()
之前,需要确保向量 (Vector) 不为空。如果向量 (Vector) 为空,调用 pop_back()
的行为是未定义的。pop_back()
只移除元素,不返回被移除元素的值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | vec.pop_back(); // 移除最后一个元素 (30) |
6 | std::cout << "Vector elements after pop_back: "; |
7 | for (int val : vec) { |
8 | std::cout << val << " "; // 输出:Vector elements after pop_back: 10 20 |
9 | } |
10 | std::cout << std::endl; |
11 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:Vector size: 2 |
12 | return 0; |
13 | } |
5.3.4 insert() 方法
folly::Vector
提供了多个重载版本的 insert()
方法,用于在向量 (Vector) 的指定位置插入新元素。
① 单元素插入 (Single Element Insertion)
1 | iterator insert(const_iterator pos, const T& value); |
2 | iterator insert(const_iterator pos, T&& value); |
⚝ 作用:在迭代器 pos
指向的位置之前插入一个新元素 value
。返回指向新插入元素的迭代器。提供了拷贝插入和移动插入两个版本。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指定插入位置。元素将插入到 pos
指向的位置之前。
▮▮▮▮⚝ value
: 要插入的元素值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 30, 40}; |
5 | auto it = vec.begin() + 1; // 指向 30 的迭代器 |
6 | vec.insert(it, 20); // 在 30 之前插入 20 |
7 | std::cout << "Vector elements after insert: "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; // 输出:Vector elements after insert: 10 20 30 40 |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
② 多元素填充插入 (Fill Insertion)
1 | iterator insert(const_iterator pos, size_type count, const T& value); |
⚝ 作用:在迭代器 pos
指向的位置之前插入 count
个值为 value
的新元素。返回指向第一个新插入元素的迭代器。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指定插入位置。
▮▮▮▮⚝ count
: 要插入的元素数量。
▮▮▮▮⚝ value
: 要插入的元素值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 40}; |
5 | auto it = vec.begin() + 1; // 指向 40 的迭代器 |
6 | vec.insert(it, 2, 20); // 在 40 之前插入 2 个 20 |
7 | std::cout << "Vector elements after fill insert: "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; // 输出:Vector elements after fill insert: 10 20 20 40 |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
③ 范围插入 (Range Insertion)
1 | template <class InputIterator> |
2 | iterator insert(const_iterator pos, InputIterator first, InputIterator last); |
⚝ 作用:在迭代器 pos
指向的位置之前插入由迭代器范围 [first, last)
指定的元素。返回指向第一个新插入元素的迭代器。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指定插入位置。
▮▮▮▮⚝ first
: 指向要插入元素范围的起始迭代器。
▮▮▮▮⚝ last
: 指向要插入元素范围的结束迭代器。
⚝ 示例:
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {10, 40}; |
6 | std::vector<int> valuesToInsert = {20, 30}; |
7 | auto it = vec.begin() + 1; // 指向 40 的迭代器 |
8 | vec.insert(it, valuesToInsert.begin(), valuesToInsert.end()); // 插入范围 [20, 30) |
9 | std::cout << "Vector elements after range insert: "; |
10 | for (int val : vec) { |
11 | std::cout << val << " "; // 输出:Vector elements after range insert: 10 20 30 40 |
12 | } |
13 | std::cout << std::endl; |
14 | return 0; |
15 | } |
④ 初始化列表插入 (Initializer List Insertion) (C++11 及以上)
1 | iterator insert(const_iterator pos, std::initializer_list<T> il); |
⚝ 作用:在迭代器 pos
指向的位置之前插入初始化列表 il
中的元素。返回指向第一个新插入元素的迭代器。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指定插入位置。
▮▮▮▮⚝ il
: 要插入的初始化列表。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 40}; |
5 | auto it = vec.begin() + 1; // 指向 40 的迭代器 |
6 | vec.insert(it, {20, 30}); // 插入初始化列表 {20, 30} |
7 | std::cout << "Vector elements after initializer list insert: "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; // 输出:Vector elements after initializer list insert: 10 20 30 40 |
10 | } |
11 | std::cout << std::endl; |
12 | return 0; |
13 | } |
5.3.5 emplace() 方法
1 | template <class... Args> |
2 | iterator emplace(const_iterator pos, Args&&... args); |
⚝ 作用:在迭代器 pos
指向的位置之前就地构造一个新元素。类似于 insert()
,但与 emplace_back()
和 push_back()
的关系类似,emplace()
直接在指定位置构造元素,避免了拷贝或移动。返回指向新插入元素的迭代器。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指定插入位置。
▮▮▮▮⚝ args...
: 用于构造新元素的参数,会被完美转发到元素类型的构造函数。
⚝ 示例:
1 | |
2 | |
3 | class MyClass { |
4 | public: |
5 | MyClass(int val) : value(val) { |
6 | std::cout << "MyClass constructor called for value: " << value << std::endl; |
7 | } |
8 | int value; |
9 | }; |
10 | int main() { |
11 | folly::Vector<MyClass> vec; |
12 | vec.emplace_back(10); |
13 | vec.emplace_back(40); |
14 | auto it = vec.begin() + 1; // 指向 40 的迭代器 |
15 | vec.emplace(it, 20); // 在 40 之前就地构造 MyClass 对象,输出:MyClass constructor called for value: 20 |
16 | std::cout << "Vector elements (values) after emplace: "; |
17 | for (const auto& obj : vec) { |
18 | std::cout << obj.value << " "; // 输出:Vector elements (values) after emplace: 10 20 40 |
19 | } |
20 | std::cout << std::endl; |
21 | return 0; |
22 | } |
5.3.6 erase() 方法
folly::Vector
提供了两个重载版本的 erase()
方法,用于从向量 (Vector) 中删除元素。
① 删除单个元素 (Single Element Erase)
1 | iterator erase(const_iterator pos); |
⚝ 作用:删除迭代器 pos
指向的元素。返回指向被删除元素之后元素的迭代器,如果删除的是最后一个元素,则返回 end()
迭代器。
⚝ 参数:
▮▮▮▮⚝ pos
: 迭代器,指向要删除的元素。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; |
5 | auto it = vec.begin() + 1; // 指向 20 的迭代器 |
6 | it = vec.erase(it); // 删除 20,it 指向 30 |
7 | std::cout << "Vector elements after erase single element: "; |
8 | for (int val : vec) { |
9 | std::cout << val << " "; // 输出:Vector elements after erase single element: 10 30 40 |
10 | } |
11 | std::cout << std::endl; |
12 | std::cout << "Iterator it now points to: " << *it << std::endl; // 输出:Iterator it now points to: 30 |
13 | return 0; |
14 | } |
② 删除范围元素 (Range Erase)
1 | iterator erase(const_iterator first, const_iterator last); |
⚝ 作用:删除迭代器范围 [first, last)
内的所有元素。返回指向被删除范围之后元素的迭代器,如果删除的是末尾范围,则返回 end()
迭代器。
⚝ 参数:
▮▮▮▮⚝ first
: 指向要删除元素范围的起始迭代器。
▮▮▮▮⚝ last
: 指向要删除元素范围的结束迭代器。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40, 50}; |
5 | auto startIt = vec.begin() + 1; // 指向 20 |
6 | auto endIt = vec.begin() + 4; // 指向 50 |
7 | auto it = vec.erase(startIt, endIt); // 删除 [20, 50) 范围的元素 (20, 30, 40) |
8 | std::cout << "Vector elements after erase range: "; |
9 | for (int val : vec) { |
10 | std::cout << val << " "; // 输出:Vector elements after erase range: 10 50 |
11 | } |
12 | std::cout << std::endl; |
13 | std::cout << "Iterator it now points to (if not end): "; |
14 | if (it != vec.end()) { |
15 | std::cout << *it << std::endl; // 输出:Iterator it now points to (if not end): 50 |
16 | } else { |
17 | std::cout << "end()" << std::endl; |
18 | } |
19 | return 0; |
20 | } |
5.3.7 clear() 方法
1 | void clear() noexcept; |
⚝ 作用:移除向量 (Vector) 中的所有元素,使其变为空向量 (Vector)。向量 (Vector) 的容量 (capacity) 可能会保持不变,也可能会根据实现而改变。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | vec.clear(); // 清空向量 |
6 | std::cout << "Vector size after clear: " << vec.size() << std::endl; // 输出:Vector size after clear: 0 |
7 | std::cout << "Vector is empty: " << (vec.empty() ? "true" : "false") << std::endl; // 输出:Vector is empty: true |
8 | return 0; |
9 | } |
5.3.8 assign() 方法
folly::Vector
提供了多个重载版本的 assign()
方法,用于为向量 (Vector) 赋予新的内容,替换原有内容。
① 填充赋值 (Fill Assignment)
1 | void assign(size_type count, const T& value); |
⚝ 作用:将向量 (Vector) 的内容替换为 count
个值为 value
的元素。如果向量 (Vector) 原有内容,会被清除。
⚝ 参数:
▮▮▮▮⚝ count
: 要赋值的元素数量。
▮▮▮▮⚝ value
: 要赋值的元素值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3}; |
5 | vec.assign(5, 100); // 赋值为 5 个 100 |
6 | std::cout << "Vector elements after fill assign: "; |
7 | for (int val : vec) { |
8 | std::cout << val << " "; // 输出:Vector elements after fill assign: 100 100 100 100 100 |
9 | } |
10 | std::cout << std::endl; |
11 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:Vector size: 5 |
12 | return 0; |
13 | } |
② 范围赋值 (Range Assignment)
1 | template <class InputIterator> |
2 | void assign(InputIterator first, InputIterator last); |
⚝ 作用:将向量 (Vector) 的内容替换为由迭代器范围 [first, last)
指定的元素。如果向量 (Vector) 原有内容,会被清除。
⚝ 参数:
▮▮▮▮⚝ first
: 指向要赋值元素范围的起始迭代器。
▮▮▮▮⚝ last
: 指向要赋值元素范围的结束迭代器。
⚝ 示例:
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec = {1, 2, 3}; |
6 | std::vector<int> newValues = {10, 20, 30, 40}; |
7 | vec.assign(newValues.begin(), newValues.end()); // 从 std::vector 赋值 |
8 | std::cout << "Vector elements after range assign: "; |
9 | for (int val : vec) { |
10 | std::cout << val << " "; // 输出:Vector elements after range assign: 10 20 30 40 |
11 | } |
12 | std::cout << std::endl; |
13 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:Vector size: 4 |
14 | return 0; |
15 | } |
③ 初始化列表赋值 (Initializer List Assignment) (C++11 及以上)
1 | void assign(std::initializer_list<T> il); |
⚝ 作用:将向量 (Vector) 的内容替换为初始化列表 il
中的元素。如果向量 (Vector) 原有内容,会被清除。
⚝ 参数:
▮▮▮▮⚝ il
: 要赋值的初始化列表。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {1, 2, 3}; |
5 | vec.assign({100, 200}); // 使用初始化列表赋值 |
6 | std::cout << "Vector elements after initializer list assign: "; |
7 | for (int val : vec) { |
8 | std::cout << val << " "; // 输出:Vector elements after initializer list assign: 100 200 |
9 | } |
10 | std::cout << std::endl; |
11 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:Vector size: 2 |
12 | return 0; |
13 | } |
5.3.9 resize() 方法
1 | void resize(size_type count); |
2 | void resize(size_type count, const T& value); |
⚝ 作用:改变向量 (Vector) 的大小 (size) 为 count
。
▮▮▮▮⚝ 如果 count
小于当前大小,向量 (Vector) 尾部的元素会被删除。
▮▮▮▮⚝ 如果 count
大于当前大小,向量 (Vector) 会在尾部添加新元素。
▮▮▮▮▮▮▮▮⚝ resize(count)
: 新元素默认值初始化(对于基本类型,值不确定;对于类类型,调用默认构造函数)。
▮▮▮▮▮▮▮▮⚝ resize(count, value)
: 新元素用 value
初始化。
⚝ 参数:
▮▮▮▮⚝ count
: 新的向量 (Vector) 大小。
▮▮▮▮⚝ value
(可选): 用于初始化新增元素的值。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | vec.resize(5); // 增大大小到 5,新元素默认初始化 |
6 | std::cout << "Vector elements after resize(5): "; |
7 | for (int val : vec) { |
8 | std::cout << val << " "; // 输出:Vector elements after resize(5): 10 20 30 0 0 (默认初始化值可能不同) |
9 | } |
10 | std::cout << std::endl; |
11 | vec.resize(2); // 减小大小到 2,移除尾部元素 |
12 | std::cout << "Vector elements after resize(2): "; |
13 | for (int val : vec) { |
14 | std::cout << val << " "; // 输出:Vector elements after resize(2): 10 20 |
15 | } |
16 | std::cout << std::endl; |
17 | vec.resize(4, 100); // 增大大小到 4,新元素用 100 初始化 |
18 | std::cout << "Vector elements after resize(4, 100): "; |
19 | for (int val : vec) { |
20 | std::cout << val << " "; // 输出:Vector elements after resize(4, 100): 10 20 100 100 |
21 | } |
22 | std::cout << std::endl; |
23 | return 0; |
24 | } |
5.3.10 swap() 方法
1 | void swap(folly::Vector& other) noexcept; |
⚝ 作用:交换当前向量 (Vector) 与另一个向量 (Vector) other
的内容。swap()
操作通常非常高效,因为它只交换内部指针、大小和容量等信息,而不需要拷贝或移动元素。
⚝ 参数:
▮▮▮▮⚝ other
: 要交换内容的另一个 folly::Vector
对象。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {1, 2, 3}; |
5 | folly::Vector<int> vec2 = {100, 200}; |
6 | std::cout << "Before swap:" << std::endl; |
7 | std::cout << "vec1: "; for (int val : vec1) std::cout << val << " "; std::cout << std::endl; // 输出:vec1: 1 2 3 |
8 | std::cout << "vec2: "; for (int val : vec2) std::cout << val << " "; std::cout << std::endl; // 输出:vec2: 100 200 |
9 | vec1.swap(vec2); // 交换 vec1 和 vec2 的内容 |
10 | std::cout << "After swap:" << std::endl; |
11 | std::cout << "vec1: "; for (int val : vec1) std::cout << val << " "; std::cout << std::endl; // 输出:vec1: 100 200 |
12 | std::cout << "vec2: "; for (int val : vec2) std::cout << val << " "; std::cout << std::endl; // 输出:vec2: 1 2 3 |
13 | return 0; |
14 | } |
总结
folly::Vector
提供了丰富的修改器 API,涵盖了元素的添加、删除、插入、替换以及向量 (Vector) 结构的调整。理解和熟练运用这些 API,可以灵活地操作向量 (Vector) 中的数据,满足各种不同的数据处理需求。在选择修改器 API 时,应考虑性能和语义,例如,emplace_back()
和 emplace()
在构造复杂对象时通常比 push_back()
和 insert()
更高效。
5.4 容量 (Capacity) 相关 API 详解
folly::Vector
的容量 (Capacity) 相关 API 用于查询和管理向量 (Vector) 的内存分配情况。理解容量和大小 (Size) 的区别,以及如何有效地管理容量,对于优化向量 (Vector) 的性能至关重要。本节将详细介绍这些容量相关的 API。
5.4.1 size() 方法
1 | size_type size() const noexcept; |
⚝ 作用:返回向量 (Vector) 中当前元素的数量,即向量 (Vector) 的大小 (Size)。
⚝ 返回值:
▮▮▮▮⚝ size_type
: 无符号整数类型,表示向量 (Vector) 中元素的个数。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40, 50}; |
5 | std::cout << "Vector size: " << vec.size() << std::endl; // 输出:Vector size: 5 |
6 | vec.pop_back(); |
7 | std::cout << "Vector size after pop_back: " << vec.size() << std::endl; // 输出:Vector size after pop_back: 4 |
8 | return 0; |
9 | } |
5.4.2 capacity() 方法
1 | size_type capacity() const noexcept; |
⚝ 作用:返回向量 (Vector) 当前已分配的存储空间可以容纳的元素数量,即向量 (Vector) 的容量 (Capacity)。容量通常大于或等于大小 (Size)。当向量 (Vector) 的大小增长到超过当前容量时,folly::Vector
会自动重新分配更大的内存空间。
⚝ 返回值:
▮▮▮▮⚝ size_type
: 无符号整数类型,表示向量 (Vector) 的容量。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Initial capacity: " << vec.capacity() << std::endl; // 输出:Initial capacity: 0 (或某个初始值,取决于实现) |
6 | for (int i = 0; i < 10; ++i) { |
7 | vec.push_back(i); |
8 | std::cout << "Capacity after push_back " << i + 1 << " elements: " << vec.capacity() << std::endl; |
9 | // 容量会随着元素添加而增长,例如: |
10 | // Capacity after push_back 1 elements: 1 |
11 | // Capacity after push_back 2 elements: 2 |
12 | // Capacity after push_back 3 elements: 4 |
13 | // Capacity after push_back 4 elements: 4 |
14 | // Capacity after push_back 5 elements: 8 |
15 | // ... |
16 | } |
17 | return 0; |
18 | } |
5.4.3 max_size() 方法
1 | size_type max_size() const noexcept; |
⚝ 作用:返回向量 (Vector) 理论上可以容纳的最大元素数量,受到系统和库实现的限制。这个值通常非常大,实际应用中不太可能达到。
⚝ 返回值:
▮▮▮▮⚝ size_type
: 无符号整数类型,表示向量 (Vector) 的最大容量。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Max size of vector: " << vec.max_size() << std::endl; // 输出:Max size of vector: 4611686018427387903 (或一个非常大的值) |
6 | return 0; |
7 | } |
5.4.4 empty() 方法
1 | bool empty() const noexcept; |
⚝ 作用:检查向量 (Vector) 是否为空,即大小 (Size) 是否为 0。
⚝ 返回值:
▮▮▮▮⚝ bool
: 如果向量 (Vector) 为空,返回 true
;否则返回 false
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Is vector empty? " << (vec.empty() ? "true" : "false") << std::endl; // 输出:Is vector empty? true |
6 | vec.push_back(10); |
7 | std::cout << "Is vector empty after push_back? " << (vec.empty() ? "true" : "false") << std::endl; // 输出:Is vector empty after push_back? false |
8 | return 0; |
9 | } |
5.4.5 reserve() 方法
1 | void reserve(size_type new_cap); |
⚝ 作用:预先分配至少能容纳 new_cap
个元素的内存空间,改变向量 (Vector) 的容量 (Capacity)。
▮▮▮▮⚝ 如果 new_cap
大于当前容量,reserve()
会分配新的内存空间,并将现有元素移动到新空间。这可以避免在后续添加元素时多次重新分配内存,提高性能。
▮▮▮▮⚝ 如果 new_cap
小于或等于当前容量,reserve()
可能不做任何操作,也可能根据具体实现进行调整(但通常不会缩小容量)。
▮▮▮▮⚝ reserve()
不会改变向量 (Vector) 的大小 (Size),即使预分配了空间,向量 (Vector) 中实际的元素数量仍然由 size()
返回。
⚝ 参数:
▮▮▮▮⚝ new_cap
: 期望的最小容量。
⚝ 应用场景: 在预知向量 (Vector) 大概需要存储多少元素时,提前调用 reserve()
可以减少内存重新分配的次数,提高性能。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | std::cout << "Initial capacity: " << vec.capacity() << std::endl; // 输出:Initial capacity: 0 (或某个初始值) |
6 | vec.reserve(100); // 预分配容量为 100 的空间 |
7 | std::cout << "Capacity after reserve(100): " << vec.capacity() << std::endl; // 输出:Capacity after reserve(100): 100 (或至少 100) |
8 | std::cout << "Size after reserve(100): " << vec.size() << std::endl; // 输出:Size after reserve(100): 0 (size 不变) |
9 | for (int i = 0; i < 100; ++i) { |
10 | vec.push_back(i); // 添加 100 个元素,不会触发多次重新分配 |
11 | } |
12 | std::cout << "Capacity after push_back 100 elements: " << vec.capacity() << std::endl; // 输出:Capacity after push_back 100 elements: 100 (或更大,但至少 100) |
13 | std::cout << "Size after push_back 100 elements: " << vec.size() << std::endl; // 输出:Size after push_back 100 elements: 100 |
14 | return 0; |
15 | } |
5.4.6 shrink_to_fit() 方法
1 | void shrink_to_fit(); |
⚝ 作用:尝试减小向量 (Vector) 的容量 (Capacity) 以适应当前的大小 (Size)。调用 shrink_to_fit()
后,容量可能会减小到等于或略大于当前大小,从而释放多余的内存。但是,shrink_to_fit()
只是一个请求,具体是否缩小容量以及缩小到什么程度取决于具体的实现。在某些情况下,容量可能不会发生变化。
⚝ 性能考量: shrink_to_fit()
可能会导致内存重新分配和元素移动,因此在性能敏感的场景下,需要权衡是否使用。频繁地调用 shrink_to_fit()
可能会降低性能。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec; |
5 | vec.reserve(100); // 预分配容量 100 |
6 | std::cout << "Capacity after reserve(100): " << vec.capacity() << std::endl; // 输出:Capacity after reserve(100): 100 (或至少 100) |
7 | for (int i = 0; i < 10; ++i) { |
8 | vec.push_back(i); |
9 | } |
10 | std::cout << "Capacity after push_back 10 elements: " << vec.capacity() << std::endl; // 输出:Capacity after push_back 10 elements: 100 (容量仍然是 100) |
11 | vec.shrink_to_fit(); // 尝试缩小容量 |
12 | std::cout << "Capacity after shrink_to_fit(): " << vec.capacity() << std::endl; // 输出:Capacity after shrink_to_fit(): 10 (或略大于 10,取决于实现) |
13 | std::cout << "Size after shrink_to_fit(): " << vec.size() << std::endl; // 输出:Size after shrink_to_fit(): 10 (size 不变) |
14 | return 0; |
15 | } |
总结
容量 (Capacity) 相关 API 提供了对 folly::Vector
内存管理的控制能力。size()
和 capacity()
用于查询向量 (Vector) 的大小和容量,max_size()
返回最大容量限制,empty()
检查向量 (Vector) 是否为空。reserve()
允许预先分配内存,避免频繁的内存重新分配,而 shrink_to_fit()
则尝试释放多余的内存。合理地使用这些 API,可以有效地管理 folly::Vector
的内存使用,并优化性能。理解大小和容量的区别,以及它们对性能的影响,是高效使用 folly::Vector
的关键。
5.5 迭代器 (Iterator) 相关 API 详解
迭代器 (Iterator) 是访问容器 (Container) 中元素的一种通用方式。folly::Vector
提供了多种迭代器相关的 API,用于遍历向量 (Vector) 中的元素。本节将详细介绍这些迭代器 API,包括不同类型的迭代器以及如何使用它们进行遍历。
5.5.1 begin() 和 end() 方法
1 | iterator begin() noexcept; |
2 | const_iterator begin() const noexcept; |
3 | iterator end() noexcept; |
4 | const_iterator end() const noexcept; |
⚝ 作用:
▮▮▮▮⚝ begin()
: 返回指向向量 (Vector) 第一个元素的迭代器。
▮▮▮▮⚝ end()
: 返回指向向量 (Vector) 尾后位置 (past-the-end) 的迭代器。尾后位置并不指向任何实际元素,而是作为遍历结束的标志。
▮▮▮▮⚝ 提供了 iterator
和 const_iterator
两个版本,分别用于可修改和只读访问。
⚝ 返回值:
▮▮▮▮⚝ iterator
: 指向元素的可修改迭代器(用于非 const
向量)。
▮▮▮▮⚝ const_iterator
: 指向元素的常量迭代器(用于 const
向量)。
⚝ 迭代器范围: [begin(), end())
表示一个左闭右开区间,包含了向量 (Vector) 中的所有元素。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; |
5 | std::cout << "Iterating using begin() and end(): "; |
6 | for (auto it = vec.begin(); it != vec.end(); ++it) { |
7 | std::cout << *it << " "; // 输出:Iterating using begin() and end(): 10 20 30 40 |
8 | } |
9 | std::cout << std::endl; |
10 | // 使用 const_iterator 遍历 const 向量 |
11 | const folly::Vector<int> constVec = {50, 60}; |
12 | std::cout << "Iterating const vector using begin() and end(): "; |
13 | for (auto it = constVec.begin(); it != constVec.end(); ++it) { |
14 | std::cout << *it << " "; // 输出:Iterating const vector using begin() and end(): 50 60 |
15 | } |
16 | std::cout << std::endl; |
17 | return 0; |
18 | } |
5.5.2 cbegin() 和 cend() 方法 (C++11 及以上)
1 | const_iterator cbegin() const noexcept; |
2 | const_iterator cend() const noexcept; |
⚝ 作用:
▮▮▮▮⚝ cbegin()
: 返回指向向量 (Vector) 第一个元素的常量迭代器 (const_iterator)。
▮▮▮▮⚝ cend()
: 返回指向向量 (Vector) 尾后位置的常量迭代器 (const_iterator)。
▮▮▮▮⚝ cbegin()
和 cend()
总是返回常量迭代器,即使在非 const
向量上调用,也只能进行只读访问。
⚝ 返回值:
▮▮▮▮⚝ const_iterator
: 指向元素的常量迭代器。
⚝ 应用场景: 在需要确保只读访问向量 (Vector) 元素时,可以使用 cbegin()
和 cend()
,避免意外修改元素。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | std::cout << "Iterating using cbegin() and cend(): "; |
6 | for (auto it = vec.cbegin(); it != vec.cend(); ++it) { |
7 | std::cout << *it << " "; // 输出:Iterating using cbegin() and cend(): 10 20 30 |
8 | // *it = 100; // 错误:const_iterator 不允许修改元素 |
9 | } |
10 | std::cout << std::endl; |
11 | return 0; |
12 | } |
5.5.3 rbegin() 和 rend() 方法
1 | reverse_iterator rbegin() noexcept; |
2 | const_reverse_iterator rbegin() const noexcept; |
3 | reverse_iterator rend() noexcept; |
4 | const_reverse_iterator rend() const noexcept; |
⚝ 作用:
▮▮▮▮⚝ rbegin()
: 返回指向向量 (Vector) 最后一个元素的反向迭代器 (reverse_iterator)。
▮▮▮▮⚝ rend()
: 返回指向向量 (Vector) 首元素之前位置 (before-the-beginning) 的反向迭代器 (reverse_iterator)。
▮▮▮▮⚝ 提供了 reverse_iterator
和 const_reverse_iterator
两个版本,分别用于可修改和只读反向访问。
⚝ 返回值:
▮▮▮▮⚝ reverse_iterator
: 指向元素的可修改反向迭代器(用于非 const
向量)。
▮▮▮▮⚝ const_reverse_iterator
: 指向元素的常量反向迭代器(用于 const
向量)。
⚝ 反向迭代器范围: [rbegin(), rend())
表示反向遍历的左闭右开区间。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30, 40}; |
5 | std::cout << "Reverse iterating using rbegin() and rend(): "; |
6 | for (auto it = vec.rbegin(); it != vec.rend(); ++it) { |
7 | std::cout << *it << " "; // 输出:Reverse iterating using rbegin() and rend(): 40 30 20 10 |
8 | } |
9 | std::cout << std::endl; |
10 | // 使用 const_reverse_iterator 遍历 const 向量 |
11 | const folly::Vector<int> constVec = {50, 60}; |
12 | std::cout << "Reverse iterating const vector using rbegin() and rend(): "; |
13 | for (auto it = constVec.rbegin(); it != constVec.rend(); ++it) { |
14 | std::cout << *it << " "; // 输出:Reverse iterating const vector using rbegin() and rend(): 60 50 |
15 | } |
16 | std::cout << std::endl; |
17 | return 0; |
18 | } |
5.5.4 crbegin() 和 crend() 方法 (C++11 及以上)
1 | const_reverse_iterator crbegin() const noexcept; |
2 | const_reverse_iterator crend() const noexcept; |
⚝ 作用:
▮▮▮▮⚝ crbegin()
: 返回指向向量 (Vector) 最后一个元素的常量反向迭代器 (const_reverse_iterator)。
▮▮▮▮⚝ crend()
: 返回指向向量 (Vector) 首元素之前位置的常量反向迭代器 (const_reverse_iterator)。
▮▮▮▮⚝ crbegin()
和 crend()
总是返回常量反向迭代器,即使在非 const
向量上调用,也只能进行只读反向访问。
⚝ 返回值:
▮▮▮▮⚝ const_reverse_iterator
: 指向元素的常量反向迭代器。
⚝ 应用场景: 在需要确保只读反向遍历向量 (Vector) 元素时,可以使用 crbegin()
和 crend()
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec = {10, 20, 30}; |
5 | std::cout << "Reverse iterating using crbegin() and crend(): "; |
6 | for (auto it = vec.crbegin(); it != vec.crend(); ++it) { |
7 | std::cout << *it << " "; // 输出:Reverse iterating using crbegin() and crend(): 30 20 10 |
8 | // *it = 100; // 错误:const_reverse_iterator 不允许修改元素 |
9 | } |
10 | std::cout << std::endl; |
11 | return 0; |
12 | } |
5.5.5 迭代器类型总结
folly::Vector
提供了四种主要的迭代器类型,以满足不同的遍历和访问需求:
① iterator
: 默认迭代器类型,用于正向遍历,可以读取和修改元素。通过 begin()
和 end()
返回。
② const_iterator
: 常量迭代器类型,用于正向遍历,只能读取元素,不能修改。通过 cbegin()
和 cend()
返回,也可以通过 begin()
和 end()
在 const
向量上返回。
③ reverse_iterator
: 反向迭代器类型,用于反向遍历,可以读取和修改元素。通过 rbegin()
和 rend()
返回。
④ const_reverse_iterator
: 常量反向迭代器类型,用于反向遍历,只能读取元素,不能修改。通过 crbegin()
和 crend()
返回,也可以通过 rbegin()
和 rend()
在 const
向量上返回。
总结
迭代器是遍历 folly::Vector
元素的关键工具。begin()
, end()
, cbegin()
, cend()
, rbegin()
, rend()
, crbegin()
, crend()
等 API 提供了不同类型的迭代器,以支持正向、反向、可修改和只读的遍历方式。选择合适的迭代器类型,可以灵活地访问和操作向量 (Vector) 中的元素,并确保代码的安全性和效率。理解不同迭代器类型的特点和使用场景,是掌握 folly::Vector
迭代器 API 的重要一步。
5.6 其他常用 API 详解
除了前面几节介绍的构造函数、析构函数、元素访问、修改器和容量、迭代器相关的 API 外,folly::Vector
还提供了一些其他常用的 API,用于比较向量 (Vector)、获取分配器等。本节将介绍这些其他常用 API。
5.6.1 比较运算符 (Comparison Operators)
folly::Vector
重载了比较运算符,可以方便地比较两个向量 (Vector) 的内容。
① operator==
(等于)
1 | bool operator==(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
是否相等。只有当两个向量 (Vector) 的大小相同,并且所有对应位置的元素都相等时,才返回 true
,否则返回 false
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | std::cout << "vec1 == vec2: " << (vec1 == vec2 ? "true" : "false") << std::endl; // 输出:vec1 == vec2: true |
9 | std::cout << "vec1 == vec3: " << (vec1 == vec3 ? "true" : "false") << std::endl; // 输出:vec1 == vec3: false |
10 | std::cout << "vec1 == vec4: " << (vec1 == vec4 ? "true" : "false") << std::endl; // 输出:vec1 == vec4: false |
11 | return 0; |
12 | } |
② operator!=
(不等于)
1 | bool operator!=(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
是否不相等。与 operator==
相反,只要两个向量 (Vector) 的大小不同,或者存在任何对应位置的元素不相等,就返回 true
,否则返回 false
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | std::cout << "vec1 != vec2: " << (vec1 != vec2 ? "true" : "false") << std::endl; // 输出:vec1 != vec2: false |
9 | std::cout << "vec1 != vec3: " << (vec1 != vec3 ? "true" : "false") << std::endl; // 输出:vec1 != vec3: true |
10 | std::cout << "vec1 != vec4: " << (vec1 != vec4 ? "true" : "false") << std::endl; // 输出:vec1 != vec4: true |
11 | return 0; |
12 | } |
③ operator<
(小于)
1 | bool operator<(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
的字典序大小。按照字典序规则,从第一个元素开始逐个比较,直到找到不相等的元素或者其中一个向量 (Vector) 结束。
▮▮▮▮⚝ 如果在某个位置 i
,lhs[i] < rhs[i]
,则 lhs < rhs
为 true
。
▮▮▮▮⚝ 如果在某个位置 i
,lhs[i] > rhs[i]
,则 lhs < rhs
为 false
。
▮▮▮▮⚝ 如果所有对应位置的元素都相等,但 lhs
的大小小于 rhs
的大小,则 lhs < rhs
为 true
。
▮▮▮▮⚝ 其他情况,lhs < rhs
为 false
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | folly::Vector<int> vec5 = {5, 20, 30}; |
9 | std::cout << "vec1 < vec2: " << (vec1 < vec2 ? "true" : "false") << std::endl; // 输出:vec1 < vec2: false |
10 | std::cout << "vec1 < vec3: " << (vec1 < vec3 ? "true" : "false") << std::endl; // 输出:vec1 < vec3: true |
11 | std::cout << "vec1 < vec4: " << (vec1 < vec4 ? "true" : "false") << std::endl; // 输出:vec1 < vec4: false |
12 | std::cout << "vec4 < vec1: " << (vec4 < vec1 ? "true" : "false") << std::endl; // 输出:vec4 < vec1: true |
13 | std::cout << "vec5 < vec1: " << (vec5 < vec1 ? "true" : "false") << std::endl; // 输出:vec5 < vec1: true |
14 | return 0; |
15 | } |
④ operator<=
(小于等于)
1 | bool operator<=(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
的字典序大小,判断 lhs
是否小于等于 rhs
。等价于 !(rhs < lhs)
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | std::cout << "vec1 <= vec2: " << (vec1 <= vec2 ? "true" : "false") << std::endl; // 输出:vec1 <= vec2: true |
9 | std::cout << "vec1 <= vec3: " << (vec1 <= vec3 ? "true" : "false") << std::endl; // 输出:vec1 <= vec3: true |
10 | std::cout << "vec3 <= vec1: " << (vec3 <= vec1 ? "true" : "false") << std::endl; // 输出:vec3 <= vec1: false |
11 | std::cout << "vec4 <= vec1: " << (vec4 <= vec1 ? "true" : "false") << std::endl; // 输出:vec4 <= vec1: true |
12 | return 0; |
13 | } |
⑤ operator>
(大于)
1 | bool operator>(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
的字典序大小,判断 lhs
是否大于 rhs
。等价于 (rhs < lhs)
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | std::cout << "vec1 > vec2: " << (vec1 > vec2 ? "true" : "false") << std::endl; // 输出:vec1 > vec2: false |
9 | std::cout << "vec3 > vec1: " << (vec3 > vec1 ? "true" : "false") << std::endl; // 输出:vec3 > vec1: true |
10 | std::cout << "vec1 > vec4: " << (vec1 > vec4 ? "true" : "false") << std::endl; // 输出:vec1 > vec4: true |
11 | std::cout << "vec4 > vec1: " << (vec4 > vec1 ? "true" : "false") << std::endl; // 输出:vec4 > vec1: false |
12 | return 0; |
13 | } |
⑥ operator>=
(大于等于)
1 | bool operator>=(const folly::Vector& lhs, const folly::Vector& rhs); |
⚝ 作用:比较两个向量 (Vector) lhs
和 rhs
的字典序大小,判断 lhs
是否大于等于 rhs
。等价于 !(lhs < rhs)
。
⚝ 示例:
1 | |
2 | |
3 | int main() { |
4 | folly::Vector<int> vec1 = {10, 20, 30}; |
5 | folly::Vector<int> vec2 = {10, 20, 30}; |
6 | folly::Vector<int> vec3 = {10, 20, 40}; |
7 | folly::Vector<int> vec4 = {10, 20}; |
8 | std::cout << "vec1 >= vec2: " << (vec1 >= vec2 ? "true" : "false") << std::endl; // 输出:vec1 >= vec2: true |
9 | std::cout << "vec3 >= vec1: " << (vec3 >= vec1 ? "true" : "false") << std::endl; // 输出:vec3 >= vec1: true |
10 | std::cout << "vec4 >= vec1: " << (vec4 >= vec1 ? "true" : "false") << std::endl; // 输出:vec4 >= vec1: false |
11 | std::cout << "vec1 >= vec4: " << (vec1 >= vec4 ? "true" : "false") << std::endl; // 输出:vec1 >= vec4: true |
12 | return 0; |
13 | } |
5.6.2 get_allocator() 方法
1 | allocator_type get_allocator() const noexcept; |
⚝ 作用:返回与向量 (Vector) 关联的分配器 (allocator) 对象的拷贝。分配器对象负责向量 (Vector) 的内存分配和释放。默认情况下,folly::Vector
使用 std::allocator
。
⚝ 返回值:
▮▮▮▮⚝ allocator_type
: 分配器类型,通常是 std::allocator<T>
.
⚝ 应用场景: get_allocator()
方法主要用于高级内存管理和自定义分配器场景。在大多数情况下,默认的分配器已经足够使用,无需显式操作分配器。
⚝ 示例:
1 | |
2 | |
3 | |
4 | int main() { |
5 | folly::Vector<int> vec; |
6 | std::allocator<int> alloc = vec.get_allocator(); // 获取分配器 |
7 | // 可以使用 allocator 进行内存分配和释放,但这通常不是必需的 |
8 | int* ptr = alloc.allocate(1); // 分配一个 int 的空间 |
9 | alloc.deallocate(ptr, 1); // 释放分配的空间 |
10 | std::cout << "Allocator class name: " << typeid(alloc).name() << std::endl; // 输出:Allocator class name: St17allocatorIiE (取决于编译器) |
11 | return 0; |
12 | } |
5.6.3 其他可能存在的 API
除了上述详细介绍的 API 外,folly::Vector
可能还会根据 folly
库的版本和具体实现,提供一些其他的辅助 API 或重载操作符。在实际使用中,建议查阅 folly
官方文档或头文件 (Vector.h
) 以获取最准确和全面的 API 信息。
总结
本节介绍了 folly::Vector
的其他常用 API,包括比较运算符和 get_allocator()
方法。比较运算符使得向量 (Vector) 之间的比较变得简单直接,而 get_allocator()
方法则提供了访问底层内存分配器的途径。这些 API 进一步丰富了 folly::Vector
的功能,使其在各种应用场景下都能提供强大而灵活的支持。掌握这些 API,可以更全面地理解和使用 folly::Vector
。
END_OF_CHAPTER
6. chapter 6: 实战案例:folly::Vector 在实际项目中的应用
6.1 案例一:高性能数据缓存的实现 (Case 1: Implementation of High-Performance Data Cache)
在现代软件系统中,高性能数据缓存(High-Performance Data Cache)是提升应用性能的关键组件。缓存通过将热点数据存储在快速访问的介质中,减少对后端存储系统的访问延迟,从而显著提高数据读取速度和系统响应能力。folly::Vector
由于其高效的内存管理和快速的元素访问特性,非常适合作为高性能缓存的底层数据结构。
场景描述:
假设我们需要构建一个内存缓存系统,用于存储频繁访问的数据对象。该缓存需要具备以下特点:
① 高性能:快速的数据读取和写入操作,尽可能降低延迟。
② 高效率:有效利用内存资源,避免不必要的内存开销。
③ 动态性:能够根据数据量动态调整容量,适应不同的负载情况。
folly::Vector
的应用:
folly::Vector
可以作为缓存值的存储容器。我们可以使用 folly::Vector<T>
来存储缓存的数据项,其中 T
可以是任意类型,例如基本数据类型、复杂对象或者智能指针。
代码示例:
以下代码示例展示了如何使用 folly::Vector
实现一个简单的基于内存的缓存:
1 | |
2 | |
3 | |
4 | |
5 | template <typename KeyType, typename ValueType> |
6 | class SimpleCache { |
7 | public: |
8 | SimpleCache(size_t capacity) : capacity_(capacity) {} |
9 | bool get(const KeyType& key, ValueType& value) { |
10 | auto it = cache_.find(key); |
11 | if (it != cache_.end()) { |
12 | value = it->second; |
13 | return true; |
14 | } |
15 | return false; |
16 | } |
17 | void put(const KeyType& key, const ValueType& value) { |
18 | if (cache_.size() >= capacity_) { |
19 | // 缓存已满,简单策略:直接替换 |
20 | cache_.erase(cache_.begin()); // 移除最旧的元素 (FIFO 策略简化) |
21 | } |
22 | cache_[key] = value; |
23 | } |
24 | size_t size() const { |
25 | return cache_.size(); |
26 | } |
27 | size_t capacity() const { |
28 | return capacity_; |
29 | } |
30 | private: |
31 | size_t capacity_; |
32 | std::unordered_map<KeyType, ValueType> cache_; // 使用 unordered_map 作为缓存索引 |
33 | }; |
34 | int main() { |
35 | SimpleCache<std::string, folly::Vector<int>> vectorCache(10); |
36 | // 存入数据 |
37 | folly::Vector<int> vec1 = {1, 2, 3}; |
38 | folly::Vector<int> vec2 = {4, 5, 6, 7}; |
39 | vectorCache.put("key1", vec1); |
40 | vectorCache.put("key2", vec2); |
41 | // 读取数据 |
42 | folly::Vector<int> retrievedVec1; |
43 | if (vectorCache.get("key1", retrievedVec1)) { |
44 | std::cout << "key1: "; |
45 | for (int val : retrievedVec1) { |
46 | std::cout << val << " "; |
47 | } |
48 | std::cout << std::endl; |
49 | } |
50 | folly::Vector<int> retrievedVec2; |
51 | if (vectorCache.get("key2", retrievedVec2)) { |
52 | std::cout << "key2: "; |
53 | for (int val : retrievedVec2) { |
54 | std::cout << val << " "; |
55 | } |
56 | std::cout << std::endl; |
57 | } |
58 | std::cout << "Cache size: " << vectorCache.size() << std::endl; |
59 | std::cout << "Cache capacity: " << vectorCache.capacity() << std::endl; |
60 | return 0; |
61 | } |
代码解析:
① SimpleCache
类:定义了一个简单的缓存类,使用 std::unordered_map
作为缓存的索引,键为 KeyType
,值为 ValueType
。在本例中,ValueType
是 folly::Vector<int>
,意味着缓存的值是 folly::Vector
容器。
② get()
方法:根据键值从缓存中检索数据。如果找到,则将值复制到 value
参数并返回 true
,否则返回 false
。
③ put()
方法:将键值对存入缓存。如果缓存已满,则采用简单的 FIFO (先进先出) 策略移除最旧的元素。
④ main()
函数:演示了 SimpleCache
的基本用法,创建了一个缓存实例,存入和读取了 folly::Vector<int>
类型的数据。
优势分析:
① 高效存储复杂数据:folly::Vector
能够高效地存储和管理动态大小的数据集合,非常适合缓存变长的数据对象,例如网络请求的响应数据、配置文件内容等。
② 快速访问:folly::Vector
提供了快速的元素访问速度,保证了缓存的读取性能。
③ 动态调整容量:folly::Vector
的动态数组特性使得缓存能够根据实际数据量自动扩展或收缩,提高了内存利用率。
④ 与 folly
库的集成:如果项目已经使用了 folly
库,那么使用 folly::Vector
可以无缝集成,减少依赖,并可能与其他 folly
组件更好地协同工作。
总结:
folly::Vector
在高性能数据缓存的实现中,可以作为高效、灵活的数据存储容器,尤其适用于缓存复杂结构或动态大小的数据对象。通过结合合适的缓存策略和索引结构,可以构建出高性能、高效率的缓存系统,提升应用程序的整体性能。
6.2 案例二:日志系统的优化 (Case 2: Optimization of Logging System)
日志系统是软件系统中不可或缺的组成部分,用于记录系统运行状态、错误信息和用户行为等。高性能的日志系统需要能够快速、可靠地写入大量日志数据,同时尽可能减少对系统性能的影响。folly::Vector
可以应用于日志系统的优化,特别是在日志缓冲和批量写入方面。
场景描述:
假设我们需要优化一个现有的日志系统,该系统在高峰期会产生大量的日志数据,频繁的磁盘 I/O 操作成为性能瓶颈。优化的目标是:
① 减少 I/O 次数:通过批量写入日志,降低磁盘 I/O 频率,提高写入效率。
② 提高写入速度:使用高效的数据结构作为日志缓冲区,减少内存拷贝和管理开销。
③ 异步写入:将日志写入操作异步化,避免阻塞主线程,提高系统响应性。
folly::Vector
的应用:
folly::Vector
可以作为日志消息的缓冲区。日志消息可以先暂存在 folly::Vector
中,当缓冲区满或者达到一定时间间隔时,再批量写入到日志文件或远程存储。
代码示例:
以下代码示例展示了如何使用 folly::Vector
实现一个简单的日志缓冲和批量写入功能:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | |
8 | class AsyncLogger { |
9 | public: |
10 | AsyncLogger(const std::string& logFilePath, size_t bufferSize = 1024) |
11 | : logFilePath_(logFilePath), bufferSize_(bufferSize), running_(true), workerThread_([this] { run(); }) {} |
12 | ~AsyncLogger() { |
13 | stop(); |
14 | workerThread_.join(); |
15 | flush(); // 确保退出前刷新缓冲区 |
16 | } |
17 | void log(const std::string& message) { |
18 | { |
19 | std::lock_guard<std::mutex> lock(mutex_); |
20 | logBuffer_.push_back(message); |
21 | } |
22 | if (logBuffer_.size() >= bufferSize_) { |
23 | condition_.notify_one(); // 通知工作线程写入日志 |
24 | } |
25 | } |
26 | void stop() { |
27 | running_ = false; |
28 | condition_.notify_one(); // 唤醒工作线程,使其退出 |
29 | } |
30 | private: |
31 | void run() { |
32 | while (running_) { |
33 | { |
34 | std::unique_lock<std::mutex> lock(mutex_); |
35 | condition_.wait(lock, [this] { return !running_ || logBuffer_.size() >= bufferSize_; }); |
36 | } |
37 | flush(); |
38 | } |
39 | } |
40 | void flush() { |
41 | folly::Vector<std::string> messagesToWrite; |
42 | { |
43 | std::lock_guard<std::mutex> lock(mutex_); |
44 | if (logBuffer_.empty()) return; |
45 | messagesToWrite.swap(logBuffer_); // 高效交换,避免拷贝 |
46 | logBuffer_.clear(); // 清空原始 buffer |
47 | } |
48 | std::ofstream logFile(logFilePath_, std::ios::app); |
49 | if (logFile.is_open()) { |
50 | for (const auto& message : messagesToWrite) { |
51 | logFile << message << std::endl; |
52 | } |
53 | logFile.close(); |
54 | } else { |
55 | std::cerr << "Error opening log file: " << logFilePath_ << std::endl; |
56 | } |
57 | } |
58 | private: |
59 | std::string logFilePath_; |
60 | size_t bufferSize_; |
61 | folly::Vector<std::string> logBuffer_; // 使用 folly::Vector 作为日志缓冲区 |
62 | std::mutex mutex_; |
63 | std::condition_variable condition_; |
64 | std::thread workerThread_; |
65 | bool running_; |
66 | }; |
67 | int main() { |
68 | AsyncLogger logger("app.log"); |
69 | for (int i = 0; i < 1000; ++i) { |
70 | logger.log("Log message " + std::to_string(i)); |
71 | } |
72 | // 程序结束时,logger 的析构函数会确保日志被刷新和写入 |
73 | return 0; |
74 | } |
代码解析:
① AsyncLogger
类:实现了一个异步日志记录器。
② logBuffer_
:使用 folly::Vector<std::string>
作为日志消息的缓冲区。
③ log()
方法:将日志消息添加到缓冲区。当缓冲区大小达到 bufferSize_
时,通过条件变量 condition_
通知工作线程。
④ run()
方法:工作线程的主循环,等待缓冲区满或收到停止信号。
⑤ flush()
方法:将缓冲区中的日志消息批量写入到日志文件。使用 messagesToWrite.swap(logBuffer_)
高效地交换缓冲区内容,避免不必要的内存拷贝。
⑥ 异步写入:日志写入操作在单独的工作线程中执行,不会阻塞主线程,提高了系统的响应性。
优势分析:
① 批量写入:通过 folly::Vector
缓冲区,将多次小的日志写入操作合并为一次大的批量写入,显著减少了磁盘 I/O 次数,提高了写入效率。
② 高效缓冲区:folly::Vector
作为缓冲区,提供了高效的内存管理和快速的元素添加操作,降低了日志记录的开销。
③ 异步处理:异步日志写入机制保证了日志记录不会阻塞主线程,提高了系统的并发性和响应速度。
④ 减少内存拷贝:使用 swap()
操作交换缓冲区内容,避免了大量日志消息的拷贝,提高了性能。
总结:
folly::Vector
在日志系统优化中,可以作为高效的日志缓冲区,结合异步写入和批量处理技术,显著提高日志系统的性能和可靠性。尤其在高并发、大流量的应用场景下,使用 folly::Vector
优化的日志系统能够有效地降低 I/O 瓶颈,提升系统整体性能。
6.3 案例三:图数据结构的构建与操作 (Case 3: Construction and Operation of Graph Data Structure)
图(Graph)是一种重要的非线性数据结构,广泛应用于社交网络、推荐系统、路由算法等领域。在图数据结构的实现中,邻接表(Adjacency List)是一种常用的表示方法,它使用列表来存储每个顶点的邻居节点。folly::Vector
由于其动态数组的特性和高效的元素访问能力,非常适合用于实现邻接表。
场景描述:
假设我们需要构建一个图数据结构,用于表示社交网络中的用户关系。图的顶点表示用户,边表示用户之间的关注关系。我们需要支持以下操作:
① 添加顶点和边:动态地向图中添加用户和关注关系。
② 查询顶点的邻居:快速获取某个用户关注的所有用户(邻居节点)。
③ 图的遍历:支持图的深度优先搜索 (DFS) 或广度优先搜索 (BFS) 等遍历算法。
folly::Vector
的应用:
可以使用 folly::Vector
来实现邻接表。对于图中的每个顶点,可以使用一个 folly::Vector
来存储其邻居节点。
代码示例:
以下代码示例展示了如何使用 folly::Vector
实现一个简单的基于邻接表的图数据结构,并进行基本的图操作:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | class Graph { |
7 | public: |
8 | Graph() = default; |
9 | void addVertex(int vertex) { |
10 | if (adjacencyList_.find(vertex) == adjacencyList_.end()) { |
11 | adjacencyList_[vertex] = folly::Vector<int>(); |
12 | } |
13 | } |
14 | void addEdge(int u, int v) { |
15 | addVertex(u); |
16 | addVertex(v); |
17 | adjacencyList_[u].push_back(v); // 有向图,只添加 u -> v 的边 |
18 | } |
19 | const folly::Vector<int>& getNeighbors(int vertex) const { |
20 | auto it = adjacencyList_.find(vertex); |
21 | if (it != adjacencyList_.end()) { |
22 | return it->second; |
23 | } else { |
24 | static const folly::Vector<int> emptyNeighbors; // 返回空邻居列表 |
25 | return emptyNeighbors; |
26 | } |
27 | } |
28 | void bfs(int startVertex) const { |
29 | std::unordered_map<int, bool> visited; |
30 | std::queue<int> q; |
31 | visited[startVertex] = true; |
32 | q.push(startVertex); |
33 | std::cout << "BFS traversal starting from vertex " << startVertex << ": "; |
34 | while (!q.empty()) { |
35 | int u = q.front(); |
36 | q.pop(); |
37 | std::cout << u << " "; |
38 | for (int v : getNeighbors(u)) { |
39 | if (!visited[v]) { |
40 | visited[v] = true; |
41 | q.push(v); |
42 | } |
43 | } |
44 | } |
45 | std::cout << std::endl; |
46 | } |
47 | private: |
48 | std::unordered_map<int, folly::Vector<int>> adjacencyList_; // 邻接表,使用 folly::Vector 存储邻居节点 |
49 | }; |
50 | int main() { |
51 | Graph graph; |
52 | // 添加顶点 |
53 | graph.addVertex(1); |
54 | graph.addVertex(2); |
55 | graph.addVertex(3); |
56 | graph.addVertex(4); |
57 | graph.addVertex(5); |
58 | // 添加边 |
59 | graph.addEdge(1, 2); |
60 | graph.addEdge(1, 3); |
61 | graph.addEdge(2, 4); |
62 | graph.addEdge(3, 4); |
63 | graph.addEdge(4, 5); |
64 | // 查询邻居 |
65 | std::cout << "Neighbors of vertex 1: "; |
66 | for (int neighbor : graph.getNeighbors(1)) { |
67 | std::cout << neighbor << " "; |
68 | } |
69 | std::cout << std::endl; |
70 | // BFS 遍历 |
71 | graph.bfs(1); |
72 | return 0; |
73 | } |
代码解析:
① Graph
类:实现了一个简单的图数据结构。
② adjacencyList_
:使用 std::unordered_map<int, folly::Vector<int>>
作为邻接表。键为顶点,值为 folly::Vector<int>
,存储该顶点的邻居节点列表。
③ addVertex()
方法:添加顶点到图中。
④ addEdge()
方法:添加边到图中,这里实现的是有向图。
⑤ getNeighbors()
方法:返回指定顶点的邻居节点列表,返回类型为 const folly::Vector<int>&
,避免不必要的拷贝。
⑥ bfs()
方法:实现广度优先搜索算法,遍历图并打印遍历结果。
优势分析:
① 动态邻接表:folly::Vector
作为邻接表的存储容器,可以动态地添加邻居节点,方便构建和扩展图结构。
② 高效邻居访问:folly::Vector
提供了快速的元素访问速度,使得查询顶点的邻居节点非常高效。
③ 内存效率:folly::Vector
的动态数组特性,使得邻接表能够根据实际的邻居数量动态调整容量,提高了内存利用率。
④ 易于实现图算法:使用 folly::Vector
实现的邻接表,可以方便地进行图的遍历、搜索等算法的实现。
总结:
folly::Vector
在图数据结构的构建与操作中,可以作为高效、灵活的邻接表存储容器。通过使用 folly::Vector
,可以方便地实现动态图的构建、高效的邻居查询以及各种图算法,适用于社交网络分析、推荐系统、路径规划等多种应用场景。
6.4 案例四:并行计算中的数据分发与收集 (Case 4: Data Distribution and Collection in Parallel Computing)
在并行计算中,数据分发(Data Distribution)和数据收集(Data Collection)是关键步骤。数据需要被有效地分割并分发到不同的计算单元进行并行处理,处理完成后,结果需要被收集和汇总。folly::Vector
可以应用于并行计算的数据管理,特别是在数据分发和收集过程中作为数据容器。
场景描述:
假设我们需要进行一项大规模的数据处理任务,例如图像处理、科学计算等,需要将数据分割成多个块,分配给多个计算核心并行处理,最后将各个核心的处理结果收集起来进行汇总。优化的目标是:
① 高效数据分割:快速将数据分割成大小合适的块。
② 灵活数据分发:方便将数据块分发给不同的计算单元。
③ 高效结果收集:快速收集各个计算单元的处理结果。
④ 减少数据拷贝:尽可能减少数据在分发和收集过程中的拷贝开销。
folly::Vector
的应用:
folly::Vector
可以用于存储和管理数据块。在数据分发阶段,可以将原始数据分割成多个 folly::Vector
,每个 folly::Vector
代表一个数据块。在数据收集阶段,可以使用 folly::Vector
存储各个计算单元返回的结果,并进行汇总。
代码示例:
以下代码示例展示了如何使用 folly::Vector
在简单的并行计算场景中进行数据分发和收集:
1 | |
2 | |
3 | |
4 | |
5 | |
6 | |
7 | // 模拟数据处理函数 |
8 | folly::Vector<int> processDataChunk(const folly::Vector<int>& dataChunk) { |
9 | folly::Vector<int> results; |
10 | for (int val : dataChunk) { |
11 | results.push_back(val * 2); // 简单示例:将每个元素乘以 2 |
12 | } |
13 | return results; |
14 | } |
15 | int main() { |
16 | // 原始数据 |
17 | folly::Vector<int> originalData(100); |
18 | std::iota(originalData.begin(), originalData.end(), 1); // 初始化为 1, 2, ..., 100 |
19 | // 数据分块 |
20 | size_t numCores = std::thread::hardware_concurrency(); // 获取硬件线程数 |
21 | size_t chunkSize = originalData.size() / numCores; |
22 | std::vector<folly::Vector<int>> dataChunks; |
23 | for (size_t i = 0; i < numCores; ++i) { |
24 | size_t start = i * chunkSize; |
25 | size_t end = (i == numCores - 1) ? originalData.size() : (i + 1) * chunkSize; |
26 | folly::Vector<int> chunk; |
27 | for (size_t j = start; j < end; ++j) { |
28 | chunk.push_back(originalData[j]); |
29 | } |
30 | dataChunks.push_back(chunk); |
31 | } |
32 | // 并行处理 |
33 | std::vector<std::future<folly::Vector<int>>> futures; |
34 | for (const auto& chunk : dataChunks) { |
35 | futures.push_back(std::async(std::launch::async, processDataChunk, chunk)); |
36 | } |
37 | // 结果收集 |
38 | folly::Vector<int> aggregatedResults; |
39 | for (auto& future : futures) { |
40 | folly::Vector<int> results = future.get(); |
41 | aggregatedResults.insert(aggregatedResults.end(), results.begin(), results.end()); // 合并结果 |
42 | } |
43 | // 打印结果 (部分) |
44 | std::cout << "Aggregated results (first 10): "; |
45 | for (size_t i = 0; i < std::min((size_t)10, aggregatedResults.size()); ++i) { |
46 | std::cout << aggregatedResults[i] << " "; |
47 | } |
48 | std::cout << std::endl; |
49 | return 0; |
50 | } |
代码解析:
① processDataChunk()
函数:模拟数据处理函数,接收一个 folly::Vector<int>
数据块,并返回处理结果 folly::Vector<int>
。
② 数据分块:将原始数据 originalData
分割成 numCores
个数据块,存储在 dataChunks
向量中,每个数据块都是一个 folly::Vector<int>
。
③ 并行处理:使用 std::async
启动多个异步任务,并行处理每个数据块。每个任务的返回值是一个 std::future<folly::Vector<int>>
,用于获取处理结果。
④ 结果收集:遍历 futures
,使用 future.get()
获取每个任务的处理结果(folly::Vector<int>
),并将结果合并到 aggregatedResults
中。
⑤ 结果合并:使用 aggregatedResults.insert()
将各个数据块的处理结果合并成一个最终结果 folly::Vector<int>
。
优势分析:
① 灵活数据分块:folly::Vector
可以方便地创建和管理数据块,支持灵活的数据分割策略。
② 高效数据容器:folly::Vector
作为数据块的容器,提供了高效的内存管理和元素访问,适用于大规模数据处理。
③ 方便结果合并:folly::Vector
提供了 insert()
等方法,可以方便地将多个数据块的处理结果合并成一个最终结果。
④ 减少拷贝:在数据分发和收集过程中,可以尽量使用移动语义和引用传递,减少数据拷贝开销,提高性能。
总结:
folly::Vector
在并行计算的数据分发与收集环节,可以作为高效的数据容器,用于存储和管理数据块以及处理结果。通过结合并行计算框架和算法,使用 folly::Vector
可以构建高效、可扩展的并行数据处理系统,加速大规模数据分析和计算任务的完成。
END_OF_CHAPTER
7. chapter 7: folly::Vector 源码剖析与设计思想
7.1 folly::Vector 核心源码分析 (Core Source Code Analysis of folly::Vector)
源码分析是深入理解 folly::Vector
的关键步骤。通过剖析其核心源码,我们可以了解其内部实现机制、数据结构以及性能优化的策略。本节将重点分析 folly::Vector
的关键组成部分,例如内存管理、元素存储和核心操作的实现。请注意,由于 folly
库的源码可能随时更新,以下分析基于常见的版本,并侧重于概念和原理的讲解。为了简化理解,我们可能会使用伪代码或简化的代码片段进行说明,而不是直接复制粘贴大量的源代码。
7.1.1 内存分配与管理 (Memory Allocation and Management)
folly::Vector
作为动态数组,其内存管理是核心组成部分。与 std::vector
类似,folly::Vector
也需要在运行时动态地分配和释放内存,以适应元素数量的变化。
① 分配器 (Allocator):
folly::Vector
依赖于分配器(Allocator)来处理内存的分配和回收。默认情况下,它可能使用标准的 std::allocator
或 folly
库提供的自定义分配器,例如 fb::Allocator
。分配器的选择会直接影响内存分配的效率和策略。folly
库通常会提供更高效的内存分配器,以优化特定场景下的性能。
② 容量 (Capacity) 与增长策略 (Growth Strategy):
与 std::vector
相同,folly::Vector
也维护着容量(capacity)和大小(size)的概念。容量是指已分配的内存空间可以容纳的元素数量,而大小是指当前向量中实际存储的元素数量。当向 folly::Vector
添加元素且当前容量不足时,就需要进行内存重新分配。
⚝ 指数增长 (Exponential Growth):
folly::Vector
通常采用指数增长策略来扩展容量。这意味着每次容量不足时,它会将容量增加到当前容量的某个倍数(例如,2倍或1.5倍)。这种策略可以在摊销常数时间内完成元素的添加操作,避免频繁的内存重新分配。
⚝ 预分配 (Pre-allocation):
folly::Vector
提供了 reserve()
方法,允许用户预先分配一定的内存空间。这在预知向量大致大小的情况下非常有用,可以减少动态内存分配的次数,提高性能。
③ 内存释放 (Memory Deallocation):
当 folly::Vector
对象销毁时,或者当调用 clear()
、pop_back()
、erase()
等方法移除元素时,folly::Vector
需要负责释放不再使用的内存。析构函数会确保所有已分配的内存都被正确释放,防止内存泄漏。shrink_to_fit()
方法可以尝试释放多余的容量,将容量调整为与大小相匹配,从而减少内存占用。
7.1.2 元素存储与访问 (Element Storage and Access)
folly::Vector
内部使用连续的内存空间来存储元素,这与 std::vector
的实现方式一致。连续存储是向量容器高效访问元素的基础。
① 连续内存块 (Contiguous Memory Block):
folly::Vector
的元素存储在一个连续的内存块中,这意味着可以通过指针算术快速访问任何位置的元素。这使得下标访问([]
运算符)和迭代器操作非常高效。
② 指针 (Pointers) 管理:
folly::Vector
内部维护着指向内存块起始位置的指针、指向已用空间的末尾的指针以及指向已分配空间的末尾的指针(用于容量管理)。这些指针协同工作,实现了对元素的有效管理和内存的动态扩展。
③ 元素访问方式:
folly::Vector
提供了多种元素访问方式,包括:
⚝ 下标访问 []
(Subscript Operator):提供快速的随机访问,但不进行边界检查。
⚝ at()
方法:提供带边界检查的访问,当索引越界时会抛出异常。
⚝ front()
和 back()
方法:分别访问第一个和最后一个元素。
⚝ 迭代器 (Iterator):提供遍历容器元素的通用方式。
7.1.3 关键操作的源码分析 (Source Code Analysis of Key Operations)
理解 folly::Vector
关键操作的源码实现,有助于深入了解其性能特点。以下分析几个常用操作:
① push_back(const T& value)
:在向量末尾添加元素(拷贝语义)。
1 | // 伪代码,简化说明 push_back 的原理 |
2 | void push_back(const T& value) { |
3 | if (size_ == capacity_) { // 容量不足 |
4 | reallocate(); // 重新分配内存,通常容量翻倍 |
5 | } |
6 | // 在末尾构造元素,使用拷贝构造 |
7 | allocator_.construct(data_ + size_, value); |
8 | ++size_; |
9 | } |
这个操作首先检查容量是否足够,如果不足则进行重新分配。然后,在内存末尾使用拷贝构造函数构造新的元素,并更新大小。
② emplace_back(Args&&... args)
:在向量末尾添加元素(移动语义/就地构造)。
1 | // 伪代码,简化说明 emplace_back 的原理 |
2 | template <typename... Args> |
3 | void emplace_back(Args&&... args) { |
4 | if (size_ == capacity_) { // 容量不足 |
5 | reallocate(); // 重新分配内存 |
6 | } |
7 | // 在末尾就地构造元素,完美转发构造参数 |
8 | allocator_.construct(data_ + size_, std::forward<Args>(args)...); |
9 | ++size_; |
10 | } |
emplace_back
与 push_back
类似,但它直接在向量末尾使用提供的参数就地构造元素,避免了不必要的拷贝或移动操作,尤其对于复杂对象,性能优势更明显。
③ insert(iterator position, const T& value)
:在指定位置插入元素。
1 | // 伪代码,简化说明 insert 的原理 (简化版,未考虑效率优化) |
2 | iterator insert(iterator position, const T& value) { |
3 | if (size_ == capacity_) { |
4 | reallocate(); // 重新分配内存 |
5 | // position 可能失效,需要重新计算 |
6 | } |
7 | size_type index = position - begin(); // 计算插入位置的索引 |
8 | // 从插入位置开始,将元素向后移动一位 |
9 | for (size_type i = size_; i > index; --i) { |
10 | allocator_.construct(data_ + i, *(data_ + (i - 1))); // 移动元素 (简化,实际可能用 move) |
11 | allocator_.destroy(data_ + (i - 1)); // 销毁原位置元素 (简化,实际情况更复杂) |
12 | } |
13 | // 在插入位置构造新元素 |
14 | allocator_.construct(data_ + index, value); |
15 | ++size_; |
16 | return begin() + index; |
17 | } |
insert
操作相对复杂,它需要在插入位置之后的所有元素向后移动,为新元素腾出空间。这涉及到元素的移动和构造,效率相对较低,特别是当在向量头部或中间位置插入元素时。
④ erase(iterator position)
:移除指定位置的元素。
1 | // 伪代码,简化说明 erase 的原理 (简化版,未考虑效率优化) |
2 | iterator erase(iterator position) { |
3 | if (empty()) { |
4 | return end(); // 空向量,直接返回 |
5 | } |
6 | size_type index = position - begin(); // 计算移除位置的索引 |
7 | // 从移除位置之后开始,将元素向前移动一位 |
8 | for (size_type i = index; i < size_ - 1; ++i) { |
9 | allocator_.construct(data_ + i, *(data_ + (i + 1))); // 移动元素 (简化,实际可能用 move) |
10 | allocator_.destroy(data_ + (i + 1)); // 销毁原位置元素 (简化,实际情况更复杂) |
11 | } |
12 | allocator_.destroy(data_ + size_ - 1); // 销毁最后一个元素 |
13 | --size_; |
14 | return begin() + index; |
15 | } |
erase
操作与 insert
类似,也需要移动元素。移除指定位置的元素后,需要将后续元素向前移动填补空缺。同样,在向量头部或中间位置移除元素的效率较低。
总结:
通过源码分析,我们可以看到 folly::Vector
在内存管理、元素存储和关键操作实现上与 std::vector
有很多相似之处,都基于动态数组的原理。folly::Vector
可能会在内存分配器、增长策略和一些细节实现上进行优化,以追求更高的性能。深入理解这些源码细节,有助于我们更好地使用 folly::Vector
,并在必要时进行性能调优。
7.2 folly::Vector 的设计原则与权衡 (Design Principles and Trade-offs of folly::Vector)
folly::Vector
的设计并非偶然,而是基于一系列的设计原则和权衡考量。理解这些设计原则和权衡,有助于我们认识到 folly::Vector
的优势和局限性,以及在何种场景下它能发挥最佳性能。
7.2.1 设计原则 (Design Principles)
① 高性能 (High Performance):
高性能是 folly
库的核心目标之一,folly::Vector
也不例外。其设计处处体现着对性能的追求,例如:
⚝ 连续存储:保证元素访问的局部性,提高缓存命中率。
⚝ 高效的内存管理:可能使用优化的内存分配器,减少内存分配和释放的开销。
⚝ 移动语义:充分利用 C++11 的移动语义,减少不必要的拷贝操作。
⚝ 针对特定场景的优化:folly::Vector
可能会针对 Facebook 内部的特定应用场景进行优化。
② 与 std::vector
兼容 (Compatibility with std::vector
):
folly::Vector
在 API 设计上尽可能地与 std::vector
保持兼容。这降低了学习成本,并使得从 std::vector
迁移到 folly::Vector
变得相对容易。大多数 std::vector
的操作在 folly::Vector
中都有对应的实现,并且行为也基本一致。
③ 现代 C++ 特性 (Modern C++ Features):
folly::Vector
充分利用了现代 C++ 的特性,例如:
⚝ 模板 (Templates):泛型编程的基础,使得 folly::Vector
可以存储任意类型的元素。
⚝ 移动语义 (Move Semantics):提高性能的关键特性。
⚝ 异常安全 (Exception Safety):保证在异常发生时,程序的状态仍然是有效的。
⚝ RAII (Resource Acquisition Is Initialization):资源管理的重要原则,确保资源在对象生命周期内得到正确管理。
④ 可扩展性与可维护性 (Extensibility and Maintainability):
虽然性能是首要目标,但 folly::Vector
的设计也考虑了可扩展性和可维护性。清晰的代码结构、良好的注释以及模块化的设计,都有助于后续的维护和功能扩展。
7.2.2 设计权衡 (Design Trade-offs)
在追求高性能的同时,folly::Vector
的设计也需要在多个方面进行权衡。
① 内存占用 (Memory Footprint) 与性能 (Performance):
动态数组为了保证高效的随机访问和快速的尾部添加,通常会预留一定的容量。这意味着即使向量中只存储了少量元素,也可能占用较大的内存空间。这是空间换时间的典型权衡。folly::Vector
在内存增长策略上需要权衡,选择合适的增长因子,既要避免频繁的内存重新分配,又要避免过度浪费内存。
② 通用性 (Generality) 与特定场景优化 (Specific Scenario Optimization):
std::vector
旨在提供通用的动态数组容器,适用于各种场景。而 folly::Vector
可能会更侧重于 Facebook 内部的特定应用场景进行优化。这种优化可能会在某些通用场景下带来额外的开销,或者牺牲一定的通用性。例如,folly::Vector
可能会针对高并发、低延迟的服务器环境进行优化,但这可能不适用于所有类型的应用。
③ 复杂性 (Complexity) 与性能 (Performance):
为了追求极致的性能,folly::Vector
的实现可能会比 std::vector
更复杂。例如,为了实现更高效的内存分配,可能需要使用更复杂的内存分配器。这种复杂性会增加代码的维护成本和理解难度。设计者需要在性能提升和代码复杂性之间进行权衡。
④ 异常安全 (Exception Safety) 与性能 (Performance):
异常安全是 C++ 编程中非常重要的考量。然而,在某些极端追求性能的场景下,为了减少开销,可能会牺牲一定的异常安全性。folly::Vector
在异常安全方面通常会遵循强异常安全保证或基本异常安全保证,但在某些特定的操作中,为了性能可能会有所妥协。需要在异常安全和性能之间找到平衡点。
7.2.3 folly::Vector 相对于 std::vector 的权衡 (Trade-offs of folly::Vector Compared to std::vector)
folly::Vector
通常被认为是 std::vector
的一个高性能替代品。但这种高性能并非免费午餐,而是通过一些权衡换来的。
① 潜在的性能提升 (Potential Performance Gains):
在某些特定场景下,folly::Vector
可能比 std::vector
具有更高的性能,例如:
⚝ 更快的内存分配:如果 folly::Vector
使用了更高效的内存分配器,那么在频繁进行内存分配和释放的场景下,性能可能会优于 std::vector
。
⚝ 针对特定硬件或平台的优化:folly::Vector
可能会针对 Facebook 内部使用的硬件或平台进行优化,从而在这些平台上获得更好的性能。
② 增加的依赖 (Increased Dependencies):
folly::Vector
是 folly
库的一部分,使用 folly::Vector
需要引入 folly
库的依赖。folly
库本身是一个大型的 C++ 库,包含了大量的组件。引入 folly
库可能会增加项目的编译时间和二进制文件大小。而 std::vector
是 C++ 标准库的一部分,无需额外依赖。
③ 学习成本 (Learning Curve):
虽然 folly::Vector
的 API 与 std::vector
兼容,但要深入理解 folly::Vector
的设计思想和性能特点,仍然需要一定的学习成本。特别是当需要进行性能调优或源码分析时,需要对 folly
库有一定的了解。对于初学者来说,std::vector
可能更容易上手。
④ 维护成本 (Maintenance Cost):
使用第三方库总是会带来一定的维护成本。当 folly
库升级或出现 bug 时,需要及时更新和修复。而 std::vector
作为标准库的一部分,通常具有更好的稳定性和更广泛的社区支持。
总结:
folly::Vector
的设计原则是高性能、兼容 std::vector
、利用现代 C++ 特性以及兼顾可扩展性和可维护性。其设计权衡主要体现在内存占用与性能、通用性与特定场景优化、复杂性与性能以及异常安全与性能之间。相对于 std::vector
,folly::Vector
在某些场景下可能提供更高的性能,但也引入了额外的依赖和学习成本。选择使用 folly::Vector
还是 std::vector
,需要根据具体的应用场景、性能需求以及项目维护成本等因素进行综合考虑。
7.3 与其他容器的对比分析:std::vector, std::deque, std::list (Comparative Analysis with Other Containers: std::vector, std::deque, std::list)
folly::Vector
,std::vector
, std::deque
, 和 std::list
都是 C++ 标准库或 folly
库中常用的序列容器。它们各自具有不同的数据结构和性能特点,适用于不同的应用场景。本节将对这四种容器进行对比分析,帮助读者理解它们的优缺点,并选择最合适的容器。
7.3.1 数据结构与内存布局 (Data Structure and Memory Layout)
① std::vector
和 folly::Vector
:
⚝ 数据结构:动态数组(Dynamic Array)。
⚝ 内存布局:元素存储在连续的内存块中。
⚝ 特点:
▮▮▮▮⚝ 随机访问速度快(O(1))。
▮▮▮▮⚝ 尾部添加和删除元素效率高(摊销 O(1))。
▮▮▮▮⚝ 中间或头部插入和删除元素效率低(O(n))。
▮▮▮▮⚝ 内存连续,缓存友好。
② std::deque
(Double-ended Queue):
⚝ 数据结构:双端队列。通常实现为分段连续的内存块(例如,多个小的动态数组)。
⚝ 内存布局:逻辑上连续,物理上可能不完全连续。
⚝ 特点:
▮▮▮▮⚝ 头部和尾部添加和删除元素效率高(摊销 O(1))。
▮▮▮▮⚝ 随机访问速度相对较慢,但仍然是常数时间复杂度(O(1),但常数项较大)。
▮▮▮▮⚝ 中间插入和删除元素效率较低(O(n))。
▮▮▮▮⚝ 内存分段,缓存局部性可能不如 std::vector
。
③ std::list
(Doubly Linked List):
⚝ 数据结构:双向链表(Doubly Linked List)。
⚝ 内存布局:元素在内存中分散存储,通过指针链接。
⚝ 特点:
▮▮▮▮⚝ 任意位置插入和删除元素效率高(O(1))。
▮▮▮▮⚝ 随机访问速度慢(O(n))。
▮▮▮▮⚝ 内存不连续,缓存不友好。
▮▮▮▮⚝ 额外存储指针,内存开销较大。
7.3.2 性能对比 (Performance Comparison)
性能对比主要从以下几个方面进行:
① 随机访问 (Random Access):
⚝ std::vector
和 folly::Vector
: 最快,O(1)。由于内存连续,缓存命中率高。
⚝ std::deque
: 较快,O(1),但常数项比 std::vector
大。需要额外的索引计算。
⚝ std::list
: 最慢,O(n)。需要遍历链表才能找到指定位置的元素。
② 顺序访问 (Sequential Access):
⚝ std::vector
和 folly::Vector
: 非常快,迭代器自增操作高效。
⚝ std::deque
: 较快,迭代器操作略微复杂,但仍然高效。
⚝ std::list
: 较快,迭代器自增操作涉及指针跳转,但仍然是常数时间。
③ 尾部插入/删除 (Insertion/Deletion at the Back):
⚝ std::vector
和 folly::Vector
: 摊销 O(1)。偶尔需要重新分配内存,但平均性能很高。
⚝ std::deque
: 摊销 O(1)。头部和尾部插入删除都很快。
⚝ std::list
: O(1)。尾部插入删除非常快。
④ 头部插入/删除 (Insertion/Deletion at the Front):
⚝ std::deque
: 摊销 O(1)。头部插入删除高效是 std::deque
的优势。
⚝ std::list
: O(1)。头部插入删除也非常快。
⚝ std::vector
和 folly::Vector
: O(n)。需要移动大量元素,效率很低。
⑤ 中间插入/删除 (Insertion/Deletion in the Middle):
⚝ std::list
: O(1)。只需要修改指针,效率很高。
⚝ std::deque
: O(n)。需要移动部分元素。
⚝ std::vector
和 folly::Vector
: O(n)。需要移动大量元素,效率很低。
⑥ 内存占用 (Memory Overhead):
⚝ std::vector
和 folly::Vector
: 相对较低。主要内存开销是存储元素的连续内存块。
⚝ std::deque
: 中等。除了元素内存,还需要维护分段内存块的索引。
⚝ std::list
: 较高。每个元素都需要额外的指针来维护链表结构。
7.3.3 应用场景选择 (Application Scenario Selection)
根据不同容器的特点和性能,选择合适的容器至关重要。
① std::vector
和 folly::Vector
:
⚝ 适用场景:
▮▮▮▮⚝ 需要频繁随机访问元素的场景。
▮▮▮▮⚝ 元素数量动态增长,但主要在尾部添加和删除的场景。
▮▮▮▮⚝ 对内存连续性要求高,需要缓存友好的场景。
▮▮▮▮⚝ 作为默认的序列容器选择,通用性强。
⚝ 不适用场景:
▮▮▮▮⚝ 频繁在头部或中间位置插入和删除元素的场景。
② std::deque
:
⚝ 适用场景:
▮▮▮▮⚝ 需要在头部和尾部都高效地进行插入和删除操作的场景,例如双端队列。
▮▮▮▮⚝ 偶尔需要在中间位置插入和删除元素,但频率不高。
▮▮▮▮⚝ 对内存连续性要求不高,但仍需要较好的顺序访问性能。
⚝ 不适用场景:
▮▮▮▮⚝ 对随机访问性能要求极高的场景,std::vector
和 folly::Vector
可能更优。
▮▮▮▮⚝ 频繁在中间位置插入和删除元素的场景,std::list
可能更优。
③ std::list
:
⚝ 适用场景:
▮▮▮▮⚝ 需要频繁在任意位置(包括头部、尾部和中间)插入和删除元素的场景。
▮▮▮▮⚝ 对随机访问性能要求不高,主要进行顺序访问或迭代的场景。
▮▮▮▮⚝ 元素数量变化频繁,且插入删除操作占主导的场景。
⚝ 不适用场景:
▮▮▮▮⚝ 需要频繁随机访问元素的场景。
▮▮▮▮⚝ 对内存占用敏感的场景,std::vector
和 std::deque
可能更节省内存。
▮▮▮▮⚝ 对缓存局部性要求高的场景。
7.3.4 容器选择建议 (Container Selection Recommendations)
① 默认选择 std::vector
或 folly::Vector
:
在大多数情况下,std::vector
或 folly::Vector
都是不错的默认选择。它们提供了良好的随机访问性能和尾部操作性能,并且内存连续,缓存友好。如果对性能有较高要求,可以考虑 folly::Vector
。
② 需要高效的头部和尾部操作选择 std::deque
:
当需要在头部和尾部频繁进行插入和删除操作时,std::deque
是一个很好的选择。例如,实现消息队列、任务调度队列等场景。
③ 需要频繁的中间插入删除选择 std::list
:
当需要在容器的任意位置频繁进行插入和删除操作,且对随机访问性能要求不高时,std::list
是最佳选择。例如,实现文本编辑器的行编辑、操作历史记录等场景。
④ 根据实际场景进行性能测试:
在关键性能路径上,最好针对实际应用场景进行性能测试,比较不同容器的性能表现,选择最合适的容器。理论分析和经验法则固然重要,但实际测试数据更具有指导意义。
总结:
std::vector
, folly::Vector
, std::deque
, 和 std::list
各有优缺点,适用于不同的应用场景。std::vector
和 folly::Vector
适用于需要高效随机访问和尾部操作的场景;std::deque
适用于需要高效头部和尾部操作的场景;std::list
适用于需要高效中间插入和删除操作的场景。选择合适的容器需要综合考虑应用场景的特点、性能需求以及内存占用等因素。在实际开发中,应根据具体情况进行选择,并在必要时进行性能测试,以确保选择的容器能够满足性能要求。
END_OF_CHAPTER
8. chapter 8: 最佳实践与常见问题解答 (Best Practices and Common Questions & Answers)
8.1 folly::Vector 使用的最佳实践 (Best Practices for Using folly::Vector)
使用 folly::Vector
,如同使用任何强大的工具一样,遵循最佳实践能够显著提升代码的效率、可读性和可维护性。以下是一些关于 folly::Vector
使用的最佳实践建议,旨在帮助读者充分利用其优势,并避免潜在的陷阱。
① 明确使用场景:
folly::Vector
并非在所有场景下都是 std::vector
的理想替代品。它在某些特定场景下,例如需要高度优化的内存分配策略或与 folly
库的其他组件协同工作时,才能发挥其最大优势。因此,在选择使用 folly::Vector
之前,务必评估其是否真的能为你的应用带来性能提升或功能增强。如果仅仅是简单的动态数组需求,std::vector
可能已经足够满足,并且具有更好的跨平台兼容性。
② 合理预分配内存:
与 std::vector
类似,folly::Vector
的动态扩容涉及到内存的重新分配和数据的拷贝,这可能会带来显著的性能开销。如果你能预先估计向量可能达到的最大容量,使用 reserve()
函数预先分配足够的内存是一个非常好的实践。这可以减少甚至消除因动态扩容而产生的性能抖动,尤其是在对性能敏感的应用中。
1 | folly::Vector<int> vec; |
2 | vec.reserve(1000); // 预分配 1000 个元素的空间 |
3 | for (int i = 0; i < 1000; ++i) { |
4 | vec.push_back(i); // 避免多次重新分配内存 |
5 | } |
③ 利用移动语义:
folly::Vector
充分利用了 C++11 引入的移动语义。在向 folly::Vector
中添加元素,或者在函数间传递 folly::Vector
对象时,尽可能使用移动操作(例如 std::move
)来避免不必要的拷贝,尤其是在向量存储的是大型对象时。
1 | folly::Vector<std::string> vec1; |
2 | std::string str = "large string"; |
3 | vec1.push_back(std::move(str)); // 移动而非拷贝 str 的内容 |
4 | folly::Vector<std::string> vec2 = std::move(vec1); // 移动构造,避免深拷贝 |
④ 避免不必要的拷贝:
在函数参数传递、返回值以及对象赋值等场景中,要时刻注意避免不必要的 folly::Vector
拷贝。使用引用传递(&
或 const&
)作为函数参数,或者使用移动语义返回 folly::Vector
对象,可以有效减少拷贝开销。
1 | void processVector(const folly::Vector<int>& vec) { // 使用常量引用,避免拷贝 |
2 | // ... 处理 vec |
3 | } |
4 | folly::Vector<int> createVector() { |
5 | folly::Vector<int> vec; |
6 | // ... 填充 vec |
7 | return vec; // 返回时会发生移动,而非拷贝 |
8 | } |
⑤ 审慎使用 emplace_back
:
emplace_back
允许直接在 folly::Vector
容器的末尾构造元素,避免了先构造临时对象再拷贝或移动到容器中的过程。对于构造开销较大的对象,emplace_back
可以带来性能提升。然而,emplace_back
的语法相对复杂,需要根据元素的构造函数参数进行调用。在简单类型或移动构造代价较小的场景下,push_back
可能更简洁易用。
1 | folly::Vector<std::pair<int, std::string>> vec; |
2 | vec.emplace_back(1, "value"); // 直接在容器内构造 pair 对象 |
⑥ 关注异常安全性:
在使用 folly::Vector
进行元素操作时,要考虑异常安全性。例如,在复杂的插入或删除操作中,如果操作过程中抛出异常,需要确保程序的状态仍然是有效的,避免资源泄露或数据损坏。folly::Vector
提供了基本的异常安全性保证,但在自定义操作中仍需谨慎处理。
⑦ 结合 folly
库的其他组件:
folly::Vector
通常与 folly
库的其他组件(如 folly::Range
、folly::Algorithms
等)配合使用,可以发挥更大的威力。例如,可以使用 folly::Range
来方便地遍历 folly::Vector
的一部分元素,或者使用 folly::Algorithms
中提供的算法来高效地处理 folly::Vector
中的数据。
⑧ 性能测试与基准测试:
最佳实践并非一成不变,具体的性能优化策略需要根据实际的应用场景和性能瓶颈来调整。在对 folly::Vector
进行性能优化时,务必进行充分的性能测试和基准测试,以验证优化措施的有效性,并避免过度优化。可以使用 folly
库提供的基准测试工具来进行性能评估。
⑨ 代码审查与团队协作:
在团队开发中,代码审查是确保代码质量和遵循最佳实践的重要环节。对于使用 folly::Vector
的代码,进行代码审查可以帮助发现潜在的性能问题、错误用法和不规范的代码风格,促进团队成员之间的知识共享和技能提升。
遵循以上最佳实践,可以帮助开发者更加高效、安全地使用 folly::Vector
,充分发挥其性能优势,构建高质量的 C++ 应用。
8.2 常见错误与陷阱 (Common Errors and Pitfalls)
即使是经验丰富的 C++ 开发者,在使用 folly::Vector
时也可能会遇到一些常见的错误和陷阱。了解这些潜在的问题,可以帮助我们避免犯同样的错误,提高代码的健壮性和可靠性。
① 下标越界访问:
与 std::vector
一样,folly::Vector
的下标访问运算符 []
不进行边界检查。如果使用超出有效索引范围的下标访问元素,会导致未定义行为,可能引发程序崩溃或数据损坏。为了安全地访问元素,应该使用 at()
函数,它会在越界访问时抛出 std::out_of_range
异常。
1 | folly::Vector<int> vec = {1, 2, 3}; |
2 | // int value = vec[5]; // 错误:下标越界,未定义行为 |
3 | int value = vec.at(5); // 正确:抛出 std::out_of_range 异常 |
② 迭代器失效:
在对 folly::Vector
进行插入或删除操作时,可能会导致迭代器失效。例如,如果在循环中使用迭代器遍历 folly::Vector
,并在循环体内进行了插入或删除操作,那么迭代器可能会变得无效,导致程序崩溃或逻辑错误。要避免迭代器失效,需要仔细考虑迭代器的生命周期,并在必要时重新获取迭代器。
1 | folly::Vector<int> vec = {1, 2, 3, 4, 5}; |
2 | for (auto it = vec.begin(); it != vec.end(); /* 循环体内控制迭代器递增 */) { |
3 | if (*it % 2 == 0) { |
4 | it = vec.erase(it); // erase 返回指向被删除元素之后元素的迭代器 |
5 | } else { |
6 | ++it; |
7 | } |
8 | } |
③ 忘记 reserve()
预分配内存:
在已知 folly::Vector
大致容量的情况下,忘记使用 reserve()
预分配内存是一个常见的性能陷阱。频繁的动态扩容会导致内存重新分配和数据拷贝,降低程序性能。特别是在循环中大量添加元素时,预分配内存尤为重要。
1 | folly::Vector<int> vec; // 没有预分配内存 |
2 | for (int i = 0; i < 10000; ++i) { |
3 | vec.push_back(i); // 可能多次重新分配内存 |
4 | } |
5 | folly::Vector<int> vec2; |
6 | vec2.reserve(10000); // 预分配内存 |
7 | for (int i = 0; i < 10000; ++i) { |
8 | vec2.push_back(i); // 避免多次重新分配内存 |
9 | } |
④ 深拷贝与浅拷贝混淆:
当 folly::Vector
存储的是指针或包含动态分配内存的对象时,需要特别注意深拷贝和浅拷贝的区别。默认的拷贝构造函数和赋值运算符执行的是浅拷贝,即只拷贝指针的值,而不拷贝指针指向的内存。如果需要深拷贝,即拷贝指针指向的内存,则需要自定义拷贝构造函数和赋值运算符。
1 | class MyObject { |
2 | public: |
3 | int* data; |
4 | MyObject(int value) : data(new int(value)) {} |
5 | ~MyObject() { delete data; } |
6 | // 拷贝构造函数(深拷贝) |
7 | MyObject(const MyObject& other) : data(new int(*other.data)) {} |
8 | // 赋值运算符(深拷贝) |
9 | MyObject& operator=(const MyObject& other) { |
10 | if (this != &other) { |
11 | delete data; |
12 | data = new int(*other.data); |
13 | } |
14 | return *this; |
15 | } |
16 | // 移动构造函数 (可选,用于优化性能) |
17 | MyObject(MyObject&& other) noexcept : data(other.data) { |
18 | other.data = nullptr; |
19 | } |
20 | // 移动赋值运算符 (可选,用于优化性能) |
21 | MyObject& operator=(MyObject&& other) noexcept { |
22 | if (this != &other) { |
23 | delete data; |
24 | data = other.data; |
25 | other.data = nullptr; |
26 | } |
27 | return *this; |
28 | } |
29 | }; |
30 | folly::Vector<MyObject> vec1; |
31 | vec1.emplace_back(10); |
32 | folly::Vector<MyObject> vec2 = vec1; // 调用拷贝构造函数(深拷贝) |
⑤ 错误地使用 shrink_to_fit()
:
shrink_to_fit()
函数试图释放 folly::Vector
中未使用的容量,以减少内存占用。然而,shrink_to_fit()
只是一个请求,具体的实现可能并不总是能够完全释放多余的容量。此外,频繁调用 shrink_to_fit()
可能会导致性能下降,因为它可能涉及到内存的重新分配和数据拷贝。因此,应该谨慎使用 shrink_to_fit()
,只有在确实需要减少内存占用,并且对性能影响有充分评估的情况下才使用。
⑥ 在多线程环境下的并发访问:
folly::Vector
本身不是线程安全的。在多线程环境下,如果多个线程同时访问或修改同一个 folly::Vector
对象,可能会导致数据竞争和未定义行为。为了保证线程安全,需要使用互斥锁、原子操作或其他同步机制来保护对 folly::Vector
的并发访问。
⑦ 过度依赖 folly::Vector
的特殊优化:
folly::Vector
针对某些特定场景进行了优化,例如小对象优化等。然而,过度依赖这些特殊优化可能会导致代码的可移植性降低。如果代码需要在不同的平台或编译器上运行,应该尽量避免过度依赖 folly::Vector
的特定实现细节,而应该关注其通用的接口和功能。
⑧ 忽略编译错误和警告:
编译器产生的错误和警告信息通常是代码中潜在问题的指示。在使用 folly::Vector
时,应该认真对待编译错误和警告,及时修复代码中的问题。例如,类型不匹配、未初始化的变量、潜在的内存泄漏等问题都可能通过编译器的警告信息暴露出来。
了解并避免这些常见错误和陷阱,可以帮助开发者更加熟练地使用 folly::Vector
,编写出更加健壮、高效的 C++ 代码。
8.3 性能调优技巧 (Performance Tuning Tips)
folly::Vector
作为一个高性能的容器,已经做了很多优化。然而,在特定的应用场景下,我们仍然可以通过一些技巧来进一步提升其性能。以下是一些 folly::Vector
的性能调优技巧,旨在帮助读者榨干 folly::Vector
的最后一滴性能。
① 选择合适的内存分配器:
folly::Vector
允许自定义内存分配器。默认情况下,它使用标准的 std::allocator
。在某些高性能场景下,使用更高效的内存分配器,例如 jemalloc
、tcmalloc
或 mimalloc
,可以显著提升内存分配和释放的性能,从而间接提升 folly::Vector
的整体性能。可以通过全局替换或为 folly::Vector
指定自定义分配器来使用这些高性能分配器。
1 | |
2 | |
3 | int main() { |
4 | using JemallocVector = folly::Vector<int, folly::JemallocAllocator<int>>; |
5 | JemallocVector vec; // 使用 jemalloc 分配器 |
6 | // ... 使用 vec |
7 | return 0; |
8 | } |
② 利用移动语义减少拷贝:
移动语义是 C++11 引入的重要特性,可以显著减少不必要的对象拷贝开销。在向 folly::Vector
中添加元素,或者在函数间传递 folly::Vector
对象时,务必充分利用移动语义。使用 std::move
将左值转换为右值引用,可以触发移动构造函数或移动赋值运算符,从而避免深拷贝。
1 | folly::Vector<std::string> vec; |
2 | std::string largeString = "very long string..."; |
3 | vec.push_back(std::move(largeString)); // 移动而非拷贝 |
4 | folly::Vector<std::string> anotherVec = std::move(vec); // 移动构造 |
③ 避免不必要的内存重新分配:
folly::Vector
的动态扩容涉及到内存的重新分配和数据的拷贝,这是性能开销的主要来源之一。通过预先估计 folly::Vector
的容量,并使用 reserve()
函数预分配足够的内存,可以有效减少甚至消除动态扩容的次数,从而提升性能。尤其是在循环中大量添加元素时,预分配内存的效果非常明显。
1 | folly::Vector<int> vec; |
2 | vec.reserve(10000); // 预分配 10000 个元素的空间 |
3 | for (int i = 0; i < 10000; ++i) { |
4 | vec.push_back(i); // 避免多次重新分配内存 |
5 | } |
④ 使用 emplace_back
原位构造对象:
emplace_back
允许直接在 folly::Vector
容器的末尾构造元素,避免了先构造临时对象再拷贝或移动到容器中的过程。对于构造开销较大的对象,emplace_back
可以带来性能提升。尤其是在循环中频繁添加复杂对象时,emplace_back
的优势更加明显。
1 | folly::Vector<std::complex<double>> complexVec; |
2 | for (int i = 0; i < 1000; ++i) { |
3 | complexVec.emplace_back(i, i * 2); // 原位构造 complex 对象 |
4 | } |
⑤ 批量操作优于单元素操作:
对于某些操作,例如插入、删除等,批量操作通常比单元素操作效率更高。folly::Vector
提供了一些批量操作的接口,例如 insert
的范围版本、erase
的范围版本等。在需要插入或删除多个元素时,优先考虑使用批量操作,可以减少函数调用开销和内存操作次数。
1 | folly::Vector<int> vec1 = {1, 2, 3}; |
2 | folly::Vector<int> vec2 = {4, 5, 6}; |
3 | vec1.insert(vec1.end(), vec2.begin(), vec2.end()); // 批量插入 |
⑥ 利用缓存局部性:
folly::Vector
在内存中是连续存储的,这有利于利用 CPU 缓存的局部性原理。在访问 folly::Vector
中的元素时,顺序访问通常比随机访问效率更高,因为顺序访问可以更好地利用缓存。因此,在算法设计和数据访问模式上,尽量考虑缓存局部性,可以提升程序性能。
1 | folly::Vector<int> vec(1000000); |
2 | // 顺序访问 |
3 | for (size_t i = 0; i < vec.size(); ++i) { |
4 | vec[i] += 1; // 顺序访问,缓存友好 |
5 | } |
6 | // 随机访问 (性能可能较差) |
7 | std::random_device rd; |
8 | std::mt19937 gen(rd()); |
9 | std::uniform_int_distribution<> distrib(0, vec.size() - 1); |
10 | for (int i = 0; i < 100000; ++i) { |
11 | vec[distrib(gen)] += 1; // 随机访问,缓存利用率低 |
12 | } |
⑦ 避免不必要的拷贝和赋值:
在函数参数传递、返回值以及对象赋值等场景中,要时刻注意避免不必要的 folly::Vector
拷贝和赋值操作。使用引用传递(&
或 const&
)作为函数参数,或者使用移动语义返回 folly::Vector
对象,可以有效减少拷贝和赋值开销。
⑧ 使用 shrink_to_fit()
释放多余容量:
如果 folly::Vector
在使用过程中分配了大量的内存,但在后续使用中只需要较小的容量,可以考虑使用 shrink_to_fit()
函数释放多余的容量,减少内存占用。但这可能会带来一定的性能开销,需要权衡内存占用和性能之间的平衡。
1 | folly::Vector<int> vec; |
2 | vec.reserve(10000); |
3 | // ... 添加少量元素 |
4 | vec.shrink_to_fit(); // 释放多余容量 |
⑨ 性能测试和基准测试:
性能调优是一个迭代的过程,需要通过实际的性能测试和基准测试来验证优化效果。在进行性能调优时,务必进行充分的性能测试和基准测试,找出性能瓶颈,并针对瓶颈进行优化。可以使用 folly
库提供的基准测试工具来进行性能评估。
⑩ 编译器优化选项:
编译器优化选项对程序性能有重要影响。在编译使用 folly::Vector
的代码时,应该启用编译器优化选项,例如 -O2
或 -O3
,以充分发挥编译器的优化能力,提升程序性能。
1 | g++ -O3 your_code.cpp -o your_program |
通过应用这些性能调优技巧,并结合实际的应用场景进行性能测试和分析,可以最大限度地提升 folly::Vector
的性能,构建高性能的 C++ 应用。
8.4 folly::Vector 未来发展趋势展望 (Future Development Trends of folly::Vector)
folly::Vector
作为 folly
库中的重要组件,其发展方向与 folly
库以及整个 C++ 生态系统的发展趋势密切相关。展望未来,folly::Vector
可能会在以下几个方面持续发展和演进:
① 持续的性能优化:
性能一直是 folly::Vector
的核心优势之一。未来,folly::Vector
可能会继续在性能优化方面进行探索,例如:
▮▮▮▮⚝ 更先进的内存分配策略:研究和引入更高效的内存分配算法,例如针对特定场景的定制化分配器,或者与操作系统更紧密结合的内存管理机制。
▮▮▮▮⚝ SIMD 指令优化:利用 SIMD (Single Instruction, Multiple Data) 指令集,对 folly::Vector
的常见操作(例如元素拷贝、填充、查找等)进行并行化加速,进一步提升数据处理效率。
▮▮▮▮⚝ NUMA (Non-Uniform Memory Access) 感知优化:在 NUMA 架构的系统中,优化 folly::Vector
的内存分配和访问模式,减少跨 NUMA 节点的内存访问延迟,提升多核系统的性能。
② 与 C++ 标准的对齐与融合:
C++ 标准在不断发展演进,新的 C++ 标准(例如 C++20、C++23 及更高版本)引入了许多新的语言特性和库组件。folly::Vector
可能会积极跟进 C++ 标准的发展,与 C++ 标准库进行对齐和融合,例如:
▮▮▮▮⚝ 采纳新的 C++ 标准特性:利用 C++20 的 Concepts、Ranges 等新特性,改进 folly::Vector
的接口设计和实现,提升代码的安全性、可读性和可维护性。
▮▮▮▮⚝ 与标准库算法的更好集成:加强 folly::Vector
与 C++ 标准库算法的兼容性和互操作性,例如支持 C++20 Ranges 库,使得可以使用 Ranges 库的算法更方便地操作 folly::Vector
。
▮▮▮▮⚝ 考虑将 folly::Vector
的优秀特性反哺到 C++ 标准库:如果 folly::Vector
中出现了一些被证明非常优秀的特性或优化,可能会考虑将其提案到 C++ 标准委员会,推动其成为 C++ 标准的一部分,惠及更广泛的 C++ 开发者。
③ 功能增强与扩展:
除了性能优化和标准对齐,folly::Vector
也可能会在功能方面进行增强和扩展,以满足更多应用场景的需求,例如:
▮▮▮▮⚝ 支持异构存储:考虑支持将 folly::Vector
的部分数据存储在非主内存介质上(例如 NVMe SSD、GPU 显存等),以应对大数据量和高性能计算的需求。
▮▮▮▮⚝ 提供更丰富的 API:增加一些实用的 API,例如更高效的查找、排序、去重等操作,或者针对特定数据类型的优化操作。
▮▮▮▮⚝ 与其他 folly
库组件的更紧密集成:进一步加强 folly::Vector
与 folly
库中其他组件(例如 folly::ConcurrentSkipList
、folly::FBString
等)的集成,构建更完善的 folly
生态系统。
④ 更好的跨平台支持:
folly
库最初主要在 Linux 平台上开发和使用。未来,folly::Vector
可能会加强对其他平台(例如 Windows、macOS 等)的支持,提升跨平台兼容性,使得更多的开发者可以在不同的平台上使用 folly::Vector
。
⑤ 社区驱动的演进:
folly
库是一个开源项目,其发展离不开社区的贡献和参与。未来,folly::Vector
的发展将更加依赖社区的力量,包括:
▮▮▮▮⚝ 接受社区的贡献:积极接受来自社区的代码贡献、bug 报告、功能建议等,共同推动 folly::Vector
的发展。
▮▮▮▮⚝ 加强社区交流与合作:通过邮件列表、论坛、GitHub Issues 等渠道,加强与社区的交流与合作,了解用户的需求和痛点,共同探讨 folly::Vector
的未来发展方向。
▮▮▮▮⚝ 鼓励社区参与测试与反馈:鼓励社区用户参与 folly::Vector
的测试和使用,提供反馈意见,帮助发现和解决潜在的问题,提升 folly::Vector
的质量和稳定性。
总而言之,folly::Vector
的未来发展将是性能优化、标准对齐、功能增强、跨平台支持和社区驱动等多方面因素共同作用的结果。我们有理由相信,folly::Vector
将会继续保持其高性能和先进性,并在未来的 C++ 开发领域发挥越来越重要的作用。
附录 A: folly 官方文档与社区资源 (Official Documentation and Community Resources of folly)
为了更深入地学习和使用 folly::Vector
以及 folly
库的其他组件,查阅官方文档和利用社区资源是非常重要的途径。以下是一些关键的 folly
官方文档和社区资源链接,供读者参考:
① folly
官方 GitHub 仓库:
▮▮▮▮⚝ 链接:https://github.com/facebook/folly
▮▮▮▮⚝ 描述:这是 folly
库的官方代码仓库,包含了最新的源代码、构建脚本、示例代码、以及详细的 README 文档。在这里可以获取到最权威的 folly
信息,包括 folly::Vector
的最新代码实现。
② folly
官方文档 (Doxygen):
▮▮▮▮⚝ 链接:通常在 folly
GitHub 仓库的 folly/docs
目录下,或者可以通过构建 folly
库后生成。
▮▮▮▮⚝ 描述:官方文档使用 Doxygen 工具生成,包含了 folly
库所有组件的详细 API 文档,包括类、函数、宏等的说明、参数、返回值、用法示例等。是深入了解 folly::Vector
API 的必备资源。
③ folly
官方教程和示例:
▮▮▮▮⚝ 链接:folly
GitHub 仓库的 folly/example
目录下,以及一些博客文章和技术分享。
▮▮▮▮⚝ 描述:官方提供了一些教程和示例代码,演示了 folly
库的各种组件的使用方法,包括 folly::Vector
的基本操作和高级应用。通过学习这些示例,可以更快地上手 folly::Vector
。
④ folly
邮件列表或论坛:
▮▮▮▮⚝ 链接:通常在 folly
GitHub 仓库的 README 文档中可以找到相关链接。
▮▮▮▮⚝ 描述:folly
社区通常会设立邮件列表或论坛,供开发者交流问题、分享经验、提出建议等。在这里可以向 folly
社区提问,获取帮助,也可以参与社区讨论,了解 folly
的最新动态。
⑤ Stack Overflow 等技术问答网站:
▮▮▮▮⚝ 链接:https://stackoverflow.com/questions/tagged/folly (Stack Overflow 上关于 folly
的问题)
▮▮▮▮⚝ 描述:Stack Overflow 等技术问答网站上有大量的关于 folly
的问题和解答。可以通过搜索关键词 “folly”、“folly::Vector” 等,找到可能遇到的问题的解决方案,或者向社区提问。
⑥ folly
相关的博客文章和技术分享:
▮▮▮▮⚝ 链接:通过搜索引擎搜索 “folly tutorial”、“folly vector example”、“folly performance” 等关键词可以找到。
▮▮▮▮⚝ 描述:许多技术博客和技术分享平台上有关于 folly
库的介绍、教程、性能分析、最佳实践等文章。这些文章通常以更通俗易懂的方式讲解 folly
的使用方法和技巧,是学习 folly::Vector
的有益补充。
⑦ folly
源码阅读和分析:
▮▮▮▮⚝ 链接:folly
GitHub 仓库的源代码。
▮▮▮▮⚝ 描述:对于有一定 C++ 基础和容器原理知识的读者,阅读 folly::Vector
的源码是深入理解其实现原理、设计思想和性能优化的最佳方式。通过源码阅读,可以学习到很多高级的 C++ 编程技巧和系统设计思想。
通过充分利用以上官方文档和社区资源,读者可以更全面、深入地学习和掌握 folly::Vector
,并在实际项目开发中更加得心应手。
附录 B: C++ 容器相关学习资源 (Learning Resources for C++ Containers)
folly::Vector
是 C++ 容器大家族中的一员。为了更好地理解 folly::Vector
的设计思想、应用场景和性能特点,系统地学习 C++ 容器的相关知识是非常有益的。以下是一些推荐的 C++ 容器学习资源,涵盖了书籍、在线文档、教程和视频等方面,适合不同层次的读者:
① 书籍:
▮▮▮▮⚝ 《Effective STL》 (Scott Meyers):
▮▮▮▮▮▮▮▮⚝ 描述:C++ STL 经典之作,深入讲解了 STL 容器、迭代器、算法等组件的使用技巧和最佳实践。虽然主要讲解的是标准 STL 容器,但其 principles 和 best practices 对于理解和使用 folly::Vector
同样适用。
▮▮▮▮⚝ 《C++ Primer》 (Stanley B. Lippman, Josée Lajoie, Barbara E. Moo):
▮▮▮▮▮▮▮▮⚝ 描述:C++ 入门经典教材,全面系统地介绍了 C++ 语言的各个方面,包括 STL 容器。对于初学者,可以通过本书系统地学习 C++ 容器的基础知识。
▮▮▮▮⚝ 《The C++ Standard Library: A Tutorial and Reference (2nd Edition)》 (Nicolai M. Josuttis):
▮▮▮▮▮▮▮▮⚝ 描述:C++ 标准库的权威参考书,详细介绍了 C++ 标准库的各个组件,包括容器、算法、迭代器、函数对象等。可以作为 C++ 容器的工具书查阅。
▮▮▮▮⚝ 《Modern C++ Design: Generic Programming and Design Patterns Applied》 (Andrei Alexandrescu):
▮▮▮▮▮▮▮▮⚝ 描述:深入探讨了 C++ 泛型编程和设计模式,其中大量使用了 STL 容器和算法。对于希望深入理解 C++ 容器和泛型编程的读者,这本书是不错的选择。
② 在线文档:
▮▮▮▮⚝ cppreference.com:
▮▮▮▮▮▮▮▮⚝ 链接:https://en.cppreference.com/w/cpp/container (C++ 容器相关文档)
▮▮▮▮▮▮▮▮⚝ 描述:C++ 语言和标准库的权威在线参考文档,包含了 C++ 标准库中所有容器的详细说明、API 文档、用法示例等。是学习 C++ 容器 API 的必备资源。
▮▮▮▮⚝ cplusplus.com:
▮▮▮▮▮▮▮▮⚝ 链接:http://www.cplusplus.com/reference/stl/ (C++ STL 容器参考)
▮▮▮▮▮▮▮▮⚝ 描述:另一个常用的 C++ 在线参考文档,也包含了 C++ 标准库容器的详细说明和示例。
③ 在线教程:
▮▮▮▮⚝ LearnCpp.com:
▮▮▮▮▮▮▮▮⚝ 链接:https://www.learncpp.com/
▮▮▮▮▮▮▮▮⚝ 描述:一个免费的 C++ 在线教程网站,提供了从入门到进阶的 C++ 教程,其中包含了 C++ 容器的章节。适合 C++ 初学者系统学习。
▮▮▮▮⚝ Coursera、edX、Udemy 等在线教育平台上的 C++ 课程:
▮▮▮▮▮▮▮▮⚝ 描述:这些平台上有许多高质量的 C++ 在线课程,通常会包含 C++ 容器的教学内容。可以通过搜索 “C++”、“STL”、“Containers” 等关键词找到相关课程。
④ 视频教程:
▮▮▮▮⚝ YouTube 上搜索 “C++ Containers”、“STL Tutorial” 等关键词:
▮▮▮▮▮▮▮▮⚝ 描述:YouTube 上有大量的 C++ 容器相关的视频教程,可以找到各种不同风格的讲解,例如入门教程、进阶技巧、性能分析等。
▮▮▮▮⚝ B站 (bilibili.com) 上搜索 “C++ 容器”、“STL 教程” 等关键词:
▮▮▮▮▮▮▮▮⚝ 描述:B站上也有很多中文的 C++ 容器视频教程,适合中文学习者。
⑤ 实践项目和代码示例:
▮▮▮▮⚝ GitHub 上搜索 “C++ STL examples”、“C++ containers usage” 等关键词:
▮▮▮▮▮▮▮▮⚝ 描述:通过阅读和学习开源项目中的 C++ 容器使用示例,可以更深入地理解 C++ 容器在实际项目中的应用。
▮▮▮▮⚝ LeetCode、HackerRank 等在线编程平台上的算法题:
▮▮▮▮▮▮▮▮⚝ 描述:这些平台上有大量的算法题,很多题目需要使用 C++ 容器来解决。通过刷题练习,可以提高 C++ 容器的实际应用能力。
通过结合以上各种学习资源,读者可以构建起完善的 C++ 容器知识体系,为更好地理解和使用 folly::Vector
打下坚实的基础。
附录 C: 常用调试技巧 (Common Debugging Techniques)
在 C++ 开发过程中,调试是不可避免的环节。掌握一些常用的调试技巧,可以帮助我们快速定位和解决代码中的问题,提高开发效率。以下是一些常用的 C++ 调试技巧,其中部分技巧也特别适用于调试使用 folly::Vector
的代码:
① 使用调试器 (Debugger):
▮▮▮▮⚝ GDB (GNU Debugger):
▮▮▮▮▮▮▮▮⚝ 描述:Linux 平台下最常用的命令行调试器,功能强大,可以进行断点设置、单步执行、查看变量值、调用堆栈分析等操作。是调试 C++ 代码的必备工具。
▮▮▮▮⚝ LLDB (LLVM Debugger):
▮▮▮▮▮▮▮▮⚝ 描述:macOS 和 iOS 平台下默认的调试器,也支持 Linux 和 Windows 平台。功能与 GDB 类似,但在某些方面(例如表达式求值、Python 脚本支持)更强大。
▮▮▮▮⚝ Visual Studio Debugger:
▮▮▮▮▮▮▮▮⚝ 描述:Windows 平台下 Visual Studio IDE 集成的调试器,图形界面友好,操作方便,功能完善。适合 Windows 平台 C++ 开发。
常用调试器操作:
▮▮▮▮⚝ 设置断点 (Breakpoint):在代码的特定行设置断点,程序执行到断点处会暂停,方便我们检查程序状态。
▮▮▮▮⚝ 单步执行 (Step Over, Step Into, Step Out):逐行执行代码,或者进入函数内部、跳出函数,帮助我们跟踪代码执行流程。
▮▮▮▮⚝ 查看变量值 (Watch Variables):在程序暂停时,查看变量的值,了解程序状态。
▮▮▮▮⚝ 调用堆栈 (Call Stack):查看函数调用关系,了解程序执行到当前位置的调用路径。
▮▮▮▮⚝ 条件断点 (Conditional Breakpoint):在满足特定条件时才触发断点,例如当某个变量的值满足特定条件时。
▮▮▮▮⚝ 数据断点 (Data Breakpoint):当某个内存地址的值被修改时触发断点,用于追踪内存错误。
② 打印调试信息 (Print Debugging):
▮▮▮▮⚝ std::cout
、std::cerr
:
▮▮▮▮▮▮▮▮⚝ 描述:使用 std::cout
或 std::cerr
输出调试信息到控制台,例如变量的值、程序执行路径等。是最简单、最常用的调试方法。
▮▮▮▮⚝ folly::fbstring::print()
、folly::dynamic::print()
等 folly
库提供的打印函数:
▮▮▮▮▮▮▮▮⚝ 描述:folly
库提供了一些更方便、更强大的打印函数,例如 folly::fbstring::print()
可以方便地打印 folly::fbstring
对象,folly::dynamic::print()
可以打印 folly::dynamic
对象。
打印调试信息技巧:
▮▮▮▮⚝ 使用条件编译 (#ifdef DEBUG
):将调试代码放在 #ifdef DEBUG
和 #endif
之间,在 Release 版本编译时可以关闭调试代码,避免性能影响。
▮▮▮▮⚝ 使用日志库 (Logging Library):使用专业的日志库(例如 glog
、spdlog
等)来管理调试信息,可以实现更灵活的日志输出控制、日志级别管理、日志文件输出等功能。
③ 使用断言 (Assertion):
▮▮▮▮⚝ assert()
宏:
▮▮▮▮▮▮▮▮⚝ 描述:assert()
宏用于在代码中插入断言,检查程序的状态是否符合预期。如果断言条件为假,程序会终止并输出错误信息。用于快速发现程序中的逻辑错误。
断言使用技巧:
▮▮▮▮⚝ 只用于检查程序内部的逻辑错误:断言不应该用于处理用户输入错误或外部环境异常等情况。
▮▮▮▮⚝ 在 Debug 版本启用,Release 版本禁用:断言通常只在 Debug 版本启用,Release 版本禁用,避免性能影响。
④ 内存错误检测工具:
▮▮▮▮⚝ Valgrind (Memcheck):
▮▮▮▮▮▮▮▮⚝ 描述:Linux 平台下最常用的内存错误检测工具,可以检测内存泄漏、越界访问、使用未初始化内存等内存错误。对于调试 C++ 内存相关问题非常有效。
▮▮▮▮⚝ AddressSanitizer (ASan):
▮▮▮▮▮▮▮▮⚝ 描述:一种快速的内存错误检测工具,由 LLVM/Clang 提供,也支持 GCC。可以检测内存越界、use-after-free、double-free 等内存错误。性能开销比 Valgrind 小,适合在测试环境中启用。
⑤ 静态代码分析工具:
▮▮▮▮⚝ Clang Static Analyzer:
▮▮▮▮▮▮▮▮⚝ 描述:Clang 编译器自带的静态代码分析工具,可以检查代码中潜在的 bug、代码风格问题、安全漏洞等。
▮▮▮▮⚝ Cppcheck:
▮▮▮▮▮▮▮▮⚝ 描述:一个开源的 C++ 静态代码分析工具,可以检测多种类型的代码错误,例如内存泄漏、空指针解引用、未使用的变量等。
⑥ 单元测试 (Unit Testing):
▮▮▮▮⚝ Google Test (gtest):
▮▮▮▮▮▮▮▮⚝ 描述:Google 开源的 C++ 单元测试框架,可以方便地编写和运行单元测试用例,验证代码的正确性。通过编写单元测试,可以在开发早期发现和修复 bug。
▮▮▮▮⚝ folly::test::FollyTest
:
▮▮▮▮▮▮▮▮⚝ 描述:folly
库提供的单元测试框架,基于 Google Test,并提供了一些额外的便利功能。
⑦ 代码审查 (Code Review):
▮▮▮▮⚝ 描述:通过团队成员之间的代码互相审查,可以发现代码中潜在的 bug、代码风格问题、性能问题等。代码审查是提高代码质量的有效手段。
⑧ 版本控制系统 (Version Control System):
▮▮▮▮⚝ Git:
▮▮▮▮▮▮▮▮⚝ 描述:使用 Git 等版本控制系统管理代码,可以方便地回溯代码历史版本,比较不同版本之间的代码差异,查找 bug 引入的commit。
掌握以上调试技巧,并根据具体的调试场景选择合适的工具和方法,可以有效地提高 C++ 代码的调试效率,快速解决问题,提升开发质量。在调试使用 folly::Vector
的代码时,这些通用调试技巧同样适用。
END_OF_CHAPTER