Template Iterator Algorithm

This is a discussion on Template Iterator Algorithm within the C++ Programming forums, part of the General Programming Boards category; Hi. I am trying to figure out how to get this program to remove the item I am commanding (70 ...

  1. #1
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Question 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();
    }

  2. #2
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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.

  3. #3
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    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 =)

  4. #4
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Specialising a member function with a template template parameter
    By the4thamigo_uk in forum C++ Programming
    Replies: 10
    Last Post: 10-12-2007, 04:37 AM
  2. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  3. error: template with C linkage
    By michaels-r in forum C++ Programming
    Replies: 3
    Last Post: 05-17-2006, 08:11 AM
  4. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  5. oh me oh my hash maps up the wazoo
    By DarkDays in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 11:54 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21