C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Finding dupilcate entry in a STL          C++Talk.NET Forum Index -> C++ language (comp.lang.c++) View previous topic :: View next topic   Author Message Guest Posted: Mon Jan 30, 2006 4:00 pm    Post subject: Finding dupilcate entry in a STL 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. Back to top Thomas Tutone Guest Posted: Mon Jan 30, 2006 6:00 pm    Post subject: Re: Finding dupilcate entry in a STL ken.carlino (AT) gmail (DOT) com wrote: Quote: 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. Quote: 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(); Quote: } 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. Quote: 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 Back to top Thomas Tutone Guest Posted: Mon Jan 30, 2006 10:00 pm    Post subject: Re: Finding dupilcate entry in a STL Thomas Tutone wrote: Quote: 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 Back to top Nitin Motgi Guest Posted: Tue Jan 31, 2006 12:00 am    Post subject: Re: Finding dupilcate entry in a STL ken.carlino (AT) gmail (DOT) com wrote: Quote: 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 Back to top Nitin Motgi Guest Posted: Tue Jan 31, 2006 12:00 am    Post subject: Re: Finding dupilcate entry in a STL ken.carlino (AT) gmail (DOT) com wrote: Quote: 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 Back to top Daniel T. Guest Posted: Tue Jan 31, 2006 1:00 pm    Post subject: Re: Finding dupilcate entry in a STL In article <1138636282.225433.60450 (AT) g14g2000cwa (DOT) googlegroups.com>, ken.carlino (AT) gmail (DOT) com wrote: Quote: 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(); Quote: 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. Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ language (comp.lang.c++) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.