如何通过C ++中的数据获得向量的索引？ [英] How can I get vector's index by its data in C++?
问题描述
让我们假设我有一个向量< node> 包含10000个对象：
vect [0] to vect
struct node
{
int data;
};
假设我想要找到包含此数据的向量id（444）， 。
我真的必须为 -loop循环遍历所有元素，然后使用
if（data == c [i] .data）
还是有更快的方法？考虑我的数据是不同的，不会在其他节点中重复。
对于这个答案，我假设你已经 明智地决定使用 std :: vector 超过其他可用的容器 。
我真的要做一个for循环遍历所有的元素吗？
不，你不必滚动为 -loop找到一个元素。在容器中查找元素的惯用方法是使用来自标准库的算法。
要帮助你决定...
替代方案1：
std :: find（） 要求您的节点数据类型，可以是这样简单：
bool operator == ; l，node const& r）
{
return l.data == r.data;
}
然后，给定必需 node ，可以搜索元素。这会传回迭代器（如果您使用的是旧式阵列，则会传回指针）。如果您需要 index ，这需要一些计算：
auto i = std :: find （v.begin（），v.end（），required）;
if（i！= v.end（））
{
std :: cout< i->数据< found at index<< i-v.begin（） std :: endl;
}
else
{
std :: cout< Item not found<< std :: endl;
}
备选2：
如果创建节点太贵了或者没有相等运算符，更好的方法是使用 std :: find_if（） （这里我使用一个lambda，因为它的简洁，但你可以使用函数像这个答案）：
//替代线性搜索，使用谓词...
auto i = std :: find_if（v.begin （），v.end（），[]（node const& n）{return n.data == 444;}）;
if（i！= v.end（））
{
std :: cout< i->数据< found at index<< i-v.begin（） std :: endl;
}
else
{
std :: cout< Item not found<< std :: endl;
}
还是有更快的方法？ p>
再说一遍。 std :: find（）和 std :: find_if（） O （ ））与相同。
也就是说，使用 std :: find（）或 std :: find_if（）不会涉及随机访问或索引到容器中（它们使用迭代器），但是与 for - 循环相比，它们可能需要一些额外的代码。
替代方案3：
如果运行时间至关重要，并且数组排序（例如 std :: sort（） ），您可以执行二元搜索，它在对数时间（ （log n ））中运行。 std :: lower_bound（） 实现对不小于给定值的第一个元素进行二分查找。它不需要谓语不幸，但需要一个合适的小于比较器您的节点数据类型，如：
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->数据< found at index<< i-v.begin（） std :: endl;
}
else
{
std :: cout< Item not found<< std :: endl;
}
这些函数来自算法库与提供迭代器的任何容器一起工作，因此从 std :: vector
$ b
Let's assume I have a vector<node> containing 10000 objects:
vect[0] to vect[9999]
struct node
{
int data;
};
And let's say I want to find the vector id that contain this data ("444"), which happens to be in node 99.
Do I really have to do a for-loop to loop through all the elements then use
if (data == c[i].data)
Or is there a quicker way? Consider that my data is distinct and won't repeat in other nodes.
For this answer I am assuming that you've made 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?
No, you do not have to roll a for-loop to find an element. The idiomatic way of finding an element in a container is to use an algorithm from the standard library. Whether you should roll your own really depends on the situation.
To help you decide...
Alternative 1:
std::find() requires a that there is a suitable equality comparator for your node data type, which may be as simple as this:
bool operator ==(node const& l, node const& r)
{
return l.data == r.data;
}
Then, given a required node, you can search for the element. This returns an iterator (or a pointer if you're using a plain old array). If you need the index, this requires a little calculation:
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;
}
Alternative 2:
If creating a node is too expensive or you don't have an equality operator, a better approach would be to use std::find_if(), which takes a predicate (here I use a lambda because it's succinct, but you could 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?
Again, it depends. std::find() and std::find_if() run in linear time (O(n)), the same as your for-loop.
That said, using std::find() or std::find_if() won't involve random access or indexing into the container (they use iterators) but they may require a little bit of extra code compared with your for-loop.
Alternative 3:
If running time is critical and your array is sorted (say with std::sort()), you could perform a binary-search, which runs in logarithmic time (O(log n)). std::lower_bound() implements a binary search for the first element that is not less than the given value. It does not take a predicate unfortunately but requires a suitable less-than comparator for your node data type, such as:
bool operator <(node const& l, node const& r)
{
return l.data < r.data;
}
The invocation is similar to std::find() and returns an iterator, but requires an extra check:
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;
}
These functions from the Algorithms Library work with any container supplying an iterator, so switching to another container from std::vector would be quick and easy to test and to maintain.
The decision is yours!
这篇关于如何通过C ++中的数据获得向量的索引？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
