current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 1 down vote favorite

I have come up with this approach but I'm not convinced about its effectiveness. Is there any effective approach?

#include <string>
#include <iostream>

template <typename Container,  typename UnaryPredicate>
auto remove_if(Container& c, UnaryPredicate pred)
    -> decltype(c.begin())
{
    auto it = std::begin(c);
    while (it != std::end(c))
    {
        if(pred(*it))
        {
            it = c.erase(it);
        }
        else
        {
            ++it;
        }
    }
    return it;
}

template <typename Container, typename T>
auto remove(Container& c,  T const& value)
    -> decltype(c.begin())
{
    return remove_if(c,  [&](T const& t) { return t == value; });
}

int main()
{
    std::string str = " Text with some spaces ";
    remove(str, ' ');
    std::cout << str ;
}
share|improve this question
    
Stop trying to re-invent things that are already in the standard. Thats just silly. The standard implementation will be the most efficient way to do something (it has been reviewed by actually experts to make sure it is efficient). – Loki Astari Dec 5 '14 at 21:15
    
If you are aware of the existence of standard functions for this purpose, it might be adequate tagging this as reinventing-the-wheel – glampert Dec 5 '14 at 21:48
up vote 4 down vote accepted

General Comment

Stop trying to re-invent the wheel.
Or at least go look at a more interesting wheel that has not been optimized to the point were you can't do better.

Code Review

You are calling std::end() every iteration of the loop. Its not a very ineffecient call. But its still doing work they you probably don't need to in most containers.

    while (it != std::end(c))

The standard erase-remove idiom does not need to do this because it works out what it needs to remove first. Thus saving this cost (even if it is very small).

This does not work on all container types (in pre C++11):

             it = c.erase(it);

On containers like std::vector the erase(it) is very expensive. As you have to move all the elements down by one place each time you call erase. This is why the erase-remove idiom does it the other way. It moves elements down as many places as they need to go in a single shot without having to do multiple copies (one move per element).

share|improve this answer
    
thanks for the answer, i have tested c.erase(it++), it seems, it doesn't work with string and vector – MORTAL Dec 5 '14 at 23:19
    
You are correct. SO in C++03 you need a generic way of moving the pointer or not depending on container type that does not rely on erase() returning the next iterator value (this was fixed in C++11). – Loki Astari Dec 5 '14 at 23:44
up vote 3 down vote

You could apply the erase-remove idiom using std::remove() from <algorithm>. 

#include <algorithm>
#include <string>
#include <iostream>

int main()
{
    std::string str = " Text with some spaces ";
    str.erase(std::remove(str.begin(), str.end(), ' '),
              str.end());
    std::cout << str ;
}
share|improve this answer
    
yes. you are right. actually i looked at std::remove(). it invokes unnecessary algorithm like std::move() and std::find_if() which is a bit expensive – MORTAL Dec 5 '14 at 21:02
    
@MORTAL: std::move is a no-op as all it does is change the type. Also when appropriate this type change will result in faster code as objects will be moved rather than copied (so actually a good thing to have). And why is std::find_if() expensive? Its purpose is exactly what you are doing, The only difference is that it has already been tested and code reviewed a billion times to make sure it is actually very efficient. – Loki Astari Dec 5 '14 at 21:22
    
@LokiAstari: thanks for clarifying std::move() i thought it was some sort of casting. and for std::remove() actually it loops the container twice thats the reason it expensive – MORTAL Dec 5 '14 at 21:28
    
@MORTAL: No it does not. You understanding of what is happening is flawed. If finds the first occurrence of what needs to be removed. Then iterates over the remaining part of the container moving elements down the required number of slots (as more removed stuff is found the larger the move distance but it only requires one traversal of the container. The erase simply resets the end to the new end and calls all the destructors of deleted items. – Loki Astari Dec 5 '14 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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