0
\$\begingroup\$

I'm learning C++, and would like some guidance. I'm pretty sure I'm doing something wrong.

This algorithm runs in O(n) time and uses O(n) external space. Could I make a more efficient algorithm for doing this, time and memory-wise? Also, could I multi-thread this?

Here is my code. Ignore my coding style, I like making it minimal:

#include<iostream>
#include<vector>
std::ostream&operator<<(std::ostream&ost,const std::vector<int>&input){
  for(auto const&inp:input){
    ost<<inp<<" ";
  }
  return ost;
}
int main(){
  std::vector<int>nums={1,2,3,4,5,6,7,8,9};
  std::vector<int>evens;
  std::vector<int>odds;
  for(int ctr=0;ctr<nums.size();ctr++){
    if(nums[ctr]%2){
      odds.push_back(nums[ctr]);
    }else{
      evens.push_back(nums[ctr]);
    }
  }
  std::cout<<evens;
  std::cout<<odds;
  std::cout<<"\n";
}
\$\endgroup\$
0
3
\$\begingroup\$
std::ostream&operator<<(std::ostream&ost,const std::vector<int>&input){

It's not just style.

Peopledontwritelikethisbecauseitsreally reallyhardtoreadthisiswhatyourcodelookslikedontdoit.

...

Please use a reasonable amount of whitespace. Being able to read the code easily is a huge step towards understanding it:

std::ostream& operator<<(std::ostream& ost, const std::vector<int>& input) {

for(int ctr=0;ctr<nums.size();ctr++)

int isn't the correct type for indexing a vector. It should be std::size_t or std::vector<int>::size_type if we want to be picky.

But we could just use a range-based for loop here too:

for (int n : nums) { ... }

Otherwise it looks pretty reasonable.

We could use std::partition_copy from the <algorithm> header to implement this if we wanted to:

  std::partition_copy(
    nums.begin(), nums.end(), 
    std::back_inserter(odds), std::back_inserter(evens),
    [] (int n) { return n % 2; });

(And we could pass an execution policy to it for easy parallelization if we really wanted to - which seems overkill for splitting a vector of 9 numbers).

\$\endgroup\$
2
\$\begingroup\$
 for(int ctr=0;ctr<nums.size();ctr++){
    if(nums[ctr]%2){
      odds.push_back(nums[ctr]);
    }else{
      evens.push_back(nums[ctr]);
    }
  }

Well, you are repeating nums[ctr] three different places. Using the proper looping construct takes care of this automatically:

for (const auto x : nums) {

Now you already have the value in a simple named variable x and don't need to use the index at all.

Normally you don't want to repeat the same code in the if/else branches with only a small change to which variable is being used or something like that. Here, what you are doing is very simple so it's not as much as an issue, but you can still be clearer by saying

  • the odd/even chooses the target collection
  • it always does something with the target collection

This could be written

   const bool is_even = x%2;
   (is_even?evens:odds).push_back(x);
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.