Is there a better way to split a container of a non-movable type based on a predicate

user_19801356 0
Viewed 69

I want to ask for an alternative solution to this problem. I am dealing with this C/C++ style interface that has this non-moveable type NonMovableType defined roughly as follows:

union union_type {
  int index;
  const char* name;
};

struct NonMovableType 
{
   std::initializer_list<union_type> data;
};

This is something I cannot change, despite the unfortunate use of unions and initializer lists. We then have some container of this type, say

std::vector<NonMovableType> container

and we want to split container based on some predicate for each of its members. Now, if it was a movable type i'd do

std::vector<NonMovableType> container;
std::vector<NonMovableType> result;

auto iter = std::partition(container.begin(), container.end(), [](const NonMovableType& element){
     return element.data.size(); // the predicate
});
std::move(iter, container.end(), std::back_inserter(result));
container.erase(iter, container.end());

I could then trust container and result would contain the elements split by the predicate, that way I could then iterate over each one individually and do the necessary processing on them.

This wont work however because std::move and std::partition both require a movable type. Instead I have to result to the rather slow:

std::vector<NonMovableType> container;
std::vector<NonMovableType> result_a;
std::vector<NonMovableType> result_b;

std::copy_if(container.begin(), container.end(), std::back_inserter(result_a), [](const NonMovableType& element){
      return element.data.size();
});
std::copy_if(container.begin(), container.end(), std::back_inserter(result_b), [](const NonMovableType& element){
      return !element.data.size();
});
container.clear();

And so, my question is, is there any better way to do this? I suppose calling it a 'non movable type' may be wrong, its only the union and the initializer list which are giving me problems, so really the question becomes is there a way to move this type safely, and do so without having to change the initial class. Could it also be possible to wrap NonMovableType into another class and then use pointers as opposed to a direct type?

c++
1 Answers

Is it really a performance problem or are you trying to optimize in advance?

As for a general answer: it really depends. I would probably try to achieve everything in a single pass (especially if the original container has a lot of elements), e.g.

for (const auto& el : container) {
  if (el.data.size()) out1.push_back(el);
  else out2.push_back(el);
}

which can be easily generalized into:

template<typename ForwardIt, typename OutputIt1, typename OutputIt2, typename Pred>
void split_copy(ForwardIt b, ForwardIt e, OutputIt1 out1, OutputIt2 out2, Pred f)
{
    for(; b != e; ++b) {
        if (f(*b)) {
            *out1 = *b;
            ++out1;
        } else {
            *out2 = *b;
            ++out2;
        }
    }
}

Is this going to be faster than partitioning first and copying later? I can't tell, maybe. Both solutions are imho ok in terms of readability, as for their performance - please measure and get back with the numbers. :)

Demo: https://godbolt.org/z/axMsKGq7d

EDIT: operating on heap-allocated objects and vectors of pointers to them, as well as operating on lists is sth. to be verified in practice, for your particular use case. It might help, of course, but again, measure first, optimize later.

user_48853210
Related