How can I get vector's index by its data in C+

问题:

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.

回答1:

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!

[See a demonstration here.]

回答2:

You should use std::find. You can't get faster than linear complexity (O(n)) if you know nothing about the vector beforehand (like it being sorted).

回答3:

If you want to find elements in the container then vector is not the right data-structure. You should use an ordered container such as std::set or std::map. Since elements in these containers are kept ordered (sorted), we can find elements in O(log (n)) time as opposed to linear time for unordered containers.

回答4:

Use std::find :

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

Note that If you have sorted vector, you can make it faster.

回答5:

A neat solution would be to add an extra int index member to the node struct to provide data-to-index mapping when you have an instance of the struct. In such a case, you should probably wrap std::vector in a NodeVector class which will handle the updating of indices when, say, you remove an item (it's enough to subtract 1 from elements' indices which preceed the element being removed in such a case) etc. If the vector doesn't change the number of elements, that's not even an issue. Other than that, if you can't have an instance of the struct grow in size, use std::map. Iterating over the containter to find one item is not very smart, unless you need to do it very rarely and making anything complicated isn't worth the trouble.