c++ - 如何通过 C++ 中的数据获取 vector 的索引？

Question

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

vect[0] to vect[9999]

struct node
{
    int data;
};

假设我想找到包含此数据(“444”)的 vector ID，它恰好位于节点 99 中。

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

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

或者有没有更快的方法？考虑到我的数据是不同的，不会在其他 node 中重复

Answer 1

对于这个答案，我假设你已经做了 an informed decision to use a std::vector over the other containers available .

Do I really have to do a for-loop to loop through all the elements?

不，您不必滚动 for 循环来查找元素。在容器中查找元素的惯用方法是使用标准库中的算法。您是否应该自行推出取决于具体情况。

帮助您决定...

备选方案 1:

std::find()需要一个适合您的 node 数据类型的相等比较器，它可能像这样简单:

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

然后，给定一个required node，您可以搜索该元素。这将返回一个迭代器(或者一个指针，如果您使用的是普通的旧数组)。如果您需要索引，这需要一点计算:

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:

如果创建节点 成本太高或者您没有相等运算符，更好的方法是使用std::find_if()。 ，它带有一个谓词(这里我使用 lambda，因为它很简洁，但你可以 use a functor like in 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;
}

Or is there a quicker way?

同样，这取决于。 std::find() 和 std::find_if() 以线性时间运行(O(n))，与您的 for 循环相同。

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

备选方案 3:

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

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

调用类似于 std::find() 并返回一个迭代器，但需要额外检查:

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

这些函数来自 the Algorithms Library与提供迭代器的任何容器一起工作，因此从 std::vector 切换到另一个容器将快速且易于测试和维护。

决定权在您!

[See a demonstration here.]