1. STL 迭代器删除元素
迭代器失效是指在对容器进行修改时，原有的迭代器可能变得不可用。正确删除元素的方法是使用 erase，并返回新的有效迭代器。
示例代码
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 输出初始状态
std::cout << "Initial vector: ";
for (int n : vec) std::cout << n << " ";
std::cout << std::endl;
// 使用迭代器遍历并删除元素
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it == 3) {
it = vec.erase(it); // 删除元素并返回下一个有效迭代器
std::cout << "Removed 3, new vector: ";
for (int n : vec) std::cout << n << " "; // 输出当前 vector
std::cout << std::endl;
} else {
++it; // 继续下一个元素
}
}
// 输出最终结果
std::cout << "Final vector: ";
for (int n : vec) std::cout << n << " "; // 输出 1 2 4 5
std::cout << std::endl;
return 0;
}
删除值为 3 的元素时，程序通过更新迭代器避免了失效问题。
1. 对于序列容器vector，deque来说，使用erase后，后边的每个元素的迭代器都会失效，后边每个 元素都往前移动一位，erase返回下一个有效的迭代器；
2. 对于关联容器map，set来说，使用了erase后，当前元素的迭代器失效，但是其结构是红黑树，删除当前元素，不会影响下一个元素的迭代器，所以在调用erase之前，记录下一个元素的迭代器即可；
3. 对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的迭代器，因此上面两种方法都可以使用。
2. resize 和 reserve 的区别
reserve：预留内存，不改变size，只影响capacity。resize：改变size，多余的元素会被移除或填充默认值。
示例代码
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
// 预留空间
vec.reserve(10);
std::cout << "After reserve(10): Size = " << vec.size() << ", Capacity = " << vec.capacity() << std::endl;
// 调用 resize 改变大小
vec.resize(10);
std::cout << "After resize(10): Size = " << vec.size() << ", Capacity = " << vec.capacity() << std::endl;
// 输出元素
std::cout << "Elements: ";
for (int n : vec) std::cout << n << " "; // 输出 0 0 0 0 0 0 0 0 0 0
std::cout << std::endl;
// 继续添加元素
for (int i = 0; i < 5; ++i) {
vec.push_back(i + 1);
}
std::cout << "After adding 5 elements: Size = " << vec.size() << ", Capacity = " << vec.capacity() << std::endl;
// 输出最终元素
std::cout << "Final Elements: ";
for (int n : vec) std::cout << n << " "; // 输出 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5
std::cout << std::endl;
return 0;
}
这里 reserve 预留了空间而不初始化元素，resize 则初始化了新增加的元素。
1. 首先必须弄清楚两个概念：
（1）capacity：该值在容器初始化时赋值，指的是容器能够容纳的最大的元素的个数。还不能通 过下标等访问，因为此时容器中还没有创建任何对象。
（2）size：指的是此时容器中实际的元素个数。可以通过下标访问0-(size-1)范围内的对象。
2. resize和reserve区别主要有以下几点：
（1）resize既分配了空间，也创建了对象；reserve表示容器预留空间，但并不是真正的创建对 象，需要通过insert（）或push_back（）等创建对象。
（2）resize既修改capacity大小，也修改size大小；reserve只修改capacity大小，不修改size大 小。
（3）两者的形参个数不一样。 resize带两个参数，一个表示容器大小，一个表示初始值（默认为 0）；reserve只带一个参数，表示容器预留的大小。
问题延伸： resize 和 reserve 既有差别，也有共同点。两个接口的共同点是它们都保证了vector的空间大小 (capacity)最少达到它的参数所指定的大小。
下面就他们的细节进行分析。 为实现resize的语义，resize接口做了两个保证：
（1）保证区间[0, new_size)范围内数据有效，如果下标index在此区间内，vector[indext]是合法的；
（2）保证区间[0, new_size)范围以外数据无效，如果下标index在区间外，vector[indext]是非法的。
reserve只是保证vector的空间大小(capacity)最少达到它的参数所指定的大小n。在区间[0, n)范围内， 如果下标是index，vector[index]这种访问有可能是合法的，也有可能是非法的，视具体情况而定。 以下是两个接口的源代码：
template <class T, class Allocator = std::allocator<T>>
class vector {
public:
void reserve(size_type new_cap) {
if (new_cap > capacity()) {
pointer new_data = alloc.allocate(new_cap); // 分配新内存
for (size_type i = 0; i < size(); ++i) {
alloc.construct(new_data + i, std::move_if_noexcept(data[i])); // 移动元素
}
for (size_type i = 0; i < size(); ++i) {
alloc.destroy(data + i); // 销毁旧元素
}
alloc.deallocate(data, capacity()); // 释放旧内存
data = new_data;
cap = new_cap;
}
}
};
template <class T, class Allocator = std::allocator<T>>
class vector {
public:
void resize(size_type count, T value = T()) {
if (count < size()) {
for (size_type i = count; i < size(); ++i) {
alloc.destroy(data + i); // 销毁多余的元素
}
} else if (count > size()) {
reserve(count); // 确保容量足够
for (size_type i = size(); i < count; ++i) {
alloc.construct(data + i, value); // 添加新元素
}
}
size_ = count; // 更新大小
}
};
注意：如果n大于当前的vector的容量(是容量，并非vector的size)，将会引起自动内存分配。所以现有的pointer,references,iterators将会失效。而内存的重新配置会很耗时间。
3. STL 容器动态链接可能产生的问题
动态链接可能引发多种问题，主要包括 ABI 兼容性、符号冲突和性能开销。
- ABI 兼容性：不同编译器或 STL 实现可能导致二进制不兼容，进而引发运行时错误。
- 符号冲突：同名符号在不同库中可能导致链接错误。
- 性能开销：动态链接在每次调用时可能引入查找开销，影响性能。
4. map 和 unordered_map 的区别
map
- 实现：红黑树，元素按键值排序。
- 复杂度：O(log n) 的插入、删除和查找。
unordered_map
- 实现：哈希表，无序存储。
- 复杂度：平均 O(1) 的插入、删除和查找，最坏 O(n)。
示例代码
#include <iostream>
#include <map>
#include <unordered_map>
int main() {
// 使用 map
std::map<int, std::string> orderedMap;
orderedMap[1] = "One";
orderedMap[3] = "Three";
orderedMap[2] = "Two";
std::cout << "Ordered map (sorted by keys):" << std::endl;
for (const auto& pair : orderedMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
// 使用 unordered_map
std::unordered_map<int, std::string> unorderedMap;
unorderedMap[1] = "One";
unorderedMap[3] = "Three";
unorderedMap[2] = "Two";
std::cout << "Unordered map (unordered keys):" << std::endl;
for (const auto& pair : unorderedMap) {
std::cout << pair.first << ": " << pair.second << std::endl; // 输出顺序不确定
}
return 0;
}
map和unordered_map的区别在于他们的实现基理不同。
1. map实现机理
map内部实现了一个红黑树（红黑树是非严格平衡的二叉搜索树，而AVL是严格平衡二叉搜索 树），红黑树有自动排序的功能，因此map内部所有元素都是有序的，红黑树的每一个节点都代表 着map的一个元素。因此，对于map进行的查找、删除、添加等一系列的操作都相当于是对红黑树进行的操作。map中的元素是按照二叉树（又名二叉查找树、二叉排序树）存储的，特点就是左子树上所有节点的键值都小于根节点的键值，右子树所有节点的键值都大于根节点的键值。使用中序遍历可将键值按照从小到大遍历出来。
2. unordered_map实现机理
unordered_map内部实现了一个哈希表（也叫散列表），通过把关键码值映射到Hash表中一个位 置来访问记录，查找时间复杂度可达O（1），其中在海量数据处理中有着广泛应用。因此，元素 的排列顺序是无序的。
5. vector 和 list 的区别及适用场景
vector
- 动态数组，支持随机访问。
- 适合场景：大量读操作、尾部插入。
list
- 双向链表，每个元素包含前后指针。
- 适合场景：频繁中间插入和删除。
示例代码
#include <iostream>
#include <vector>
#include <list>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {1, 2, 3, 4, 5};
// vector 随机访问
std::cout << "Vector element at index 2: " << vec[2] << std::endl; // 输出 3
// list 中间插入
auto it = lst.begin();
std::advance(it, 2); // 移动到第三个元素
lst.insert(it, 10); // 在第三个元素之前插入 10
std::cout << "List after insertion: ";
for (int n : lst) std::cout << n << " "; // 输出 1 2 10 3 4 5
std::cout << std::endl;
return 0;
}
vector和list区别在于底层实现机理不同，因而特性和适用场景也有所不同。
vector：一维数组
特点：元素在内存连续存放，动态数组，在堆中分配内存，元素连续存放，有保留内存，如果减少大小后内存也不会释放。
优点：和数组类似开辟一段连续的空间，并且支持随机访问，所以它的查找效率高其时间复杂度O(1)。
缺点：由于开辟一段连续的空间，所以插入删除会需要对数据进行移动比较麻烦，时间复杂度O （n），另外当空间不足时还需要进行扩容。
list：双向链表
特点：元素在堆中存放，每个元素都是存放在一块内存中，它的内存空间可以是不连续的，通过指针来进行数据的访问。
优点：底层实现是循环双链表，当对大量数据进行插入删除时，其时间复杂度O(1)。
缺点：底层没有连续的空间，只能通过指针来访问，所以查找数据需要遍历其时间复杂度O（n），没有提供[]操作符的重载。
应用场景
vector拥有一段连续的内存空间，因此支持随机访问，如果需要高效的随即访问，而不在乎插入和删除的效率，使用vector。
list拥有一段不连续的内存空间，如果需要高效的插入和删除，而不关心随机访问，则应使用list。
6. vector 原理
vector底层实现原理为一维数组（元素在空间连续存放）。
1. 插入元素
insert 方法用于在指定位置插入一个或多个元素。它会返回指向新插入元素的迭代器。
示例代码
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 4, 5};
// 在第二个位置插入元素 3
auto it = vec.insert(vec.begin() + 2, 3);
std::cout << "Vector after insert: ";
for (int n : vec) std::cout << n << " "; // 输出 1 2 3 4 5
std::cout << "\nInserted element: " << *it << std::endl; // 输出插入的元素
return 0;
}
2. 删除元素
erase 方法用于删除指定位置的元素或删除一个范围内的元素。删除后，迭代器会失效。
示例代码
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 删除第三个元素
auto it = vec.erase(vec.begin() + 2); // 删除 3
std::cout << "Vector after erase: ";
for (int n : vec) std::cout << n << " "; // 输出 1 2 4 5
std::cout << "\nNext element after erased: " << *it << std::endl; // 输出 4
return 0;
}
3. 迭代器的管理
-
失效性：当进行插入或删除操作后，原有的迭代器可能会失效。
vector的erase和insert操作可能导致原有元素的移动，因此必须小心使用。 -
更新迭代器：在插入和删除后，通常需要重新获取有效的迭代器。如果使用
erase，它会返回指向下一个有效元素的迭代器。
示例代码：插入与删除的迭代器管理
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
// 使用迭代器遍历
for (auto it = vec.begin(); it != vec.end(); ) {
if (*it % 2 == 0) { // 删除偶数
it = vec.erase(it); // 删除元素并更新迭代器
} else {
++it; // 继续下一个元素
}
}
std::cout << "Vector after removing even numbers: ";
for (int n : vec) std::cout << n << " "; // 输出 1 3 5
std::cout << std::endl;
return 0;
}
4. 总结
-
插入：使用
insert方法可以在任意位置插入元素，并返回指向新元素的迭代器。 -
删除：使用
erase方法删除指定元素，返回指向下一个元素的迭代器。 -
迭代器管理：在插入和删除后，需谨慎管理迭代器，避免使用失效的迭代器。
vector 使用动态数组，支持按需扩展。其内部维护一个指向动态分配内存的指针和两个变量表示 size 和 capacity。
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec;
for (int i = 0; i < 15; ++i) {
vec.push_back(i); // 动态扩展
std::cout << "Size: " << vec.size() << ", Capacity: " << vec.capacity() << std::endl;
}
return 0;
}
7. map 原理
map是关联式容器，它们的底层容器都是红黑树。map的所有元素都是pair，同时拥有实值（value） 和键值（key）。pair的第一元素被视为键值，第二元素被视为实值。所有元素都会根据元素的键值自动被排序。不允许键值重复。
map的特性如下
（1）map以RBTree作为底层容器；
（2）所有元素都是键+值存在；
（3）不允许键重复；
（4）所有元素是通过键进行自动排序的；
（5）map的键是不能修改的，但是其键对应的值是可以修改的。
红黑树特性
- 节点颜色为红或黑。
- 根节点为黑色。
- 每个叶子节点（空节点）都是黑色。
- 红色节点的子节点必须为黑色。
- 从根到每个叶子的路径上，黑色节点的数量相同。
示例代码
#include <iostream>
#include <map>
int main() {
std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[3] = "Three";
myMap[2] = "Two";
std::cout << "Map elements in sorted order:" << std::endl;
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl; // 输出按键排序
}
return 0;
}
8. 删除元素后的指针和迭代器变化
- 删除末尾元素：
vector和list删除末尾元素时不会影响其他元素的迭代器。
- 删除中间元素：
vector删除中间元素会导致后续元素的迭代器失效。list删除中间元素不会导致其他元素的迭代器失效。
示例代码
#include <iostream>
#include <vector>
#include <list>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {1, 2, 3, 4, 5};
// 删除末尾元素
vec.pop_back();
lst.pop_back();
std::cout << "Vector after pop_back: ";
for (int n : vec) std::cout << n << " "; // 输出 1 2 3 4
std::cout << std::endl;
std::cout << "List after pop_back: ";
for (int n : lst) std::cout << n << " "; // 输出 1 2 3 4
std::cout << std::endl;
// 删除中间元素
vec.erase(vec.begin() + 2); // 删除 3
auto it = lst.begin();
std::advance(it, 2); // 移动到第三个元素
lst.erase(it); // 删除 3
std::cout << "Vector after erase(2): ";
for (int n : vec) std::cout << n << " "; // 输出 1 2 4
std::cout << std::endl;
std::cout << "List after erase(2): ";
for (int n : lst) std::cout << n << " "; // 输出 1 2 4
std::cout << std::endl;
return 0;
}
在这个示例中，vector 和 list 删除元素后显示了各自的状态。
1. 迭代器和指针之间的区别
迭代器不是指针，是类模板，表现的像指针。他只是模拟了指针的一些功能，重载了指针的一些操 作符，-->、++、--等。迭代器封装了指针，是一个”可遍历STL（ Standard Template Library）容 器内全部或部分元素”的对象，本质是封装了原生指针，是指针概念的一种提升，提供了比指针更 高级的行为，相当于一种智能指针，他可以根据不同类型的数据结构来实现不同的++，--等操作。 迭代器返回的是对象引用而不是对象的值，所以cout只能输出迭代器使用取值后的值而不能直接输 出其自身。
2. vector和list特性
vector特性：动态数组。元素在内存连续存放。随机存取任何元素都在常数时间完成。在尾端增删 元素具有较大的性能（大部分情况下是常数时间）。
list特性：双向链表。元素在内存不连续存放。在任何位置增删元素都能在常数时间完成。不支持随机存取。
3. vector增删元素
对于vector而言，删除某个元素以后，该元素后边的每个元素的迭代器都会失效，后边每个元素都 往前移动一位，erase返回下一个有效的迭代器。
4. list增删元素
对于list而言，删除某个元素，只有“指向被删除元素”的那个迭代器失效，其它迭代器不受任何影 响
9. map 和 set 的区别及实现
map：键值对，按键排序，使用红黑树实现。set：只存储键，按键排序，使用红黑树实现。
1. set是一种关联式容器，其特性如下：
（1）set以RBTree作为底层容器
（2）所得元素的只有key没有value，value就是key
（3）不允许出现键值重复
（4）所有的元素都会被自动排序
（5）不能通过迭代器来改变set的值，因为set的值就是键，set的迭代器是const的
2. map和set一样是关联式容器，其特性如下：
（1）map以RBTree作为底层容器
（2）所有元素都是键+值存在
（3）不允许键重复
（4）所有元素是通过键进行自动排序的
（5）map的键是不能修改的，但是其键对应的值是可以修改的
综上所述，map和set底层实现都是红黑树；map和set的区别在于map的值不作为键，键和值是分 开的
示例代码
#include <iostream>
#include <map>
#include <set>
int main() {
std::map<int, std::string> myMap;
myMap[1] = "One";
myMap[2] = "Two";
std::set<int> mySet = {1, 2, 3};
std::cout << "Map elements:" << std::endl;
for (const auto& pair : myMap) {
std::cout << pair.first << ": " << pair.second << std::endl;
}
std::cout << "Set elements:" << std::endl;
for (int n : mySet) {
std::cout << n << " "; // 输出 1 2 3
}
std::cout << std::endl;
return 0;
}
10. push_back 和 emplace_back 的区别
push_back：需要先构造对象，然后拷贝到容器。emplace_back：直接在容器中构造对象，避免拷贝，提高性能。
示例代码
#include <iostream>
#include <vector>
#include <string>
class MyClass {
public:
MyClass(int a, const std::string& str) : a(a), str(str) {
std::cout << "Constructing MyClass with a=" << a << ", str=" << str << "\n";
}
private:
int a;
std::string str;
};
int main() {
std::vector<MyClass> vec;
// 使用 push_back
MyClass obj1(1, "Hello");
vec.push_back(obj1); // 需要拷贝
// 使用 emplace_back
vec.emplace_back(2, "World"); // 直接构造
return 0;
}
最后，推荐一个学习网站https://github.com/0voice。
标签：std,map,cout,迭代,区别,元素,back,vector From： https://blog.csdn.net/qq_50373827/article/details/142969320