Looking for efficient algorithm on list iterator

[dekeenfrance]

Hi,

I have a list and a vector, for example like

list<int> mylist = {1, 1, 1, 0, 0, 1, 0, 0}
vector<int> myvec;

I want to create an efficient algorithm to erase all element of value "1", and give these elements to a vector. My code (not efficient) is as follows

for(auto it = mylist.begin(); it != mylist.end(); it++) {
   if(*it == 1) {
      myvec.push_back(*it);
      it = mylist.erase(it);
      if(it != mylist.begin())
         it--;
   }
}

Could anyone please help me to improve this algorithm? Thanks!

[jlb]

Why do you need to erase the entry in the list? Also your implementation seems to be missing one of your ones.

   for(auto it = mylist.begin(); it != mylist.end(); it++) {
      if(*it == 1) {
         myvec.push_back(*it);
      }
   }

Also if you are are always going to push the same number into your vector maybe you just want to count the number of times this number exists in your list then construct your list with correct number of elements and the default value:

// After counting the number of ones.
std::vector<int>myvec(NumberOfOnes,1);

[dekeenfrance]

Thanks for the reply.

But this is a very simplified version of my code. The original is very complexe. I have to erase all elements of 1 from the list, one by one. And push_back the vector of elements of 1, one by one.

Otherwise it would be too easy to make it.

[jlb]

Then I don't understand the problem. You say you must push_back the vector, and remove them from the list one by one. That's basically what you're doing. You do seem to be missing one element, I count 4 ones but the code you provided only pushes 3 to the vector.

The only speed up I can see would be to construct your vector with the same size as your list. Then you could use array access instead of the expensive push_back(). If you keep a count of the number of items deleted you can then resize the vector after the loop.

[dekeenfrance]

yes you are right, the second 1 is still in the list. I have to correct this... thanks

Please feel free to help if anyone is interested. just erase one by one from list, and add one by one to vector...

[mik2718]

I would do this

it = mylist.begin();
while(it != mylist.end())
{
  if(*it == 1)
  {
    myvec.push_back(*it);
    it = mylist.erase(it); // erase returns iterator to next element
  }
  else
  {
    ++it;
  }
}

[dekeenfrance]

Thanks. How about this? Is this one slower? (imagine with list of 10 million elements)

	for(auto it = mylist.begin(); it != mylist.end(); it++)
	{
		while(*it == 1)
		{
			myvec.push_back(*it);
			it = mylist.erase(it);
			if(it != mylist.begin())
				it--;
		}
	}

[jlb]

Actually this seemed to work for me:

int main()
{
   list<int> mylist = {1, 1, 1, 0, 0, 1, 0, 0};
   vector<int> myvec(mylist.size());
   size_t counter = 0;
   for(auto it = mylist.begin(); it != mylist.end(); it++) {
      if(*it == 1) {
         myvec[counter++] = (*it);
         it = mylist.erase(it);
         it--;
      }
   }
   myvec.resize(counter);
   cout << myvec.size() << endl;
   return(0);
}

]

[dekeenfrance]

Yes, this one is good by saving time of reallocate vector...