Which container to use to remove duplicates?

[blueeyedlion]

I have many pairs of co-ordinate positions (starting points and destinations). If any of the pairs have the same destination, I need to delete all the pairs with that destination. I was thinking that a std::multimap could work, but is there a different container better suited to the task?

[JLBorges]

Perhaps a std::map<> mapping pairs of co-ordinate positions (with keys compared on destination values), to count of number of occurrences. Or a similiar std::unordered_map<>

#include <utility>
#include <vector>
#include <map>
#include <iostream>

std::vector< std::pair<int,int> > remove_pairs_with_the_same_destination(
                        const std::vector< std::pair<int,int> >& srce_dest_pairs )
{
    using pair = std::pair<int,int> ;

    static const auto compare_dest = [] ( const pair& a, const pair& b )
                                       { return a.second < b.second ; } ;
    std::map< pair, int, decltype(compare_dest) > counts(compare_dest) ;
    for( const pair& p : srce_dest_pairs ) ++counts[p] ;

    std::vector<pair> result ;
    for( const auto& p : counts ) if( p.second == 1 ) result.push_back(p.first) ;

    return result ;
}

int main()
{
    std::vector< std::pair<int,int> > seq =
    { {0,2}, {1,2}, {3,4}, {5,6}, {0,1}, {7,2}, {0,3}, {8,6}, {9,2} } ;

    for( const auto& p : remove_pairs_with_the_same_destination(seq) )
        std::cout << p.first << ',' << p.second << '\n' ;
}

http://ideone.com/ZxyoQb

[blueeyedlion]

This is very helpful, but I think I was unclear on the co-ordinates. both the starting points and the destinations are points on a 2D grid. How would I go about getting a map to work with nested pairs?

[JLBorges]

> How would I go about getting a map to work with nested pairs?

Exactly the same way, except that instead of std::vector< std::pair<int,int> >,
you would use std::vector< std::pair< std::pair<int,int>, std::pair<int,int> > >

#include <utility>
#include <vector>
#include <map>
#include <iostream>

using coords = std::pair<int,int> ;
using line = std::pair<coords,coords> ; // start-end coordinates

std::vector<line> remove_pairs_with_the_same_destination(
                        const std::vector<line>& srce_dest_pairs )
{
    static const auto compare_dest = [] ( const line& a, const line& b )
                                       { return a.second < b.second ; } ;
    std::map< line, int, decltype(compare_dest) > counts(compare_dest) ;
    for( const line& p : srce_dest_pairs ) ++counts[p] ;

    std::vector<line> result ;
    for( const auto& p : counts ) if( p.second == 1 ) result.push_back(p.first) ;

    return result ;
}

int main()
{
   std::vector<line> seq =
    { { {0,7}, {0,2} }, { {1,2}, {3,4} }, { {5,6}, {0,2} }, { {7,2}, {7,8} }, { {8,6}, {0,2} } } ;

   static const auto print = [] ( const std::vector<line>& sequence )
   {
        for( const auto& line : sequence )
            std::cout << line.first.first << ',' << line.first.second << " => "
                       << line.second.first << ',' << line.second.second << '\n' ;
   };

   print(seq) ;
   std::cout << "----------------\n" ;
   print( remove_pairs_with_the_same_destination(seq) ) ;
}

http://ideone.com/yJYSVd

[blueeyedlion]

One last question: how does directly comparing pairs work (as you do on line 13)?

[JLBorges]

> how does directly comparing pairs work (as you do on line 13)?

std::pair<> defines overloaded operators for lexicographic comparison of the values it contains.
http://en.cppreference.com/w/cpp/utility/pair/operator_cmp

As does std::tuple<> http://en.cppreference.com/w/cpp/utility/tuple/operator_cmp

[blueeyedlion]

You have been extremely helpful. Thank you.