views:

232

answers:

2

I've attempted to write a brief utility functor that takes two std::pair items and tests for their equality, but disregarding the ordering of the elements. Additionally (and this is where I run into trouble) I've written a function to take a container of those std::pair items and test for membership of a given pair argument in a the container.

/* A quick functor way to check the identity of the two items of a pair to see if each pair contains the same items regardless of order */
template <class T>
class EqualPairs : public std::binary_function<T,T,bool> {
  T arg2;

  public:
  explicit EqualPairs (const T& x) : arg2(x) { }

  bool operator() (const T& arg1) { 
    bool same = false;
    if (arg1 == arg2 || (arg1.first == arg2.second && arg1.second == arg2.first))
      same = true;
    return same;
  }
};

/* checks to see if the give pair p is a member of the list of pairs l. The pairs are compared disregarding the order of the pair elements (i.e. (4,2) == (2,4)) */
template <class P>
bool PairListMember (const P& p, const std::vector<P>& l)
{
  std::vector<P>::iterator it;
  it = find_if (l.begin(), l.end(), EqualPairs<P>(p));
  bool member_of_list = (it != l.end()) ? true : false;
  return member_of_list;
}

I couldn't think of a clean way to allow for generic container selection, so I hard-coded a std::vector as the container type, for now. Help on making the container type generic would also be appreciated, but for now I'd just like to get the above to compile and work. The error I get is:

In function ‘bool PairListMember(const P&, const std::vector<P, std::allocator<_CharT> >&)’:

    error: expected `;' before ‘it’
    error: ‘it’ was not declared in this scope

In function ‘bool PairListMember(const P&, const std::vector<P, std::allocator<_CharT> >&) [with P = std::pair<int, int>]’:

    error: dependent-name ‘std::vector<P,std::allocator<_CharT> >::iterator’ is parsed as a non-type, but instantiation yields a type
    note: say ‘typename std::vector<P,std::allocator<_CharT> >::iterator’ if a type is meant

changing the code by adding a 'typename' as suggested only results in the following errors:

error: no match for ‘operator=’ in ‘it = std::find_if [with _InputIterator = __gnu_cxx::__normal_iterator<const std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >, _Predicate = EqualPairs<std::pair<int, int> >](((const std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >*)l)->std::vector<_Tp, _Alloc>::begin [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), ((const std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > >*)l)->std::vector<_Tp, _Alloc>::end [with _Tp = std::pair<int, int>, _Alloc = std::allocator<std::pair<int, int> >](), EqualPairs<std::pair<int, int> >(((const std::pair<int, int>&)((const std::pair<int, int>*)p))))’

/usr/include/c++/4.2/bits/stl_iterator.h:637: note: candidates are: __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >& __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >::operator=(const __gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int>, std::allocator<std::pair<int, int> > > >&)
+4  A: 

For your compiler error, you need to use the typename keyword.

typename std::vector<P>::iterator it;

iterator is a typename, i.e. it refers to an embedded type within std::vector. When you access a typename with the :: operator within a template, you need to use the typename keyword so the compiler knows it is the name of a type, as opposed to the name of some variable or function within the class.

Edit: Also, you need to use a const_iterator, because your vector is const in this case.

typename std::vector<P>::const_iterator it;
Charles Salvia
+3  A: 

There are a couple of issues with your EqualPairs template. It derives from binary_function but isn't actually a binary_function because operator() only takes one argument. You can (and should) make operator() const as it doesn't modify the EqualPairs object.

I think that you can simplify it somewhat.

template<class T>
struct EqualPairs : public std::binary_function<T, T, bool>
{
    bool operator()(const T& lhs, const T& rhs) const
    {
        return lhs == rhs || lhs.first == rhs.second && lhs.second == rhs.first;
    }
};

Then you can use std::bind1st (or std::bind2nd) to make a predicate out of your binary function and the input parameter. Also, by making the function a 'one liner' you don't actually need to declare a temporary variable for the iterator, so getting const and typename correct isn't an issue.

template <class P>
bool PairListMember (const P& p, const std::vector<P>& l)
{
    return l.end() != std::find_if(l.begin(), l.end(), std::bind1st(EqualPairs<P>(), p));
}

You can make this template more generic by taking an iterator type as a template parameter. This removes your dependency on std::vector.

template <class Iter>
bool PairListMember(const typename std::iterator_traits<Iter>::value_type& p, Iter first, Iter last)
{
    return last != std::find_if(first, last, std::bind1st(EqualPairs<typename std::iterator_traits<Iter>::value_type>(), p));
}
Charles Bailey
Thanks for this great solution. One question, though - how is it that the Iter is set in the template without explicitly calling PairListMember<iter_t>(...) and supplying the type? I'm unfamiliar with the std::iterator_traits, and it looks really neat.
Shamster
`std::iterator_traits` is a 'traits' template that is designed to let you map types to other types, it's principal use is for situations like this where you want to map an iterator type to the type that it iterates through. The standard provides specializations for pointer types and standard containers' iterators so they all work as expected, but custom iterators need to provide a specialization, optionally by deriving from a `std::iterator` specialization.
Charles Bailey
After staring at the template arguments and the ordering of the function arguments, I have to assume that template types are being deduced in a non-left-to-right order here. I can run `PairListMember` without supplying any template arguments, so is the `Iter` type being deduced from the `Iter first` and `Iter last` arguments, and then being applied in the type for `p`?
Shamster
Order doesn't matter for template argument deduction, template argument deduction must happen for each argument and produce a consistent unambiguous result. In this case the template parameter cannot be deduced from the first parameter as the template argument is in a non-deduced context in that instance. As there is only one template argument it can be deduced from the second and third parameters and as this deduction leads to single non-ambiguous specialization of the function template as a whole, it's a non necessary to supply an explicit template argument for the function template.
Charles Bailey
This is really helpful, thanks!
Shamster