CODEWITHSUNDEEP
c++c++11vectorstlset
rublow
rublow

Reputation: 53

Finding elements of std::vector in std::set

I have two containers std::set and std::vector and my task is to return elements from std::vector which are present in std::set. What is the most effective way to achieve it? Simple solution: Iterate through elements of vector and call set.find on each and then vector.erase if not found.

Upvotes: 3

Views: 2109

Answers (5)

tmp
tmp

Reputation: 1127

You can use more STL :)

#include <algorithm>
#include <set>
#include <vector>
#include <iostream>
#include <iterator>

int main() {
    std::vector<int> v {5, 4, 3, 2, 1};
    std::set<int> s {1, 3, 5};

    v.erase(std::remove_if(v.begin(), v.end(), 
                          [&s](int a) { return s.find(a) == s.end(); }),
            v.end());

    std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " "));
}

Upvotes: 0

Dev Null
Dev Null

Reputation: 5027

If you look for the most cpu-effective way of doing this in terms of complexity, have additional memory and a good hash function, you can do it in O(n + m):

std::vector<int> v;
std::set<int> s;
std::unordered_set<int> us{s.cbegin(), s.cend(), s.size()};

v.erase(
    std::remove_if(v.begin(), v.end(),
        [&us] (const int entry) { return us.find(entry) == us.cend(); }),
    v.end());

Explanation: you iterate over your set once (O(m)) to prepare unordered_set. Then you iterate through your vector once (O(n)), performing unordered_set::find (0(1)) each step. It gives you the resulting complexity of O(n+m).

Also, the size of unordered_set being equal to the size of set and a good hash function helps to reduce constant part in complexity of std::unordered_set::find.

See live example.

Bear in mind, however, that lower complexity doesn't necessarily mean faster execution in particular circumstances (for example, because of extra allocations).

Upvotes: 0

user3458
user3458

Reputation:

Depending on relative size of set and vector, remove_if may be the right thing...

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

int main()
{
    std::set<int>    s{1,2,3,4,5,6,7,8};
    std::vector<int> v{7,5,10,9};

    v.erase(std::remove_if(v.begin(), v.end(), [&](int e){return s.count(e) == 0;}), v.end());


    for(int n : v)
        std::cout << n << ' ';
}

Upvotes: 0

Nikolai Shalakin
Nikolai Shalakin

Reputation: 1494

Shortest way is probably to use std::set_intersection. But you should sort a vector to make it work:

int main()
{
    std::set<int>    s{1,2,3,4,5,6,7,8};
    std::vector<int> v{7,5,10,9};
    std::sort(v.begin(), v.end()); // should not bother you if vector is small

    std::vector<int> intersection;
    std::set_intersection(s.begin(), s.end(), v.begin(), v.end(), std::back_inserter(intersection));

    for(int n : intersection)
        std::cout << n << ' ';
}

Prints: 5 7

Upvotes: 0

The Quantum Physicist
The Quantum Physicist

Reputation: 26356

How about just looking for every element? If your vector is not sorted, then there's no way around n log(n)

#include <algorithm>

std::vector<int> result;
for(auto&& el: myvector) {
    auto it_found = myset.find(el);
    if(it != myset.end())
        result.push_back(*it_found);
}

Now result has all the elements that are in both.

PS: Haven't compiled the code, there might be slight errors.

Upvotes: 2

Related Questions