2

假设我有一个vector<node>包含 10000 个对象：

vect[0] to vect[9999]

struct node
{
    int data;
};

假设我想找到包含此数据（“444”）的向量 id，它恰好位于节点 99 中。

我真的必须做一个for循环来遍历所有元素然后使用

if (data == c[i].data)

还是有更快的方法？考虑到我的数据是不同的，不会在其他nodes 中重复。

4

5 回答 5

3

对于这个答案，我假设您已做出明智的决定，使用 astd::vector而不是其他可用的容器。

我真的必须做一个for循环来循环所有元素吗？

不，您不必滚动for-loop 来查找元素。在容器中查找元素的惯用方法是使用标准库中的算法。你是否应该自己滚动真的取决于情况。

为了帮助您决定...

备选方案 1：

std::find()要求有一个适合您的node数据类型的相等比较器，这可能很简单：

bool operator ==(node const& l, node const& r)
{
    return l.data == r.data;
}

然后，给定 a required node，您可以搜索该元素。这将返回一个迭代器（如果您使用的是普通的旧数组，则返回一个指针）。如果你需要index，这需要一点计算：

auto i = std::find(v.begin(), v.end(), required);
if (i != v.end())
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

备选方案 2：

如果创建 anode太昂贵或者您没有相等运算符，则更好的方法是使用std::find_if()，它需要一个谓词（这里我使用 lambda 因为它很简洁，但您可以使用类似this answer中的仿函数）：

// Alternative linear search, using a predicate...
auto i = std::find_if(v.begin(), v.end(), [](node const& n){return n.data == 444;});
if (i != v.end())
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

还是有更快的方法？

再次，这取决于。std::find()并std::find_if()以线性时间（O ( n )) 运行，与您的for-loop 相同。

也就是说，使用std::find()或不涉及对容器的随机访问或索引（它们使用迭代器），但与您的循环std::find_if()相比，它们可能需要一些额外的代码。for-

备选方案 3：

如果运行时间很关键并且您的数组已排序（例如使用std::sort()），您可以执行二进制搜索，该搜索以对数时间（O (log n )）运行。实现对不小于给定值std::lower_bound()的第一个元素的二进制搜索。不幸的是，它不需要谓词，但需要适合您的数据类型的小于比较器，例如：node

bool operator <(node const& l, node const& r)
{
    return l.data < r.data;
}

该调用类似于std::find()并返回一个iterator，但需要额外检查：

auto i = std::lower_bound(v.begin(), v.end(), required);
if (i != v.end() && i->data == required.data)
{
    std::cout << i->data << " found at index " << i - v.begin() << std::endl;
}
else
{
    std::cout << "Item not found" << std::endl;
}

算法库中的这些函数可与任何提供迭代器的容器一起使用，因此切换到另一个容器std::vector将是快速且易于测试和维护的。

决定权在你！

[在此处查看演示。]

于 2013-02-17T02:42:28.547 回答
0

一个巧妙的解决方案是在结构中添加一个额外的int index成员，以node在您拥有结构的实例时提供数据到索引的映射。在这种情况下，您可能应该包装std::vector一个NodeVector类，该类将处理索引的更新，例如，当您删除一个项目时（在这种情况下，从元素的索引中减去 1 就足够了，在这种情况下，该元素先于被删除的元素）等等。如果向量不改变元素的数量，那甚至都不是问题。除此之外，如果您不能让 struct 的实例大小增加，请使用std::map. 遍历容器以找到一个项目并不是很聪明，除非您很少需要这样做并且使任何复杂的事情都不值得麻烦。

于 2013-02-16T21:05:17.623 回答
0

你应该使用std::find. O(n)如果你事先对向量一无所知（比如它被排序），你就不会比线性复杂度 ( ) 更快。

于 2013-02-16T20:54:40.657 回答
0

如果您想在容器中查找元素，则vector不是正确的数据结构。您应该使用有序容器，例如std::set或std::map。由于这些容器中的元素保持有序（排序），我们可以及时找到元素，O(log (n))而不是无序容器的线性时间。

于 2013-02-16T20:56:25.133 回答
0

使用std::find：

vector<int>::Iterator it = find (vect.begin(), vect.end(), 444);

请注意，如果您对向量进行了排序，则可以使其更快。

于 2013-02-16T20:57:08.647 回答