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

P粉602998670

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

527人浏览过

来源于php中文网

原创

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 
#include 
#include 

int main() {
  std::vector vec1 = {1, 3, 5, 7, 9};
  std::vector vec2 = {2, 4, 6, 8, 10};
  std::vector 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 
#include 

int main() {
  std::vector vec = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  size_t split_index = 5;

  std::vector vec1(vec.begin(), vec.begin() + split_index);
  std::vector 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

中，而不需要复制元素。

PHP与MySQL程序设计3

本书是全面讲述PHP与MySQL的经典之作，书中不但全面介绍了两种技术的核心特性，还讲解了如何高效地结合这两种技术构建健壮的数据驱动的应用程序。本书涵盖了两种技术新版本中出现的最新特性，书中大量实际的示例和深入的分析均来自于作者在这方面多年的专业经验，可用于解决开发者在实际中所面临的各种挑战。本书内容全面深入，适合各层次PHP和MySQL开发人员阅读，既是优秀的学习教程，也可用作参考手册。

下载

#include 
#include 

int main() {
  std::list list1 = {1, 3, 5};
  std::list 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 
#include 

int main() {
  std::list list1 = {1, 2, 3, 4, 5, 6};
  std::list 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;
}

需要注意的是，