Member Avatar for Index

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 because: Found similar thread
  • 3 Contributors
  • 4 Replies
  • 2K Views
  • 6 Days Discussion Span
  • Latest Post Latest Post by Index

Dani AI

Generated

Good instinct moving away from remove_copy_if + remove_if, . That double-evaluates the predicate and does extra copying. If you are going to sort each group differently anyway, the common pattern is: partition once, then sort the two subranges. Use std::partition when you do not care about preserving the original relative order within each group; it runs in one pass and does not guarantee stability. (tcs.rwth-aachen.de)

Example (single pass to split, then two sorts):

std::vector<int> v = /* ... */;
auto is_odd = [](int x){ return (x & 1); };

auto mid = std::partition(v.begin(), v.end(), is_odd);  // one predicate eval per element

std::sort(v.begin(), mid, /* cmp for odds */);
std::stable_sort(mid, v.end(), /* cmp for evens */);

If you truly need to keep the source untouched and materialize two separate containers (what sketched with a manual loop), prefer std::partition_copy. It copies elements into two outputs in encounter order in a single pass and applies the predicate exactly N times. You can use back inserters and optionally reserve to reduce reallocations. (en.cppreference.com)

std::vector<int> src = /* ... */;
std::vector<int> odds, evens;
odds.reserve(src.size()/2);
evens.reserve(src.size()/2);

std::partition_copy(src.begin(), src.end(),
                    std::back_inserter(odds),
                    std::back_inserter(evens),
                    [](int x){ return (x & 1); });

// sort each independently as needed...

One last nuance: if you must preserve the original relative order inside each group before sorting (e.g., tie-breaking depends on input order), use std::stable_partition instead of std::partition; it preserves order but may require extra memory or pay O(N log N) swap cost when it cannot allocate a buffer. (en.cppreference.com)

Also +1 to on naming: prefer clear predicates like isOdd/isEven; when you need the inverse, use a lambda or std::not_fn for readability.

Recommended Answers

All 4 Replies

Member Avatar for mrnutty

>>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());
Member Avatar for Index

>>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 :)

Member Avatar for tetron

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 :)

Member Avatar for Index

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.