copy_if for maps
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 11 of 11

Thread: copy_if for maps

  1. #1
    Join Date
    Feb 2003
    Posts
    377

    copy_if for maps

    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.
    Code:
    #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.

  2. #2
    Join Date
    Oct 2002
    Location
    Singapore
    Posts
    3,128
    As you have probably noticed, there is no copy_if() in STL. Here's a generic example for copy_if() from Effective STL.

    Code:
    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;
    }

  3. #3
    Join Date
    Feb 2003
    Posts
    377
    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?

  4. #4
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,564
    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).

    Code:
    #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;
    }

  5. #5
    Join Date
    Oct 2002
    Location
    Singapore
    Posts
    3,128
    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.

  6. #6
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,564
    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:

    Code:
    #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);

  7. #7
    Join Date
    Feb 2003
    Posts
    377
    Thanks for the information. The following was what I was missing for a):
    Code:
        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:
    Code:
    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:
    Code:
    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.

  8. #8
    Join Date
    Oct 2002
    Location
    Singapore
    Posts
    3,128
    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.

    Code:
    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.

  9. #9
    Join Date
    Oct 2002
    Location
    Singapore
    Posts
    3,128
    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.

  10. #10
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,564
    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++) :

    Code:
    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)
    Last edited by Philip Nicoletti; January 26th, 2004 at 07:40 AM.

  11. #11
    Join Date
    Feb 2003
    Posts
    377
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center