remove algorithm

This is a discussion on remove algorithm within the C++ Programming forums, part of the General Programming Boards category; Okay, my problem is to create a function that emulates the remove algorithm in <algorithm>. so far this is what ...

  1. #1
    dra
    dra is offline
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166

    remove algorithm

    Okay, my problem is to create a function that emulates the remove algorithm in <algorithm>.

    so far this is what I have:

    Code:
    template<class X, class T>
    void remove(X& b, X& e, T test){
    
    	while(b != e){
    		
    		if(*b == test)
    			++b;
    
    		else{
    			X temp = b;
    			while ( temp != test ) ++temp;
    			swap(*b, *temp);
    			b = temp;
    		}
    
    	}
    }
    but it doesn't quite work...

    Code:
    vector<int> vec;
    
    //input 5 1 5
    vec.push_back(5);
    vec.push_back(1);
    vec.push_back(5);
    
    remove(vec.begin(), vec.end(), 5);
    printing vec gives me: 1 1 5

    Also, the real remove function returns a iterator...but that shouldn't be too hard.

    Can someone help me show me what my version is doing wrong?
    Last edited by dra; 01-26-2008 at 03:47 PM.

  2. #2
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    What are your errors and where do they happen, post the compiler log.

  3. #3
    dra
    dra is offline
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166
    I don't get any errors...I just don't get the expected output.

    5 1 5 and remove(vec.begin(), vec.end(), 5) should yield 1 5 5, but instead i get 1 1 5;

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    It is not clear what you're trying to do here. Are you trying to swap all the removed ones to the front, or something? It's also not clear what's going to happen if you walk past e in the while loop with temp and test. I mean, what happens if you try to remove 5 from "1 2 5 3 5 3"?

  5. #5
    dra
    dra is offline
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166
    Well my goal is to create a function that works just like the remove function in <algorithm> remove(b, e, t) which moves all values not equal to t to the front of the container...
    Last edited by dra; 01-26-2008 at 04:03 PM.

  6. #6
    Ethernal Noob
    Join Date
    Nov 2001
    Posts
    1,901
    You should take pointers to T rather than T itself, and iterate through the program.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    I'm pretty sure you've gotten "front" and "back" backwards, since your algorithm leaves the removed values alone, and takes the nonremoved values and moves them forward. Maybe you should switch your uses of ==test and !=test; this way your code would leave the nonremoved values alone, and move the removed values forward.

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Your remove logic is quite broken, too. You lose track of your current position, and you swap to the wrong position. Oh, and you swap from the wrong position, because remove() must be stable.

    On the other hand, the content of the elements after the return iterator is unspecified. There's no need to swap anything there.

    Here's what I'd do.
    Code:
    template <typename FwdIt, typename T>
    FwdIt remove(FwdIt first, FwdIt last, T death)
    {
      for(; first != last && *first != death; ++first) {}
      if(first == last) return first;
    
      FwdIt target = first;
      for(++first; first != last; ++first) {
        if(*first != death) {
          *target = *first;
          ++target;
        }
      }
      return target;
    }
    Last edited by CornedBee; 01-26-2008 at 04:45 PM.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    dra
    dra is offline
    Weak. dra's Avatar
    Join Date
    Apr 2005
    Posts
    166
    Thanks for the help...

    problems like these always seem so difficult...

    Edit:
    I went back and I looked over what remove actually does, and it seems I wasn't understanding it correctly. I was under the impression that the elements in the container should be arranged or sorted according to the value given, which is incorrect.
    Last edited by dra; 01-26-2008 at 06:23 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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