Remove all the vector elements apart from the 'largest' one

Question

Given a vector such as this:

struct product {
    float price;
    float shipping;
};

vector<product> products;

how can I remove all the products from the vector apart from the one with the largest shipping to price ratio?

I tried keeping an iterator to the highest one found so far...

vector<product>::iterator it = products.begin();
vector<product>::iterator largest = products.begin();

while (it != products.end())
{
    if (it->shipping / it->price > largest->shipping / largest->price)
    {
        products.erase(largest);
        largest = it;
        ++it;
    }
    else
    {
        it = products.erase(it);
    }
}

This is all well and good but it fails if the first element in the vector has the highest ratio (it gets deleted). I could get around the problem (I think) if largest was uninitialized and then checking for that in the if statement, but there is no real way of doing this from what I can tell (How to check if the iterator is initialized?).

Any suggestions?

Just initialize `it` to `products.begin() + 1`. – Pete Becker Nov 08 '12 at 01:23 — Pete Becker, Nov 08 '12 at 01:23

111111 · Accepted Answer · 2012-11-08T00:13:56.607

4

 vector<product> products;
 //populate products

 products.erase(
      products.begin(),
      std::max_element(
          product.begin(), 
          producted.end()
      )
 );
 products.resize(1u);

This assume you have a suitable operator< for your type, if not, make a comparison function and provide it as the third param to max_element.

EDIT:

This work also, in this case, instead of explicitly find the element and delete the element either side, it will sort to find 1 elemnt, then we can do one erase.

 vector<product> products;
 //populate products
 std::nth_element(
      products.begin(), 
      products.begin()+1, 
      products.end(), 
      std::greater<product>()
 );
 products.resize(1u);

edited Nov 08 '12 at 00:13

answered Nov 07 '12 at 23:22

111111

15,686
6
47
62

You don't need the second call to `max_element`; after the first `erase` maximum value is the first element. So `products.erase( ++products.begin(), products.end() );` will do the trick. – Praetorian Nov 07 '12 at 23:26
3

I think I'd use `std::swap` to move the maximum element to the beginning of the collection, then delete the rest (could be substantially faster, especially for `vector`). – Jerry Coffin Nov 07 '12 at 23:28
that's why I ask how big is the vector :D – billz Nov 07 '12 at 23:29
actually the nicest way in that respect would be to do `nth_element`, to sort to 1 element, then erase. – 111111 Nov 07 '12 at 23:29
Or, to also get rid of the extra allocated space: `std::vector(1, products.back()).swap(products);`. – jrok Nov 07 '12 at 23:32
2

`products.assign(1, *std::max_element(product.begin(), producted.end());` – Mooing Duck Nov 07 '12 at 23:36
@jrok, the cost of the allocation is probably more than the wasted space, although that is context specific. – 111111 Nov 07 '12 at 23:37
1

@MooingDuck, Nice, but you use three different names for `products`. – chris Nov 07 '12 at 23:37
@MooingDuck that would mean at least one copy, I think the nth_element way would be moved. – 111111 Nov 07 '12 at 23:37
@chris: I'm at a complete loss as to how/why that happened. – Mooing Duck Nov 07 '12 at 23:43
@MooingDuck, It's funny to realize what our brains can do when we're not looking :) – chris Nov 07 '12 at 23:45
Your second call to `products.erase(...)` could be simplified to `products.resize(1)` – Blastfurnace Nov 08 '12 at 00:13

score 0 · Answer 2 · answered Nov 07 '12 at 23:23

0

Just rewrite the code to only make one single deletion:

std::vector<product>::iterator largest = products.begin();

for (std::vector<product>::iterator it = products.begin(); it != products.end(); ++it)
{
    if (...) { largest = it; }
}

products.erase(it);

answered Nov 07 '12 at 23:23

Kerrek SB

464,522
92
875
1,084

say that my vector has 10 elements. how will one single deletion remove 9 of them (there is only one with the largest ratio which should be left)? – zoran119 Nov 07 '12 at 23:31
@zoran119: You need two passes. Determine the *value* of the largest ratio first, and then delete all those elements. Use `std::remove_if` for that. – Kerrek SB Nov 08 '12 at 03:33

score 0 · Answer 3 · answered Nov 08 '12 at 02:29

You could define largest as the first element and start iteration from the second element, just as followings:

bool operator < (const struct product& p1, const struct product& p2)
{
   return p1.price/p1.shipping < p2.price/p2.shipping;
}

vector<product>::iterator largest = products.begin();
vector<product>::iterator it = products.begin();
++it;

while (it != products.end())
{
    if (*largest < *it)
    {
        products.erase(largest);
        largest = it;
        ++it;
    }
    else
    {
        it = products.erase(it);
    }
 }

But there is a bug here, after products.erase(largest) is called, it will be invalidated, so you'd better take the approach other suggested here.

Remove all the vector elements apart from the 'largest' one

3 Answers3