C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  question: sort() a vector          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message John Guest Posted: Sat Apr 16, 2005 5:42 pm    Post subject: question: sort() a vector I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? Thanks, --j [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Antoun Kanawati Guest Posted: Sun Apr 17, 2005 3:38 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? Any reason you cannot capture the first element in the state of the comparator? that is: use a function object instead of a plain function. -- A. Kanawati [email]NO.antounk.SPAM (AT) comcast (DOT) net[/email] [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Valentin Samko Guest Posted: Sun Apr 17, 2005 3:40 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. create a functor and pass it to the sort function, i.e. struct mysortpredicate { bool operator()(const T& a, const T& b) const }; mysortpredicate p; sort(..., p); [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Alberto Barbati Guest Posted: Sun Apr 17, 2005 5:59 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? First of all, please notice that the comparison function shall not change behaviour during its lifetime. In particular, given any two values a and b, repeatedly calling comparison(a, b) shall always produce the same result. So the comparison shall not depend on the value of "first element of the vector" as such value may change during the sort. Failure to comply to this requirement will compromise the result of the sort operation. However, if you mean to use *a copy* of the value of the first element of the vector *before the sort*, the copy won't change value during the sort and everybody's happy. Providing parameters to the comparison function is very simple. The key point is that the third parameter of std::sort need not be a function, but can be a functor. A functor (or function object) is an object that implements operator(). An example of functor with one parameter is the following: struct Comparison { ParamType mParam; Comparison(const ParamType& param) : mParam(param) {} bool operator()(const ValueType& a, const ValueType& b) const { // return true if a is "less than" b, false otherwise } }; then you just call sort like this: std::sort(v.begin(), v.end(), Comparison(param)); You can have as many parameters as you like, just make them members of the functor and provide a constructor to initialize them. Please notice that the functor must be copiable, so make sure that all members are also copiable if you don't want to provide a copy constructor (remember that reference data members are *NOT* copiable). Please notice that operator() is declared const, so that the compiler will catch any inadvertent attempt to modify the data members (as we said at the beginning, you must not change the behaviour on the way). HTH, Alberto [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top tmk@netvision.net.il Guest Posted: Sun Apr 17, 2005 6:00 pm    Post subject: Re: question: sort() a vector You can use a functor class with attributes containing the data you need, this might be a reference to the whole vector. Define an object with this data, and use it as a comparison function. Don't forget to define the right 'operator ()' method for the comparison, and the constructor to insert the data ... Michael John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I don't see why it's a weird requirement. It's a standard practice in C++ to put info into functor objects. BTW, I think it's similar to keeping data in lambda-expressions in Scheme: for every case you create a different function. Quote: I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Daniel Cer Guest Posted: Sun Apr 17, 2005 6:03 pm    Post subject: Re: question: sort() a vector You could define your own iterator and then pass that to sort(). The iterator could then be defined such that each time an element from the vector was retrieved, it would return a pair consisting of: <first_element_in_the_vector, element_at_current_position> Your custom comparison function would then receive two such pairs, with which it should then be possible to do the comparison you described. That is, compare two elements from the vector using not only the values of the elements themselves, but also the value of the first element in the vector (all without using global variables). -Dan John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? Thanks, --j [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Heinz Ozwirk Guest Posted: Sun Apr 17, 2005 6:03 pm    Post subject: Re: question: sort() a vector "John" <weekender_ny (AT) yahoo (DOT) com> schrieb im Newsbeitrag news:1113629777.349636.159770 (AT) o13g2000cwo (DOT) googlegroups.com... Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? You don't need a "compare function". An instance of any class that implements operator() can be used as well. Something like class Compare { public: Compare(ElementType const& elem) : m_elem(elem) {} bool operator()( ElementType const& lhs, ElementType const& rhs ) const { return /* your implementation of lhs < rhs */; } private: ElementType m_elem; }; ... std::vector ... std::sort(elements.begin(), elements.end(), Compare(elements[0])); Even though it is possible to use a relation that is depending on the first element of the seqeunce to be sorted, I don't think that would be a very good idea. If you have an element that determines the ordering of a sequence, that is a very distinguished element and it is worth to keep it apart of the sequence to sort. Otherwise it may be surpising if you sort the sequence twice. HTH Heinz [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top ShaneG Guest Posted: Sun Apr 17, 2005 6:05 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? This sounds like a very odd thing to do (what happens if when you sort, it changes the first element?) But, in general the way to do something like this would be to provide a functor as the comparison operator. This is a class with an operator(). Since the functor is a class, you can put whatever data you want into it, and use that data in the operator(), which will be invoked to do the comparison. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carlos Moreno Guest Posted: Sun Apr 17, 2005 6:05 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. You do see that the first element will no longer be the first element after the sort function starts doing its job, right? Quote: I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. The magic of function objects! Perhaps a function object that could be initialized with the first element? Say that the problem were counting how many elements are divisible by the first element (assuming all non-zero integer values, or at least the first one non-zero): class divisible_by { int divisor; public: divisible_by (int d) : divisor(d) {} bool operator() (int n) const { return n % divisor == 0; } }; count_if (values.begin(), values.end(), divisible_by (values.front())); Is this compatible with what you're looking for? Carlos -- [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Carl Barron Guest Posted: Sun Apr 17, 2005 6:06 pm    Post subject: Re: question: sort() a vector John <weekender_ny (AT) yahoo (DOT) com> wrote: Quote: I have a wierd requirement and I do not see any clean way of coding (Maybe its 2:00am and my mind is not working, or maybe the problem really deserves attention). I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? if the 'first member' is the first member before the sort then a functor can hold it, providing that its operator () is a weak ordering, it can be used with std::sort. if the 'first member' is the current first member during the sort the function involve is not weak_ordering since pred(x,y) does not return the same values for x,y with repeated calls and the same x and y. template <class T> class strange_compare { T x; public: strange_compare(const T &a)(a){} bool operator () (const T &x,const T &y) const { // ... } }; template <class T> strance_compare<T> make_strange_compare(const T &x) { return strange_compare } // ,,, std::sort(strange_data.begin(),strange_data.end(), make_strange_compare(data.front())); [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ray Lischner Guest Posted: Sun Apr 17, 2005 6:07 pm    Post subject: Re: question: sort() a vector On Saturday 16 April 2005 01:42 pm, John wrote: Quote: I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. That's what function objects are for, e.g.,: struct compare { compare(int first) : first_(first) {} bool operator()(int lhs, int rhs) { // perform the comparison, using first_ as needed } private: const int first_; }; ..... std::vector<int> data; ..... assert(not data.empty()); std::sort(data.begin(), data.end(), compare(data.front())); -- Ray Lischner, author of C++ in a Nutshell http://www.tempest-sw.com/cpp [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top James Kanze Guest Posted: Sun Apr 17, 2005 9:02 pm    Post subject: Re: question: sort() a vector John wrote: Quote: I want to use sort() with my own implementation of the comparison function to sort a vector, BUT, the comparison function is dependent on the 1st element of the vector. I would have liked to send three parameters to the compare function of sort(), which I do not see how to do. And I do not see any other clean way of implementing this. I do not want to make this first element a global variable. Any ideas on how this could be done? The initial first element, I hope. If you want the current first element (possibly changed by sort along the way), I doubt that you can define a stable ordering relationship. For the initial first element, of course, the solution is easy; just use it a functional object with a local variable initialized with the first element. -- James Kanze mailto: [email]james.kanze (AT) free (DOT) fr[/email] Conseils en informatique orientée objet/ Beratung in objektorientierter Datenverarbeitung 9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] 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 (Moderated) 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.