Finding dupilcate entry in a STL

[ken.carlino]

Hi,

I have a function which check if there is duplicate entries in a STL
list:

bool hasDuplicateY() {

sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
AList::iterator iter;

iter = adjacent_find ( _aList.begin(), _aList.end(), SameY());

if (iter == _aList.end())

return false;
else
return true;
}

bool SameY::operator()( A* bd1, A* bd2)
{
return bd1->y == bd2->y;
}
template<class T> struct sort_y_comparator : public
binary_function<T,T,bool>
{
sort_y_comparator() {}

bool operator()(const T r1, const T r2) const
{
return (r1->y < r2->y);
}
};
But the above function always return true even if there is no
duplication in the list.
Can you please tell me what have I done wrong?

Thank you.

[Thomas Tutone]

ke*********@gmail.com wrote:

I have a function which check if there is duplicate entries in a STL
list:

bool hasDuplicateY() {

sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
You can't use std::sort on a std::list, because a std::list doesn't
have random access iterators. I'm surprised this even compiled. Use
std::list member function list::sort() instead.
AList::iterator iter;

iter = adjacent_find ( _aList.begin(), _aList.end(), SameY());

if (iter == _aList.end())

return false;
else
return true;
Why not just:

AList::iterator iter = adjacent_find(_aList.begin(), _aList.end(),
SameY());
return iter!=_aList.end();

or even just:

return adjacent_find(_aList.begin(),
_aList.end(),
SameY()) != _aList.end();
}

bool SameY::operator()( A* bd1, A* bd2)
{
return bd1->y == bd2->y;
}
template<class T> struct sort_y_comparator : public
binary_function<T,T,bool>
{
sort_y_comparator() {}
Many would recommend that you omit that constructor if the default will
do just fine.

bool operator()(const T r1, const T r2) const
{
return (r1->y < r2->y);
}
};
But the above function always return true even if there is no
duplication in the list.
Can you please tell me what have I done wrong?

First, fix the problem with std::sort. Then, if you're still having
the problem, re-post, this time including code we can actually compile,
rather than just a snippet.

Good luck.

Best regards,

Tom

[Thomas Tutone]

Thomas Tutone wrote:

Many would recommend that you omit that constructor if the default will
do just fine.

I meant to say that many would recommend that you omit that constructor
if the compiler-generated constructor will do just fine.

Best regards,

Tom

[Nitin Motgi]

ke*********@gmail.com wrote:

Hi,

I have a function which check if there is duplicate entries in a STL
list:

bool hasDuplicateY() {

sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
AList::iterator iter;

If you are using std::list they model the Reversible Containers who's
iterators are only bidirectional iterators. The sort you have used in
you program is a general algorithm applied to containers that support
Random Iterators. In order to sort the list of type std::list you can
use the sort provided by std::list using bidirectional iterators.

Change the following
sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
TO
_aList.sort(sort_y_comparator<A*>()); ==> Will sort your list.

-- Nitin Motgi

[Nitin Motgi]

ke*********@gmail.com wrote:

Hi,

I have a function which check if there is duplicate entries in a STL
list:

bool hasDuplicateY() {

sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
AList::iterator iter;

If you are using std::list they model the Reversible Containers who's
iterators are only bidirectional iterators. The sort you have used in
you program is a general algorithm applied to containers that support
Random Iterators. In order to sort the list of type std::list you can
use the sort provided by std::list using bidirectional iterators.

Change the following
sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
TO
_aList.sort(sort_y_comparator<A*>()); ==> Will sort your list.

-- Nitin Motgi

[Daniel T.]

In article <11*********************@g14g2000cwa.googlegroups. com>,
ke*********@gmail.com wrote:

Hi,

I have a function which check if there is duplicate entries in a STL
list:

bool hasDuplicateY() {

sort(_aList.begin(), _aList.end(), sort_y_comparator<A*>());
AList::iterator iter;

iter = adjacent_find ( _aList.begin(), _aList.end(), SameY());

if (iter == _aList.end())

return false;
else
return true;
}
As others have already said, the 'sort' above should be
_aList.sort(...), and this can be written much more compactly...

_aList.sort(sort_y_comparator<A*>());
return adjacent_find(_aList.begin(), _aList.end(), SameY()) !=
aList.end();

bool SameY::operator()( A* bd1, A* bd2)
{
return bd1->y == bd2->y;
}
template<class T> struct sort_y_comparator : public
binary_function<T,T,bool>
{
sort_y_comparator() {}

bool operator()(const T r1, const T r2) const
{
return (r1->y < r2->y);
}
};

I wouldn't make the above a template, the only types it can take are
ones that can handle "->y" which is pretty limited...

Did you notice how your sort_y_comparator and your 'SameY' look alot
alike? The only difference between them is the actual compare ('==' in
one and '<' in the other.) I would think you could factor out that
duplication...

struct A {
int y;
};

// better would be to make A a class and make this a member-function
int& getY( A* a ) {
return a->y;
}

bool hasDuplicateY( list<A*>& aList )
{
aList.sort(f_gx_gy(less<int>(), ptr_fun(&getY)));
return adjacent_find(aList.begin(), aList.end(),
f_gx_gy(equal_to<int>(), ptr_fun(&getY))) != aList.end();
}

To make the above work, you need a composer like this:

template <typename Op1, typename Op2, typename Op3>
class f_gx_hy_t: public std::binary_function<typename
Op2::argument_type, typename Op3::argument_type, typename
Op1::result_type>
{
Op1 fn1;
Op2 fn2;
Op3 fn3;
public:
f_gx_hy_t(const Op1& f, const Op2& g, const Op3& h):
fn1(f), fn2(g), fn3(h) { }

typename Op1::result_type operator()(const typename
Op2::argument_type& x, const typename Op3::argument_type& y) const {
return fn1(fn2(x), fn3(y));
}
};

template <typename Op1, typename Op2>
inline f_gx_hy_t<Op1, Op2, Op2>
f_gx_gy(const Op1& f, const Op2& g) {
return f_gx_hy_t<Op1, Op2, Op2>(f, g, g);
}
Presumably, this can be done even simpler using the boost::lambda
library.
<http://www.boost.org/doc/html/lambda.html>

--
Magic depends on tradition and belief. It does not welcome observation,
nor does it profit by experiment. On the other hand, science is based
on experience; it is open to correction by observation and experiment.