Hi!
I would like to split vector elements into the two vectors. One output vector shall contain elements that, for instance, are odd, and another output vector shall contain even elements (actually the case is more complicated;). I wrote something like this:

``````typedef vector<int> ItemVec;

static bool isOdd(const int &i)
{
return i%2;
}

static bool not_isOdd(const int &i)
{
return !isOdd(i);
}

void split_example(vector& vec)
{
ItemVector oddVec;
std::remove_copy_if(vec.begin(), vec.end(), back_inserter(oddVec), not_isOdd);
vec.erase(std::remove_if(vec.begin(), vec.end(), isOdd), vec.end());

// sort both vec - different sorting methodes
...
///

vec.insert(vec.begin(), oddVec.begin(), oddVec.end());

}``````

However, all vectors elements are checked 2 times (remove_copy_if and remove_if). Is there a better algorithm providing better performance, or old good for loop shall be applied?

Edit: found similar thread, sorry for inconvenience.

Edited by Index: Found similar thread

3
Contributors
4
Replies
5
Views
8 Years
Discussion Span
Last Post by Index

>>static bool not_isOdd(const int &i)

A better name would be , isEven(...);

Work with 2 copies, of the vector and transform then into even and odd
vectors like so :

``````int A[9] = {1,2,3,4,5,6,7,8,9};
std::vector<int> numbers = std::vector<int>(A,A+9);
std::vector<int> evenNumbers = numbers;
std::vector<int> oddNumbers = numbers;
std::vector<int>::iterator vecItr;

vecItr = std::remove_if(evenNumbers.begin(),evenNumbers.end(),isOdd);
evenNumbers.resize(vecItr - evenNumbers.begin());

vecItr = std::remove_if(oddNumbers.begin(),oddNumbers.end(),isEven);
oddNumbers.resize(vecItr - oddNumbers.begin());``````

>>static bool not_isOdd(const int &i)
A better name would be , isEven(...);

Naming convention is intentional, reminds me that unary predicate passed to remove_copy_if shall return negative result of what I want to copy ;)

PS1. Your solution also needs to check the whole vector items 2 times.

PS2. My current solution is based on what I've found in another thread, now it looks like that:

``````{
ItemVector::iterator it = std::stable_partition(vec.begin(), vec.end(),isOdd);

std::sort(vec.begin(), it, srt1); // no stable sort needed here

std::stable_sort(it, vec.end(), srt2);
}``````

Thanks anyway :)

Why not just iterate through the vector once
you have your test condition is_odd()
this has to be tested once per element if as you say it
is more complicted.
then add to v1 if true
and v2 if false

an example using std::vector<int>
sorting on the contents rather than the indices
if you want the indices this only requires adding and incrementing an int.

The sort algorithms seem somewhat slow to me as you only want to split not reorder

``````//std::vector<int> orig somewhere higher up
std::vector<int> v1, v2;
//if known estimare sz of two v1
v1.reserve(v1_sz);
v2.reserve(orig_sz - v1_sz);

std::vector<int>::iterator it_stop(orig.end());
for(std::vector<int>::iterator it(orig.begin(); it!= it_stop; ++it)
{
if(is_odd(*it))
{
//condition 1 say is odd
v1.push_back(*it);
}
else
{
//condition 2
v2.push_back(*it);
}
}``````

Naming convention is intentional, reminds me that unary predicate passed to remove_copy_if shall return negative result of what I want to copy ;)

PS1. Your solution also needs to check the whole vector items 2 times.

PS2. My current solution is based on what I've found in another thread, now it looks like that:

``````{
ItemVector::iterator it = std::stable_partition(vec.begin(), vec.end(),isOdd);

std::sort(vec.begin(), it, srt1); // no stable sort needed here

std::stable_sort(it, vec.end(), srt2);
}``````

Thanks anyway :)

Actually, the target was to sort elements with different methods to improve performance (some of them can be sort with basic sorting methods, some require additional work - casts, stable sort, etc). First I thought that the splitting is necessary, so that's why I put the question about splitting. Then I found the solution, where there is no need to do this. Once again, sorry for inconvenience and thanks for the answers.
Next time I'll try to be more precise.