Function returning a container containing specific elements of input container

Question

I have a vector or list of which I only want to apply code to specific elements. E.g.

class Container : public std::vector<Element*>

Or

class Container : public std::list<Element*>

And:

Container newContainer = inputContainer.Get(IsSomething);
if (!newContainer.empty()) {
    for (Element* const el: newContainer ) {
        [some stuff]
    }
} else {
    for (Element* const el : inputContainer) {
        [some stuff]
    }
}

I've written a member function Get() as follows.

template<typename Fn>
auto Container::Get(const Fn& fn) const {
    Container output;
    std::copy_if(cbegin(), cend(), std::inserter(output, output.end()), fn);
    return output;
}

and IsSomething would be a lambda, e.g.

auto IsSomething= [](Element const* const el)->bool { return el->someBool; };

From performance perspective: Is this a good approach? Or would it be better to copy and remove?

template<typename Fn>
auto Container::Get(const Fn& fn) const {
    Container output(*this);
    output.erase(std::remove_if(output.begin(), output.end(), fn), end(output));
    return output;
}

Or is there a better approach anyhow?

edit: different example

As my previous example can be written in a better way, let's show a different example:

while (!(container2 = container1.Get(IsSomething)).empty()&&TimesFooCalled<SomeValue)
{
    Container container3(container2.Get(IsSomething));
    if (!container3.empty()) {
        Foo(*container3.BestElement());
    } else {
        Foo(*container2.BestElement());
    }
}

You want `back_inserter`. `output.end()` is going to be invalidated as soon as the first element is inserted. — Igor Tandetnik, Aug 07 '18 at 13:56
If you want performance I suggest you look at [this](https://stackoverflow.com/a/51617017/4342498) — NathanOliver, Aug 07 '18 at 13:57
Yes. It works for anything that provides `push_back` method. `std::vector` and `std::list` both do. — Igor Tandetnik, Aug 07 '18 at 13:57
@IgorTandetnik wonderfull. I think I was in luck that I used `std::list`, because I had no seg-faults up to now. — JHBonarius, Aug 07 '18 at 14:00
Is subclassing containers a good idea? I thought it wasn't a good idea https://stackoverflow.com/questions/6806173/subclass-inherit-standard-containers — doctorlove, Aug 07 '18 at 14:15
@doctorlove thanks. I will fix that, as I aint getting on no memory-leak plane. — JHBonarius, Aug 07 '18 at 14:35
How do you find the "best" element? Do you have an item-to-item comparison or are you looking for a value that needs the whole range? — Fozi, Aug 07 '18 at 14:47
@Fozi something like max_element(begin, end, mem_fn(Element::Value)) — JHBonarius, Aug 07 '18 at 14:50
Ok, so would you be ok with something like `bool isBetter(Element const * old_value, Element const * new_value)`? Also, I'm guessing this is signal processing related? — Fozi, Aug 07 '18 at 14:56
@Fozi No it's for Legends of Code&Magic on CodinGame ;) There's a processing time limit, so I need fast(er) code. — JHBonarius, Aug 07 '18 at 14:58

score 2 · Answer 1 · answered Aug 07 '18 at 14:00

Not answering your direct question, but note that you can implement the original algorithm without copying anything. Something like this:

bool found = false;
for (Element* const el: inputContainer) {
  if (IsSomething(el)) {
    found = true;
    [some stuff]
  }
}
if (!found) {
  for (Element* const el : inputContainer) {
    [some stuff]
  }
}

Fozi · Answer 2 · 2018-08-07T15:15:30.413

The usual pattern that I use is something like this:

for(auto const * item : inputContainer) if(IsSomething(item)) {
    // Do stuff with item
}

This is usually good enough, so other approaches seem overkill.

For better performance it is always better not to copy or remove elements from the list you get. In my experience it's even faster if you only go through the list once, for caching reasons. So here is what I would do to find one or the other "best" value from a list:

auto const isBetter = std::greater<Element>();
Element const * best = nullptr, const * alt_best = nullptr;

for(Element const * current : inputContainer) {
    if(IsSomething(current)) {
        if(!best || isBetter(*best, *current)) best = current;
    } else {
        if(!alt_best || isBetter(*alt_best, *current)) alt_best = current;
    }
}

if(best) {
    // do something with best
} else if(alt_best) {
    // do something with alt_best
} else {
    // empty list
}

If you find yourself doing this a lot or you want to make this part of your class's interface you could consider writing an iterator that skips elements you don't like.

If you actually want to remove the item from the list, you could do something like this:

inputContainer.erase(std::remove_if(std::begin(inputContainer), std::end(inputContainer), 
    [](Element const *item) {
        if(IsSomething(item)) {
            // Do something with item
            return true;
        }
        return false;
    }
));

Function returning a container containing specific elements of input container

edit: different example

2 Answers2