C++如何在STL中实现容器合并与拆分-C++-PHP中文网

C++如何在STL中实现容器合并与拆分

P粉602998670

发布： 2025-09-12 11:42:01

原创

509人浏览过

C++ STL 通过算法和容器操作实现合并与拆分。有序 vector 可用 std::merge 高效合并，list 利用 splice 实现 O(1) 合并与拆分，set 和 map 需保持有序性，推荐 insert 或 C++17 节点提取。

c++如何在stl中实现容器合并与拆分

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

登录后复制

中，而不需要复制元素。

如知AI笔记

如知笔记——支持markdown的在线笔记，支持ai智能写作、AI搜索，支持DeepseekR1满血大模型

查看详情

#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;
}

登录后复制

需要注意的是，