How to efficiently search vectors in C++

Question

I need to find whether a vector<unsigned> searchvec; is present in a vector<vector<unsigned> > containerVec;. One way to do the same is to iterate over vector<vector<unsigned> > containerVec; and see whether searchVec is present in containerVec. Is there any build in c++ function which can help me do the same.

Also my searchVec is of size 1 million vector

For example if my searchVec is (9,28,4,2) and my containerVec is ((1,3,678,27),(9,28,4,2), (595,85,52)). Then searchVec (9,28,4,2) is present in ((1,3,678,27),(9,28,4,2), (595,85,52)). However if my searchVec is (23,84,25,11) then it is not present in containerVec.

EDIT: I tried std::find but perf tool shows it takes the most time. Is there any other data structure which I can use.

This is not a duplicate. As I am mentioned in my question std::find is giving poor performance. Also the duplicate which u have marked nowhere talks about performance issue

What you are asking for? Do you search a vector where the content of that vector is the same as an other sample vector? Or you really search for a object which has the name which you are searching? What is the meaning of `searchVec is present in containerVec`? — Klaus, May 30 '15 at 09:23
@Klaus I have tried to explain the same with the help of an example in my question — Steg Verner, May 30 '15 at 09:28
@DavidWoo I am not trying to check whether two vectors are equal...as I mentioned in my question..it is one of the ways of solving by iterating over containerVec..but as mentioned I am searching for an efficient implementation. What I am searching is: is it possible to find whether searchVec is in containerVec — Steg Verner, May 30 '15 at 09:31
@DavidWoo They just want to find an element in a vector. Like you do with `std::find`. — juanchopanza, May 30 '15 at 09:34
ok - then the question should be "is there an function to search a stl:container for a given value?" — David Woo, May 30 '15 at 09:38
@juanchopanza This is not a duplicate. As I am mentioned in my question std::find is giving poor performance. Also the duplicate which u have marked nowhere talks about performance issue — Steg Verner, May 30 '15 at 10:02
Then I think the question should be "How do I efficiently compare two containers with many items for equality?" In which case this question may help you http://stackoverflow.com/questions/17394149/how-to-efficiently-compare-vectors-with-c — David Woo, May 30 '15 at 10:29
@StegVerner Then you should ask the question you're actually interested in, and not some other question. — juanchopanza, May 30 '15 at 12:28

score 2 · Answer 1 · answered May 30 '15 at 09:29

Use the STL find function.

Keep in mind that there is also a find_if function, which you can use if your search is more complex, i.e. if you're not just looking for an element, but, for example, want see if there is an element that fulfills a certain condition, for example, a string that starts with "abc". (find_if would give you an iterator that points to the first such element).

see this link:http://www.sgi.com/tech/stl/find.html

Nikos Athanasiou · Answer 2 · 2015-05-30T09:42:15.013

Vectors compare lexicographically when the contained element is comparable. So a vector<unsigned> gets its compare functions for free (unless you want to specify a different behavior). In the following demo you can see why std::find can work with containers of vector<unsigned>

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    std::vector<unsigned> v1{ 1, 2, 3 }; 
    std::vector<unsigned> v2{ 1, 2, 3 }; 
    std::vector<unsigned> v3{ 3, 4 };

    std::cout << (v1 == v2) << std::endl;
    std::cout << (v1 < v3) << std::endl;
    std::cout << (v3 < v2) << std::endl;

    std::vector<std::vector<unsigned>> vv { v1, v2, v3 }; 

    auto it = std::find(vv.begin(), vv.end(), v3); 
    if (it != vv.end())
    {
        std::cout << "I found v3, it has the following elements\n"; 
        for (auto &&a : *it)
        {
            std::cout << a << std::endl;
        }
    }        
}

score 0 · Answer 3 · edited May 23 '17 at 11:58

0

Crosscororrelate searchvec with containervec,

en.wikipedia.org/wiki/Cross-correlation

this can be done like shown here:

Pattern recognition with double vectors

which will give you the similarity of the compared part of containervec to searchvec.

edited May 23 '17 at 11:58

Community

1
1

answered May 30 '15 at 09:25

mmoment

1,269
14
30

How to efficiently search vectors in C++

3 Answers3