3

I'm writing a piece of C++ that checks to see whether particular elements of a vector return true, and uses remove_if() to remove them if not. After this, I use vector.size() to check to see if there are any elements remaining in the vector, and then return the function if not.

At the moment, I do vector.erase() after remove_if(), as it doesn't actually reduce the size of the vector. However, this code needs to run fast, and recursively changing the size of a vector in memory is probably not ideal. However, returning if the vector is zero (instead of running the rest of the function) probably also saves time.

Is there a nice way to check how many elements remain in the vector without erasing?

here's the code:

  auto remove = remove_if(sight.begin(), sight.end(), [](const Glance *a) {
    return a->occupied;
  }); 

  sight.erase(remove, sight.end());

  if (sight.size() == 0) {
    // There's nowhere to move
    return;
  }

EDIT: thanks for the help + the guidance. From the answers it's clear that the wording of the question isn't quite correct: erase() doesn't change the size of the vector in memory, but the capacity. I had mis-remembered the explanation from this post, which nicely articulates why erase() is slower than remove() for multiple removals (as you have to copy the location of the elements in the vector multiple times).

I used Instruments to benchmark the code I had originally against Johannes' suggestion, and the difference was marginal, though Johannes' was consistently slightly faster (~9.8% weight vs ~8.3% weight for the same code otherwise). The linked article should explain why. ✨

Agnes Cameron
  • 105
  • 9
  • 3
    `std::distance(sight.begin(), remove);` will tell you how many elements remain in the "valid" range. – François Andrieux Feb 13 '19 at 17:19
  • It's not because it's resized that it's reallocated. – Matthieu Brucher Feb 13 '19 at 17:19
  • 2
    Note that `erase` doesn't cause the vector's *capacity* to change, there is no memory reallocation. – François Andrieux Feb 13 '19 at 17:20
  • 1
    This is really going to depend on what exactly you are going but `remove - sight.begin()` will tell you how many elements are "left" in the vector. – NathanOliver Feb 13 '19 at 17:20
  • 1
    If you are just storing a pointer here, nothing to worry about in terms of speed. Except don't use `size()` to test for emptiness, use `empty()`. – Matthieu Brucher Feb 13 '19 at 17:20
  • I'm not sure why you think your current method isn't good enough? – Rietty Feb 13 '19 at 17:21
  • Have you benchmarked this code and determined that it's slow? – Kevin Feb 13 '19 at 17:25
  • 1
    Can the people who are downvoting this question please elaborate why. I find the question clear and relevant. – Johannes Overmann Feb 13 '19 at 17:29
  • hi! My understanding was that `erase` changed the size of the vector in memory, but perhaps that's not the case. I'll try and find where I read that explanation and link it – Agnes Cameron Feb 13 '19 at 17:36
  • It's unclear what the result should be (I can't see what we're returning _from_, or what state anything is supposed to be left in). Questions that say things need to be fast with no benchmarking are always a bit suspect. Also that isn't what "recursive" means. I didn't downvote, but those are the unlikeable parts of the question for me. – Useless Feb 13 '19 at 17:36
  • @Galik the vector elements appear to be raw pointers, so destructors aren't an issue (although leaking might be, outside the scope of this Q) – Useless Feb 13 '19 at 17:40
  • "After this, I use vector.size() to check to see if there are any elements remaining in the vector, and then return the function if not." if you use pair of iterators as standard algos do instead of passing vector itself you would not even have your question. – Slava Feb 13 '19 at 17:59
  • 1
    @AgnesCameron "*My understanding was that `erase` changed the size of the vector in memory*" - it does indeed change the **size**, but not the **capacity**. Two different things. The `size` is the current number of "valid" elements, whereas the `capacity` is the max number of elements that can be held before reallocation is needed. Shrinking the `size` never reallocates the `capacity`, however "erasing" elements will destruct them if needed. But, your `vector` appears to be holding pointers, not object instances, so there is nothing for the `vector` to destruct (but YOU may have to manually). – Remy Lebeau Feb 13 '19 at 19:50
  • @RemyLebeau oh, nice! thanks so much, that makes a lot more sense. – Agnes Cameron Feb 13 '19 at 19:52

2 Answers2

5

You can use std::distance(sight.begin(), remove); to get the number of remaining elements:

auto remove = remove_if(sight.begin(), sight.end(), [](const Glance *a) {
    return a->occupied;
}); 

size_t remaining = std::distance(sight.begin(), remove);

if (remaining == 0) {
    // There's nowhere to move
    return;
}

But if you are only interested in 0 you can do:

auto remove = remove_if(sight.begin(), sight.end(), [](const Glance *a) {
    return a->occupied;
}); 

if (remove == sight.begin()) {
    // There's nowhere to move
    return;
}
Johannes Overmann
  • 4,914
  • 22
  • 38
2

Instead of erasing elements that satisfy a criteria and then checking the number of remaining elements just to find out how many elements did not satisfy the criteria, you could simply iterate the container and count those elements. The standard library has an algorithm for that: std::count_if.

eerorika
  • 232,697
  • 12
  • 197
  • 326