copy_if for maps

[jlou]

Are there any disadvantages to this implementation of copy_if for a map? Is there a better way to do it? The goal is to copy elements from one map to the other if they satisfy the predicate without changing the source.

#include <iostream>
#include <string>
#include <map>

void CopyIfOdd(const std::map<int, std::string>& source, std::map<int, std::string>& target);
bool IsOdd(int i) { return i % 2 ? true : false; }

int main()
{
    std::map<int, std::string> allIntsToTen;
    allIntsToTen.insert(std::make_pair(1, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(2, std::string("Even")));
    allIntsToTen.insert(std::make_pair(3, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(4, std::string("Even")));
    allIntsToTen.insert(std::make_pair(5, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(6, std::string("Even")));
    allIntsToTen.insert(std::make_pair(7, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(8, std::string("Even")));
    allIntsToTen.insert(std::make_pair(9, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(10, std::string("Even")));

    std::map<int, std::string> allOddIntsToTen;

    CopyIfOdd(allIntsToTen, allOddIntsToTen);
}

void CopyIfOdd(const std::map<int, std::string>& source, std::map<int, std::string>& target)
{
    std::map<int, std::string>::const_reverse_iterator iterPair = source.rbegin();
    std::map<int, std::string>::const_reverse_iterator iterEnd = source.rend();
    std::map<int, std::string>::iterator iterLastInserted = target.end();
    for (; iterPair != iterEnd; ++iterPair)
    {
        if (IsOdd(iterPair->first))
            iterLastInserted = target.insert(iterLastInserted, *iterPair);
    }
}

Note that the focus is on the copying inside the function, not on providing a generic algorithm similar to what copy_if would be.

[Kheun]

As you have probably noticed, there is no copy_if() in STL. Here's a generic example for copy_if() from Effective STL.

template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{
    while(begin != end)
    {
        if(p(*begin))
            *destBegin++ = *begin;

        ++begin;
    }
    return destBegin;
}

[jlou]

Yeah, I checked the item in the Meyers book before writing my own. Two problems I had with that version are: a) how to call it with the map from my example; and b) how is that version better or worse than mine?

[Philip Nicoletti]

a) Here is how to do it using the copy_if template.

b) How is it better ? Probably a matter of opinion, but it
is more "stl-like". The amount of code written is smaller
(assuming you already have the copy_if template).

#include <iostream>
#include <string>
#include <map>
#include <functional>

template <typename InputIterator, typename OutputIterator, typename Predicate>
OutputIterator copy_if(InputIterator begin, InputIterator end, OutputIterator destBegin, Predicate p)
{
    while(begin != end)
    {
        if(p(*begin))
            *destBegin++ = *begin;

        ++begin;
    }
    return destBegin;
}


bool IsOdd(int i) { return i % 2 ? true : false; }

bool KeyIsOdd(const std::pair<int,std::string> & the_pair)
{
    return IsOdd(the_pair.first);
}

int main()
{
    std::map<int, std::string> allIntsToTen;
    allIntsToTen.insert(std::make_pair(1, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(2, std::string("Even")));
    allIntsToTen.insert(std::make_pair(3, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(4, std::string("Even")));
    allIntsToTen.insert(std::make_pair(5, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(6, std::string("Even")));
    allIntsToTen.insert(std::make_pair(7, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(8, std::string("Even")));
    allIntsToTen.insert(std::make_pair(9, std::string("Odd")));
    allIntsToTen.insert(std::make_pair(10, std::string("Even")));

    std::map<int, std::string> allOddIntsToTen;

    copy_if(allIntsToTen.begin(),allIntsToTen.end(),
        std::inserter(allOddIntsToTen,allOddIntsToTen.end()),KeyIsOdd);

    return 0;
}

[Kheun]

Philip, you beat me to it.

If I am not wrong, the one of main ideas behind STL is to decouple algorithm from container. Thus, in my opinion, it is more generic, shorter and works for all container types. Beside that, the predicate can be reused.

[Philip Nicoletti]

Also note, that although there is not a "copy_if" , there
is a std::remove_copy_if(). Basically it will copy all elements
for which the predicate returns false. (removes the element
if it returns true). It could be used this way:

#include <algorithm>

//

bool IsEven(int i) { return i % 2 ? false : true;  }

bool KeyIsEven(const std::pair<int,std::string> & the_pair)
{
    return IsEven(the_pair.first);
}

//
std::remove_copy_if(allIntsToTen.begin(),allIntsToTen.end(),
        std::inserter(allOddIntsToTen,allOddIntsToTen.end()),KeyIsEven);

[jlou]

Thanks for the information. The following was what I was missing for a):

    copy_if(allIntsToTen.begin(),allIntsToTen.end(),
        std::inserter(allOddIntsToTen,allOddIntsToTen.end()),KeyIsOdd);

As for b), I completely agree with the idea of decoupling the algorithm from the container, but that doesn't really help me with my original question. My focus is on the copying inside the CopyIfOdd function. It is there where I need to do the work of the copying. Of course, I could just call the copy_if from inside there, but in my real world example, I don't need to or want to implement a generic copy_if algorithm.

So really the solution using Meyers's algorithm is:

void CopyIfOdd(const std::map<int, std::string>& source, std::map<int, std::string>& target)
{
    std::map<int, std::string>::const_iterator begin = source.begin();
    std::map<int, std::string>::const_iterator end = source.end();
    std::map<int, std::string>::iterator destBegin = target.end();
    while(begin != end)
    {
        if(KeyIsOdd(*begin))
            *destBegin++ = *begin;

        ++begin;
    }
}

and using my algorithm is:

void CopyIfOdd(const std::map<int, std::string>& source, std::map<int, std::string>& target)
{
    std::map<int, std::string>::const_reverse_iterator rbegin = source.rbegin();
    std::map<int, std::string>::const_reverse_iterator rend = source.rend();
    std::map<int, std::string>::iterator lastInserted = target.end();
    while(rbegin != rend)
    {
        if (KeyIsOdd(*rbegin))
            lastInserted = target.insert(lastInserted, *rbegin);

        ++rbegin;
    }
}

Are there any disadvantages to using the second version over the first?

As far as remove_copy_if, I assume it would not work since the source map is const and cannot have items removed.

[Kheun]

Unless you are using inserter within CopyIfOdd(), you still require to perform some form of insertion. We shouldn't be directly manipulate the key_value pair within the map container.

void CopyIfOdd(const map<int, string>& source, map<int, string>& target)
{
    map<int, string>::const_iterator begin = source.begin();
    map<int, string>::const_iterator end = source.end();
    while(begin != end)
    {
       // Not worrying about the insertion position since std::map automatically sort during insertion.
        if( KeyIsOdd(*begin) )
            target.insert(*begin);  
        ++begin;
    }
}

In my opinion, both methods are roughly the same. However, I still prefer the first method since it is more intuitive when using forward iterator.

[Kheun]

I like to add that all standard associative containers keep their elements in sorted order. Directly manipulating the elements, especially the key, breaks the sortedness of the container. This is also why std::map only provides constant iterator.

[Philip Nicoletti]

I think I see what you are getting at now. You are providing
a hint to the insert() to increase the speed. I did a quick
test using VC++, and your method is faster than using
copy_if or remove_copy_if. But slightly faster (for my
version of VC++) :

void CopyIfOdd2(const std::map<int, std::string>& source, std::map<int, std::string>& target)
{
    std::map<int, std::string>::const_iterator iterPair = source.begin();
    std::map<int, std::string>::const_iterator iterEnd = source.end();
    for (; iterPair != iterEnd; ++iterPair)
    {
        if (IsOdd(iterPair->first))
            target.insert(target.end(),*iterPair);
    }
}

As far as remove_copy_if, I assume it would not work since the source map is const and cannot have items removed.

remove_copy_if() does not change the source container. (I
know the Josuttis book implies that it does, but he changed
the wording in the errata for the book on his web-site)

[jlou]

Interesting. I don't know why I didn't realize that I could just give the end of the map as a hint.
That is more along the lines of what I was trying to do, and of course much more intuitive than using
reverse iterators in addition to being slightly faster (thanks for timing it... I had only done some rough
timing stopwatch style because I didn't feel like taking the time to add timing code to my test app).

In the end, if I really did need this for my app (turns out there's extra restrictions that mean I must do
something different), I'd probably go with the remove_copy_if, now that I know that it doesn't
change the source. It is only one line plus a single predicate function that I would have to write
regardless. The speed difference is not critical.