[笔记] C++容器基础之Vector| Kai@Codehubble
|
45
|
0
|
C++

1617 字
|
16 分钟

Vector

概述

Vector 是一个能够存放任意型别的动态数组

Vector 的数据结构和操作与数组 (array) 类似，在内存中的表现形式是一段地址连续的空间

Vector 与数组的区别在于，数组大小往往是定义时就固定的 (比如：char buffer [256])；Vector 支持动态空间大小调整，随着元素的加入，vector 内部会自动扩充内存空间

为了使用 vector，必须用 include 指令包含如下文件，并通过 std 命名空间去访问：

#include <vector>

int main() {
    std::vector v;
}

基础操作

创建Vector

常用方式 代码
创建一个 T 型别的空 vector std::vector<T> v;
创建一个容量是 n 的 T 型别的 vector std::vector<T> v(n);
创建一个容量是 n 的 T 型别的 vector，并且都初始化为 i std::vector<T> v(n, i);
创建一个已有 v 的拷贝 std::vector<T> copyOfV(v);
通过一个数组创建一个 vector int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; std::vector<int> v(array, array + 10);

向Vector添加元素

向vector添加元素的方法为调用其push_back函数，表示将元素添加至其尾部：

std::vector<std::wstring> v3;
for (std::size_t i = 0; i < 10; i++)
{
    std::wstringstream wss;
    wss << TEXT("String[") << i << TEXT("]");
    v3.push_back(wss.str());
}

判断vector是否为空，获取vector大小

  • 如果要判断 vector 是否为空则调用empty()函数。
  • 如果要获取 vector 大小则调用size()函数。
std::vector<std::wstring> v3;
bool isEmpty = v3.empty();

int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> v(array, array + 10);
std::size_t vSize = v.size();

访问vector中的元素

要访问中的元素，有两种方法：

  • 调用vector::at()
  • 调用vector::operator[]

两者的区别在于：

  • operator[]提供了类似数组的存取方式，但不做边界检查，可能越界，但访问效率更高
  • at()进行边界检查，如果访问越界则抛出exception，但访问效率不如operator[]
std::vector<std::wstring> v;
v.reserve(10);
for (std::size_t i = 0; i < 3; i++) {
  std::wstringstream wss;
  wss << TEXT("String[") << i << TEXT("]");
  v.push_back(wss.str());
}

try {
  std::wstring wsz1 = v[5]; // not bounds checked - will not throw
  std::wstring wsz2 = v.at(5); // bounds checked - will throw if out of range
} catch (const std::exception& ex) {
  Console::WriteLine(ex.what());
}

注：预留了 10 个wstring空间，push_back了 3 个，v[5]访问越界。

删除vector中的元素

假设一个 vector 由下列元素构成，我们的目标是要删除 vector 中所有含有 C++ 的字符串的元素：

std::vector<std::wstring> v;
v.push_back(TEXT("Standard Template Library"));
v.push_back(TEXT("The C++ Programming Language"));
v.push_back(TEXT("Windows Internals"));
v.push_back(TEXT("Programming Applications for Windows"));
v.push_back(TEXT("Design Patterns"));
v.push_back(TEXT("Effective C++"));
v.push_back(TEXT("More Effective C++"));

remove_if函数定义在algorithm中，故需include <algorithm>。

定义筛选器：一个一元函数对象 (unary_function)，关键在于重载operator()。

struct ContainsString : public std::unary_function<std::wstring, bool>
{
  ContainsString(const std::wstring& wszMatch) : m_wszMatch(wszMatch) {}
  bool operator() (const std::wstring& wszStringToMatch) const
  {
    return (wszStringToMatch.find(m_wszMatch) != -1);
  }

  std::wstring m_wszMatch;
};

在erase函数中调用remove_if执行删除：

v.erase(std::remove_if(
    v.begin(),
    v.end(),
    ContainsString(L"C++")
),
v.end());

std::unary_function 是 C++ 标准库中的一个基类模板，用于定义一元函数对象（只接受一个参数的函数对象）。它的主要作用是提供统一的类型定义，以便与 STL 算法（如 remove_if）配合使用。

在上述代码中，ContainsString 结构体 继承自 std::unary_function<std::wstring, bool>，其中：

  • 第一个模板参数 std::wstring 表示函数对象接受的参数类型
  • 第二个模板参数 bool 表示函数对象的返回值类型

继承自 std::unary_function 后，会自动获得两个成员类型定义：

  • argument_type：等同于第一个模板参数（即 std::wstring）
  • result_type：等同于第二个模板参数（即 bool）

这使得该函数对象能够满足 STL 算法对一元函数的类型要求，确保在使用 remove_if 等算法时类型匹配正确。

需要注意的是，在 C++11 及以后的标准中，std::unary_function 已被标记为 deprecated（弃用），推荐直接定义函数对象而不继承该基类，因为现代 STL 算法不再强制要求这种类型定义。但在一些 legacy 代码中仍会看到这种用法。

在C++以上可以使用如下方式：

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

