Thread: Template Iterator Algorithm

Hi. I am trying to figure out how to get this program to remove the item I am commanding (70 in this case). I am obviously barking up a slightly wrong tree here. I have just started working with iterators. Could someone give some helpful hints? Thanks.

Code:

#include<iostream>
#include<iterator>
#include<vector>
#include<string>

using namespace std;

template <class T>
class Set
{
  public:
    void add(const T& anItem);
    void remove(const T& anItem);
    friend ostream& operator <<(ostream& os, Set<T>& aSet)
    {
      typename vector<T>::iterator anIt;
      for(anIt=aSet.theMembers.begin();anIt != aSet.theMembers.end();anIt++)
      {
        os<<(*anIt)<<" ";
        os<<endl;
      }
	  return os;
    }
  private:
    vector<T> theMembers;
};


int main()
{
  Set<int> s1;
  s1.add(100);
  s1.add(90);
  s1.add(80);
  s1.add(70);
  s1.add(60);
  s1.add(50);
  cout<<s1<<endl;
  s1.remove(70);
  cout<<s1<<endl;
  system("pause");
  return 0;
}

template <class T>
void Set<T>::add(const T& anItem)
{
  theMembers.push_back(anItem);
}

template<class T>
void Set<T>::remove(const T& anItem)
{
  typename vector<T>::iterator anIt;
  for(anIt=theMembers.begin();anIt != theMembers.end();anIt++)
  {
    if((*anIt)==anItem)
      (*anIt)=((*anIt)++);
  }
  theMembers.pop_back();
}

1. I assume this is a learning device. If not, the std::multiset works very well.
   
   
2. It is generally a good idea to use ++anIt instead of anIt++ unless you need the value before the increment (in the case of the for loop you don't).
   
   
3. (*anIt)=((*anIt)++);
   
   just increments the value returned from (*anIt), which is why your output includes 71. To copy the value of the next entry you would do this:
   
   (*anIt)=*(anIt+1);
   
   
4. There is already an erase function for vector that you could use. If your Set is supposed to allow duplicates (which it currently does), then you will have to continue the loop after erasing so that the iterator is not invalidated. Look at this code for a way to do this more correctly using erase:
   Code:

     typename vector<T>::iterator anIt(theMembers.begin());
     while(anIt != theMembers.end())
     {
       if((*anIt)==anItem)
         anIt = theMembers.erase(anIt);
       else
         ++anIt;
     }

   If you don't want to allow duplicates, you can of course, just return after removing that object.
   
   
5. If you don't want to use erase() (again, I assume as a learning exercise), then you need to change your removal algorithm. Whenever you find a match, you must move the entire remainder of the vector one spot over one at a time. For that you will need a second, nested loop.
   
   
6. Obviously, that is not very efficient, which is why a list would work better in this instance (ignoring set and multiset). If your Set allows removal of items in the middle of the data, then you might want to implement it in terms of a list, which doesn't have the overhead of that extra loop above or the overhead of copying the data of each object after the removed one.

Code:

  for(anIt=theMembers.begin();anIt != theMembers.end();anIt++)
  {
    if((*anIt)==anItem)
      (*anIt)=((*anIt)++);  //this line isn't quite right
  }

the tagged line will add one to the item anIt is currently on, then set it back to itself. This would turn 70 into 71. Is that what is happening? It's been a while since i've used an STL iterator.

Even if that isn't what's happening, the algorithm still is not correct. You'll have to do more in that if statement.

edit: sorry jlou, must have been answering at the same time =)

Just a fun, probably not useful, little note: you could #include <algorithm> and change your operator << to:

Code:

friend ostream& operator <<(ostream& os, const Set<T>& aSet)
{
  std::copy(aSet.theMembers.begin(), aSet.theMembers.end(), std::ostream_iterator<T>(os, "\n"));
  return os;
}