Removing all empty elements in a vector from end

Question

Given a std::vector of strings, what is the best way of removing all elements starting from the end that are empty (equal to empty string or whitespace). The removal of elements should stop when a non-empty element is found.

My current method, (work in progress) is something like:

while (Vec.size() > 0 && (Vec.back().size() == 0 || is_whitespace(Vec.back()))
{
    Vec.pop_back();
}

where is_whitespace returns a bool stating if a string is whitespace or not

I suspect that my method will resize the vector at each iteration and that is suboptimal. Maybe with some algorithm it is possible to do in one step.

Input: { "A", "B", " ", "D", "E", " ", "", " " }

Desired Output: { "A", "B", " ", "D", "E" }

"I suspect that my method will resize the vector at each iteration " - no, it won't. — , Apr 30 '18 at 13:57
@NeilButterworth `pop_back` does change the size, doesn't it? — Baum mit Augen, Apr 30 '18 at 13:58
@Baum Yes, of course it changes what the size() member will return, but it doesn't resize the vector's storage. — , Apr 30 '18 at 13:59
@NeilButterworth Maybe I'm assuming too much precision in OP's wording here, but they *are* talking about size, not capacity, strictly speaking. — Baum mit Augen, Apr 30 '18 at 14:00
I don't see that this question is a duplicate of the one linked above. I am asking to remove from the end, and remove_if seems to take forward iterators as arguments. An example using remove_if in this case would be helpful. — Sturm, Apr 30 '18 at 14:02
@Baum When a vector's storage actually grows, we typically say it has been "resized", not "recapacitied", if that is a word. — , Apr 30 '18 at 14:03
remove_if() can be called with vector.rbegin() and vector.rend(). The choice of iterator is yours. — Goswin von Brederlow, Apr 30 '18 at 14:05
I don't know what to answer to that Jive Dadson, I am actually asking for that example. I have posted some code in order to show that I have tried something by my own before asking for help.. — Sturm, Apr 30 '18 at 14:06
@GoswinvonBrederlow But `remove_if` will go over the whole vector, which isn't what OP needs here. — interjay, Apr 30 '18 at 14:06
You could throw an exception to abort early. But I like the answerebelow better than using remove_if so lets leave it at that. — Goswin von Brederlow, Apr 30 '18 at 14:52

Baum mit Augen · Answer 1 · 2018-04-30T14:36:27.217

4

As I did not find a good dupe on first glance, here is a simple solution:

// Helper function to see if string is all whitespace
// Can also be implemented as free-function for readablity and
// reusability of course
auto stringIsWhitespace = [](const auto &str)
{
    return std::all_of(
        begin(str), end(str), [](unsigned char c) { return std::isspace(c); });
};

// Find first non-whitespace string from the back
auto it = std::find_if_not(rbegin(Vec), rend(Vec), stringIsWhitespace);
// Erase from there to the end
Vec.erase(it.base(), end(Vec));

Note the unsigned in the lambda due to this gotcha.

Live example thanks to @Killzone Kid.

edited Apr 30 '18 at 14:36

answered Apr 30 '18 at 14:07

Baum mit Augen

49,044
25
144
182

This is definitely a more modern C++ solution, but note that it does require iterating through the whitespace elements twice. – Mike Borkland Apr 30 '18 at 14:11
1

@MikeBorkland But on the other hand, we use a bulk-delete operation over repeated pops. Especially for simple stuff as `char`, I'm very reluctant to believe there is a non-negligible performance difference without benchmarks. That second "iteration" can be implemented as assignment to the vector's size member – Baum mit Augen Apr 30 '18 at 14:13
Doesn't seem to work with vector of strings, which is as I understand OP's requirement – Killzone Kid Apr 30 '18 at 14:14
@KillzoneKid Ah right; his code tests chars not strings, went from there. Hang on, I'll fix it. Thanks. – Baum mit Augen Apr 30 '18 at 14:15
@BaummitAugen Apart from missing closing brace for lambda, it still doesn't seem to work :( https://ideone.com/GJ202T – Killzone Kid Apr 30 '18 at 14:23
You are probably right. I'd be interested to see how they performed against each other with a `vector` of, say, 1 million elements, with 500,000 "whitespace" strings on the end. – Mike Borkland Apr 30 '18 at 14:25
@KillzoneKid Right, messed up what we wanted to keep and what to delete, the `find_if` is obviously wrong and should be `find_if_not`. Or switch the logic in the predicate, either works. Thanks again; not my day it seems. – Baum mit Augen Apr 30 '18 at 14:27
@MikeBorkland Honestly, I wouldn't worry about it until I actually find it's a bottleneck in my real code. Clarity first, optimization later. – Baum mit Augen Apr 30 '18 at 14:31
@BaummitAugen No worries, scratched my head as well ;) Have an upvote – Killzone Kid Apr 30 '18 at 14:32

score 3 · Answer 2 · answered Apr 30 '18 at 14:05

3

Here's a better way:

for (auto it = Vec.rbegin(); it != Vec.rend() && is_whitespace(*it); )
{
    it = Vec.erase(it);
}

It will start from the end and stop once non-whitespace has been encountered or the beginning of the vector is reached, whichever comes first. Note that I don't increment the iterator in the for loop.

answered Apr 30 '18 at 14:05

Mike Borkland

714
1
5
12

Does `auto` pick the right iterator here? You need a delete iterator. – Goswin von Brederlow Apr 30 '18 at 14:07

Removing all empty elements in a vector from end

2 Answers2

Linked