CODEWITHSUNDEEP
c++vectordata-structuresstl
dafsd
dafsd

Reputation: 55

Getting the n best elements from a vector?

I have a vector of structures, for which I have overloaded all comparison operators for. I do not know the size of the structure at compilation time.

What's the fasted way to retrieve the n best (where "best" can be either the smallest or the largest) elements in the vector? I am aware of max_element and min_element but they only return a single element. I would prefer to not loop n times, retrieving the best element, removing it and then getting the next one. This approach seems too slow.

Thanks.

Upvotes: 1

Views: 2384

Answers (6)

dwcanillas
dwcanillas

Reputation: 3651

The other answers here work, but you could also use copy_if.

std::vector<int> vec{ 1, 5, 7, 9, 3, 6, 8, 4, 2 };

std::vector<int> odd;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(odd), [](int a){ return a % 2 == 1; });
std::vector<int> low;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(low), [](int a){ return a <= 3; });
std::vector<int> high;
std::copy_if(vec.begin(), vec.end(), std::back_inserter(high), [](int a){ return a >= 7; });

There is also remove_copy_if if you need to remove the matching data.

Upvotes: 0

Christophe
Christophe

Reputation: 73366

I propose you a solution that does neither modify nor make a copy of the vector:

So I assume that the original vector is very very big and you still need the data in the original order for other purposes 

template <typename T>
set<T> best_n2(vector<T>& v, size_t n)
{
    set<int> u;          // the result is a sorted set
    int i = 0;
    for (auto x : v) {   // fill the N first elements
        if (i++ < n) {
            u.insert(x);
        }
        else if (x > *u.begin()) {  // then get rid of the smallest if necessray
            u.erase(*u.begin()); 
            u.insert(x);
        }
    }
    return u;
}

If you can modify the original vector, I'd choose the solution of szulack. I didn't propose it because he types much faster than I do ;-)

Upvotes: 0

R Sahu
R Sahu

Reputation: 206567

If you want to retrieve the n smallest elements sort the vector in ascending order.

If you want to retrieve the n largest elements sort the vector in descending order.

Then,

  1. Get two iterators.

    start = v.begin();
end = start + n;

  2. Iterate from start till end but excluding end.

Upvotes: 0

sbabbi
sbabbi

Reputation: 11181

You can use std::nth_element, that will move the smallest n elements to the first n positions in the range (notice that the relative ordering of those n elements is not defined).

std::vector<T> objects;
std::nth_element( objects.begin(), objects.begin() + n, objects.end() );

// Now the range [objects.begin(), objects.begin() + n) contains the lowest n elements
// Obviously n must be <= objects.size()

When you write that you do not know the size of the structure at compilation time, I assume that you have a collection of polymorphic objects, and you have a vector of pointers instead of elements. No big deal, you can still use std::nth_element with a lambda.

std::vector<T*> objects;
std::nth_element( objects.begin(),
                  objects.begin() + n,
                  objects.end(),
                  [](const T * lhs, const T * rhs)
                  {
                      return (*lhs) < (*rhs); // Or (*lhs) > (*rhs) for the greatest n elements
                  });

Upvotes: 5

davidhigh
davidhigh

Reputation: 15468

Another approach than the brute-force sorting-and-taking-the-first: Set up a temporary container of size n and initialize it with the first n elements of you original vector (which has size N, say). Sort that temporary vector.

Next traverse your original vector and insert elements (using std::lower_bound) whenever they are larger than the current minimum of your sorted container (and at the same time, throw out the current minimum). This should first take O(n log n + N) instead of O(N log N) asymptotically, but more important, also the constant prefactors are likely much smaller.

Upvotes: 1

szulak
szulak

Reputation: 703

Sort it and take n first elements.

struct Foo { };
std::vector<Foo> v = { Foo(), Foo(), Foo() };
std::sort(v.begin(), v.end());

std::vector<Foo> v_best(v.begin(), v.begin() + n); //where n is your best count

Upvotes: 1

Related Questions