std::vector 和 std::list 区别?
std::vector 和 std::list 是 C++ 标准库中两种不同的容器类型,它们之间有以下几个主要区别:
- 存储结构:
- std::vector 是连续内存空间上的动态数组,元素在内存中是连续存储的。
- std::list 是基于双向链表实现的,元素在内存中是非连续存储的。
- 访问效率:
- std::vector 可以通过下标随机访问元素,时间复杂度为 O(1)。
- std::list 需要顺序遍历才能访问特定元素,时间复杂度为 O(n)。
- 插入和删除效率:
- std::vector 在中间插入或删除元素时需要移动其他元素,效率较低,时间复杂度为 O(n)。
- std::list 在任意位置插入或删除元素都很高效,时间复杂度为 O(1)。
- 内存管理:
- std::vector 需要分配连续的内存空间,当容量不足时需要重新分配内存并复制元素,效率相对较低。
- std::list 在插入和删除时只需要修改指针,不需要移动元素,效率较高。
- 空间利用率:
- std::vector 由于是连续存储,可以更好地利用缓存,空间利用率较高。
- std::list 由于是链表结构,需要额外存储指针信息,空间利用率相对较低。
总的来说,std::vector 适合需要快速随机访问的场景,std::list 适合需要频繁插入和删除的场景。在选择使用哪种容器时,需要根据具体的应用需求进行权衡。
std::vector 的增删改查例子
#include <iostream>
#include <vector>
int main() {
// 创建一个空的 std::vector
std::vector<int> v;
// 增
// 在末尾追加元素
v.push_back(1);
v.push_back(2);
v.push_back(3);
// 在指定位置插入元素
v.insert(v.begin() + 1, 4);
// v 此时为 {1, 4, 2, 3}
// 查
// 访问指定位置的元素
std::cout << "Element at index 2: " << v[2] << std::endl;
// 遍历所有元素
std::cout << "All elements: ";
for (int i : v) {
std::cout << i << " ";
}
std::cout << std::endl;
// 改
// 修改指定位置的元素
v[2] = 5;
// v 此时为 {1, 4, 5, 3}
// 删
// 删除指定位置的元素
v.erase(v.begin() + 1);
// v 此时为 {1, 5, 3}
// 清空 vector
v.clear();
// v 此时为空
return 0;
}
这个例子展示了 std::vector 的基本增删改查操作:
- 创建一个空的 std::vector。
- 使用
push_back()在末尾追加元素,使用insert()在指定位置插入元素。 - 使用下标访问指定位置的元素,使用
for循环遍历所有元素。 - 使用下标修改指定位置的元素。
- 使用
erase()删除指定位置的元素,使用clear()清空整个 vector。
std::list 的增删改查例子
这里是一个 std::list 的增删改查操作的例子
#include <iostream>
#include <list>
int main() {
// 创建一个空的 std::list
std::list<int> lst;
// 增
// 在末尾追加元素
lst.push_back(1);
lst.push_back(2);
lst.push_back(3);
// 在头部插入元素
lst.push_front(4);
// lst 此时为 {4, 1, 2, 3}
// 查
// 访问头部元素
std::cout << "Head element: " << lst.front() << std::endl;
// 访问尾部元素
std::cout << "Tail element: " << lst.back() << std::endl;
// 遍历所有元素
std::cout << "All elements: ";
for (int i : lst) {
std::cout << i << " ";
}
std::cout << std::endl;
// 改
// 修改指定位置的元素
auto it = lst.begin();
std::advance(it, 2);
*it = 5;
// lst 此时为 {4, 1, 5, 3}
// 删
// 删除头部元素
lst.pop_front();
// 删除尾部元素
lst.pop_back();
// 删除指定元素
lst.remove(5);
// lst 此时为 {1, 3}
// 清空 list
lst.clear();
// lst 此时为空
return 0;
}
这个例子展示了 std::list 的基本增删改查操作:
- 创建一个空的 std::list。
- 使用
push_back()在末尾追加元素,使用push_front()在头部插入元素。 - 使用
front()访问头部元素,使用back()访问尾部元素,使用for循环遍历所有元素。 - 使用迭代器
advance()移动到指定位置,然后修改元素。 - 使用
pop_front()删除头部元素,使用pop_back()删除尾部元素,使用remove()删除指定元素,使用clear()清空整个 list。
std::list 查找某个特定元素如何查找
在 std::list 中查找特定元素有几种方法:
1 使用 find() 算法:
#include <iostream>
#include <list>
#include <algorithm>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
// 查找元素 3
auto it = std::find(lst.begin(), lst.end(), 3);
if (it != lst.end()) {
std::cout << "Found element: " << *it << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
2 使用 std::list 的成员函数 find():
#include <iostream>
#include <list>
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
// 查找元素 3
auto it = lst.find(3);
if (it != lst.end()) {
std::cout << "Found element: " << *it << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
3 使用 std::find_if() 算法,传入一个自定义的谓词函数：
#include <iostream>
#include <list>
#include <algorithm>
bool isEven(int x) {
return x % 2 == 0;
}
int main() {
std::list<int> lst = {1, 2, 3, 4, 5};
// 查找第一个偶数元素
auto it = std::find_if(lst.begin(), lst.end(), isEven);
if (it != lst.end()) {
std::cout << "Found element: " << *it << std::endl;
} else {
std::cout << "Element not found" << std::endl;
}
return 0;
}
以上三种方法都可以用来在 std::list 中查找特定元素。其中,使用 std::find() 算法和 std::list 的成员函数 find() 可以查找特定值的元素,而使用 std::find_if() 算法可以查找满足自定义条件的元素。