int main() {
    // 使用初始化列表构造vector（C++11特性）
    std::vector<std::wstring> v = {
        L"Standard Template Library",
        L"The C++ Programming Language",
        L"Windows Internals",
        L"Programming Applications for Windows",
        L"Design Patterns",
        L"Effective C++",
        L"More Effective C++"
    };

    // 使用lambda表达式替代unary_function（C++11特性）
    // 直接在remove_if中定义筛选逻辑，无需单独定义结构体
    const std::wstring target = L"C++";
    v.erase(std::remove_if(v.begin(), v.end(),
        [&target](const std::wstring& str) {  // lambda表达式捕获外部变量
            return str.find(target) != std::wstring::npos;
        }),
        v.end());

    // 使用范围for循环遍历结果（C++11特性）
    for (const auto& str : v) {
        std::wcout << str << std::endl;
    }

    return 0;
}

注意：

remove_if其实真正做的是针对ContainsString条件给出了erase函数需要操作的iterator位置，如下图所示：

image-20250812234519484

Deque

Deque 是一个能够存放任意型别的双向队列

Deque 提供的函数与 vector 类似，新增了两个函数：

  • push_front: 在头部插入一个元素
  • pop_front: 在头部弹出一个元素

Deque 采用了与 vector 不同内存管理方法：大块分配内存

为了使用 deque，必须用 include 指令包含如下文件，并通过 std 命名空间去访问：

#include <deque>
int main() {
  std::deque dq;
}

特性

  • 双向操作高效：在头部和尾部的插入、删除操作都是常数时间 O (1)
  • 随机访问：可以像数组一样通过下标访问元素，时间复杂度 O (1)
  • 动态大小：会自动扩容以适应元素数量变化
  • 内存布局：与 vector 的连续内存不同，deque 采用分段连续内存块存储，通过内部指针数组管理这些块
  • 迭代器稳定性：在两端插入或删除元素时，其他元素的迭代器、指针和引用保持有效

基本用法

声明与初始化

// 声明一个空的 deque（存储 int 类型）
deque<int> dq1;

// 声明并初始化含有 5 个元素，每个元素值为 10
deque<int> dq2(5, 10);

// 通过初始化列表初始化
deque<int> dq3 = {1, 2, 3, 4, 5};

// 通过另一个 deque 初始化
deque<int> dq4(dq3.begin(), dq3.end());

修改元素

deque<int> dq;

// 在尾部插入元素
dq.push_back(10);
dq.push_back(20);

// 在头部插入元素
dq.push_front(5);

// 在尾部删除元素
dq.pop_back();

// 在头部删除元素
dq.pop_front();

// 清空所有元素
dq.clear();

// 插入元素到指定位置
dq.insert(dq.begin() + 2, 100);  // 在索引 2 处插入 100

// 删除指定位置的元素
dq.erase(dq.begin() + 1);        // 删除索引 1 处的元素

容量相关

deque<int> dq;

// 在尾部插入元素
dq.push_back(10);
dq.push_back(20);

// 在头部插入元素
dq.push_front(5);

// 在尾部删除元素
dq.pop_back();

// 在头部删除元素
dq.pop_front();

// 清空所有元素
dq.clear();

// 插入元素到指定位置
dq.insert(dq.begin() + 2, 100);  // 在索引 2 处插入 100

// 删除指定位置的元素
dq.erase(dq.begin() + 1);        // 删除索引 1 处的元素

迭代器操作

deque<int> dq = {10, 20, 30, 40};

// 正向迭代器
for (deque<int>::iterator it = dq.begin(); it != dq.end(); ++it) {
    cout << *it << " ";
}
// 输出：10 20 30 40

// 反向迭代器
for (deque<int>::reverse_iterator rit = dq.rbegin(); rit != dq.rend(); ++rit) {
    cout << *rit << " ";
}
// 输出：40 30 20 10

Deque与Vector的区别

特性 Deque Vector
内存布局 分段连续内存 单一连续内存
头部操作 O(1) O(n)
尾部操作 O(1) O(1)
中间插入删除 O(n) O(n)
扩容效率 较高（无需复制全部元素） 较低（可能需要复制全部元素）
随机访问 支持 支持
内存使用效率 略低（有额外指针数组开销） 较高

使用场景

Deque 适合以下场景：

  • 需要在两端频繁插入和删除元素
  • 需要随机访问元素
  • 不确定元素数量，需要动态扩容
  • 实现队列（FIFO）或双端队列数据结构
  • 实现滑动窗口算法

示例代码

#include <iostream>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    // 创建并初始化 deque
    deque<int> dq = {3, 1, 4, 1, 5, 9};

    // 在头部和尾部添加元素
    dq.push_front(2);
    dq.push_back(6);

    // 排序
    sort(dq.begin(), dq.end());

    // 输出所有元素
    cout << "Deque elements: ";
    for (int num : dq) {
        cout << num << " ";
    }
    // 输出：Deque elements: 1 1 2 3 4 5 6 9

    // 查找元素
    auto it = find(dq.begin(), dq.end(), 5);
    if (it != dq.end()) {
        cout << "\nFound element 5 at position: " << (it - dq.begin()) << endl;
    }

    // 演示队列操作
    cout << "\nQueue operations:" << endl;
    while (!dq.empty()) {
        cout << "Front: " << dq.front() << ", Size: " << dq.size() << endl;
        dq.pop_front();
    }

    return 0;
}
STL
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																				
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