1

在我的项目中，我有一个带有一些关系数据的向量（一个包含两个表示它们之间关系的相似对象的结构），我需要检查向量中所有数据之间的关系组合。

我正在做的是迭代向量并在第一个 for 循环中再次迭代以查找数据之间的关系。

这是我正在做的简化模型

for(a=0; a<vec.size(); a++)
{
    for(b=0; b<vec.size(); b++)
    {
        if(vec[a].something==vec[b].something) {...}
    }
}

我的收藏有 2800 个元素，这意味着我将迭代 2800*2800 次......

什么样的数据结构更适合这种操作呢？使用 for_each 会比像这样遍历向量更快吗？

提前致谢！

vec 有两个结构，它们由两个整数组成，没有任何东西是有序的。

4

3 回答 3

4

不， for_each 仍然做同样的事情。

使用哈希映射可以使您的问题变得更好。从空哈希开始并遍历列表。对于每个元素，查看它是否在散列中。如果不是，请添加它。如果是，那么您有一个副本并运行您的代码。

在 C++ 中，您可以使用 std::map。在 C 中，没有内置的地图数据结构，因此您必须自己制作。

高级伪代码看起来像这样

foreach (element in array)
  if map.has_key(element)
    do_stuff(element)
  else
    map.add_key(element)
于 2013-07-25T18:30:16.410 回答
2

提高此操作效率的最简单方法是对向量​​进行排序，然后查找重复项。如果无法选择对向量进行排序，则可以创建另一个指向该向量元素的指针向量并对其进行排序。这两者都会将您从 N**2 复杂度带到 N*log(N) 复杂度（当然，假设您使用 N*log(N) 排序）。这确实意味着使用更多空间，但通常使用一点空间来显着改进时间是非常合理的。

于 2013-07-25T18:30:58.127 回答
0

假设您的向量包含“关系”结构，例如：

class Entity;

struct Relation {
  Entity* something;
  Entity* relative;
};

你有一个“关系”向量：

std::vector<Relation> ties;

因此，如果我理解正确，您希望分割关系并为每个实体提供一个关系列表。这可以用一张地图来表示：

std::map<Entity*,std::vector<Relation*>> entityTiesIndex;

然后您可以只扫描一次所有关系并收集每个实体的关系：

for (int i=0; i < ties.size(); ++i ) {
  Relation* relation = &ties[i];
  entityTiesIndex[relation->something].push_back(relation);
}

请注意关于容器元素引用的常见免责声明，因为当容器被更改时，这些可能会发生变化。

希望这是有道理的。

于 2013-07-25T19:06:31.660 回答