时间戳

首页 > 解决方案 > 查找 std::list 是否包含来自另一个 std::list 的元素

c++ - 查找 std::list 是否包含来自另一个 std::list 的元素

问题描述

我有两个清单：

std::list<MyClass1> listClass1;
std::list<MyClass2> listClass2;

为简单起见，假设它们具有以下元素：

listClass1

{id: 1, name: "Test1"}
{id: 2, name: "Test2"}
{id: 3, name: "Test3"}
{id: 4, name: "Test4"}
{id: 5, name: "Test5"}

listClass2

{id: 1, name: "Test2"}
{id: 2, name: "Test5"}

我需要查明listClass2 name财产是否在listClass1 name. 我的意思是，如果他们匹配。否则返回错误或-1。

有没有比循环两次更有效的方法？这就是我目前能想到的一切，所以任何帮助表示赞赏。

标签： c++

解决方案

您可以将列表名称中的一个（两者中的较大者更好）存储到 a 中set<string>，然后遍历另一个列表并查看该集合是否包含该元素。

这应该将您的运行时间从 O(m * n) 减少到 O(m * log(n))。

PS：我相信使用哈希表可以进一步降低 log(n) 因子。

推荐阅读