C++ STL 通过算法和容器操作实现合并与拆分。有序 vector 可用 std::merge 高效合并，list 利用 splice 实现 O(1) 合并与拆分，set 和 map 需保持有序性，推荐 insert 或 C++17 节点提取。
C++ STL 中并没有直接提供容器合并和拆分的原子操作，但我们可以利用 STL 提供的算法和容器操作来实现类似的功能。核心思路在于利用迭代器高效地移动元素，以及利用容器提供的插入、删除等操作。
容器合并与拆分需要根据具体的需求选择合适的算法和容器操作。例如，合并有序容器可以使用
std::merge，拆分容器可以利用迭代器和容器的插入、删除操作。
如何高效合并两个有序 std::vector
？
如果两个
std::vector已经排序，那么使用
std::merge是一个高效的选择。它可以在线性时间内完成合并，而不需要额外的排序步骤。
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec1 = {1, 3, 5, 7, 9};
std::vector<int> vec2 = {2, 4, 6, 8, 10};
std::vector<int> result;
// 预先分配足够的空间，避免多次重新分配
result.resize(vec1.size() + vec2.size());
std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
std::cout << "Merged vector: ";
for (int val : result) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}这里预先分配了
result的大小，避免了
std::merge过程中可能发生的多次重新分配内存，提升了效率。
立即学习“C++免费学习笔记（深入）”；
如何将一个 std::vector
拆分成两个？
拆分
std::vector可以根据索引或者条件进行。例如，根据索引拆分成两部分，可以直接使用迭代器构造新的
std::vector。
#include <iostream>
#include <vector>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
size_t split_index = 5;
std::vector<int> vec1(vec.begin(), vec.begin() + split_index);
std::vector<int> vec2(vec.begin() + split_index, vec.end());
std::cout << "Vector 1: ";
for (int val : vec1) {
std::cout << val << " ";
}
std::cout << std::endl;
std::cout << "Vector 2: ";
for (int val : vec2) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}如果需要根据条件拆分，可以使用
std::partition或者手动循环判断。
std::partition可以将满足条件的元素移动到容器的前面，然后可以根据
std::partition返回的迭代器位置拆分容器。
对于 std::list
，合并和拆分操作有什么不同？
std::list由于其链表结构，合并和拆分操作与
std::vector有所不同。
std::list提供了
splice方法，可以高效地将一个
std::list的一部分或者全部移动到另一个
std::list中，而不需要复制元素。
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 3, 5};
std::list<int> list2 = {2, 4, 6};
// 将 list2 的所有元素移动到 list1 的末尾
list1.splice(list1.end(), list2);
std::cout << "Merged list: ";
for (int val : list1) {
std::cout << val << " ";
}
std::cout << std::endl;
std::cout << "List2 is now: ";
for (int val : list2) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}splice操作的时间复杂度是 O(1)，因为它只需要修改指针，而不需要复制元素。
对于拆分
std::list，也可以利用迭代器和
splice方法。例如，将
list1的前 n 个元素移动到
list2中。
#include <iostream>
#include <list>
int main() {
std::list<int> list1 = {1, 2, 3, 4, 5, 6};
std::list<int> list2;
int split_index = 3;
auto it = list1.begin();
std::advance(it, split_index); // 将迭代器移动到指定位置
// 将 list1 的前 split_index 个元素移动到 list2
list2.splice(list2.begin(), list1, list1.begin(), it);
std::cout << "List1: ";
for (int val : list1) {
std::cout << val << " ";
}
std::cout << std::endl;
std::cout << "List2: ";
for (int val : list2) {
std::cout << val << " ";
}
std::cout << std::endl;
return 0;
}需要注意的是，
std::advance操作的时间复杂度是 O(n)，所以在频繁拆分
std::list时，需要考虑性能影响。
std::set
和 std::map
的合并与拆分有什么特殊考虑？
std::set和
std::map是有序容器，它们的合并需要保持元素的有序性。对于
std::set，可以使用
insert方法将一个
std::set的元素插入到另一个
std::set中，但需要注意重复元素的问题。对于
std::map，同样可以使用
insert方法，但需要处理键冲突的情况。
拆分
std::set和
std::map可以使用迭代器构造新的容器，或者使用
extract和
insert方法（C++17 引入）来移动节点，避免元素的复制。
总的来说，C++ STL 提供了丰富的算法和容器操作，可以灵活地实现容器的合并和拆分。选择合适的算法和容器操作，可以提高代码的效率和可读性。关键在于理解不同容器的特性，以及 STL 算法的适用场景。
