How do we apply std::max_element to a vector of structs (vector<myStruct>)?

[FortranLevelC++]

When we consider a vector that has only one kind of element, such as int or double, etc, it is very easy to understand the syntax of std::max_element to find the maximum value of the elements of a vector.

But what if the elements of the vector are structs and we want to find only the maximum of one type of element in the structs in the vector?

So far wrote this code only for vectors that contain simple elements, and this code is working, but how do we write the same code for a more general vector whose elements are structs (to find the maximum of just one type of element inside the vector structs?

#include <vector>
#include <algorithm>


using namespace std;
struct S {
  string myWord;
  int a;
  int b;
};


using namespace std;


int main()
{ 
   vector<int> vecInt;
   vector<S> vec;


   for(int j=0; j<10; j++) { //Initialize:
     vecInt.push_back(j);
     S tempS;
     tempS.a = j;
     tempS.b = 5+j;
     tempS.myWord = "aWord";
     vec.push_back(tempS);
   }
  
   std::vector<int>::iterator result;
   std::vector<int>::iterator tempIter;
   size_t range = 3 ;
   
    // So far I have only applied std::max_element to the case of a 
    // simple vector of ints:
   for(vector<int>::iterator itr=vecInt.begin( ) + 6  ;  itr != vecInt.end( )  ;  itr++)
   {  
      size_t index = itr - vecInt.begin();
      vector<int>::iterator first = itr -range;
      //std::max_element(first, last) returns an answer between [first,last) as half-open interval
      //and so we need to further increase last=itr+1 as follows 
      // (or else the last element does not get compared):
      vector<int>::iterator last = itr +  1 ;
      result = std::max_element( first , last );
      cout << "max element of vecInt between slot " << index -range  << " and slot "
         << index << " is: " <<  *result << endl;
      cout << "vecInt[" << index << "] = " << *itr << endl;
      
   }


}

And this is the output of the above program, which works for any range of elements in the simpler vector vector<int> vecInt:

max element of vecInt between slot 3 and slot 6 is: 6
vecInt[6] = 6
max element of vecInt between slot 4 and slot 7 is: 7
vecInt[7] = 7
max element of vecInt between slot 5 and slot 8 is: 8
vecInt[8] = 8
max element of vecInt between slot 6 and slot 9 is: 9
vecInt[9] = 9

But how does C++ restrict the std::max_element function to just one kind of element inside the structs contained in the vector, how do we write the code?

For instance how can we focus on the elements "a" in the struct S above, to find the maximum of vec[i].a over a range of indices i?

[antred]

Read this max_element - C++ Reference

The comparisons are performed using either operator< for the first version, or comp for the second;

[...]
comp Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool. The value returned indicates whether the element passed as first argument is considered less than the second.
The function shall not modify any of its arguments.
This can either be a function pointer or a function object.

[FortranLevelC++]

Read this max_element - C++ Reference

Many thanks, but I still don't understand how to apply this same syntax to the more complicated types of vectors such as

  
vector<S> vec_S,  where S is a structure of the form :
struct S { string myWord; int a; int b;};

(In this case I would like to restrict std::max_element to find only the maximum of the elements a of the form S.a inside the vector vec_S.)

[phantomotap]

O_o

What don't you understand?

The binary comparator passed to "STL" functions may be standard issue functions.

Let's start with the basics, do you know how to write a function to compare to `S' type object using only `a' as a key?

Soma

[FortranLevelC++]

O_o

What don't you understand?

The binary comparator passed to "STL" functions may be standard issue functions.

Let's start with the basics, do you know how to write a function to compare to `S' type object using only `a' as a key?

Soma

What I don't understand is how to extract the 'a' from the iterators written for the vector<S>.

To find the maximum of two 'S' type objects with respect to the key 'a', I was able to write this code:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;
struct S {
  string myWord;
  int a;
  int b;
};



S & Max_a( S & ,  S & );


int main()
{ 
   vector<S> vec;


   for(int j=0; j<10; j++) { //Initialize:
     S tempS;
     tempS.a = j;
     tempS.b = 5+j;
     tempS.myWord = "aWord";
     vec.push_back(tempS);
   }
   
   S S0, S1;


   S0 = vec[0];
   S1 = vec[3];


   S Maximum;
   Maximum = Max_a( S0, S1);


   cout << "Maximum.a = " << Maximum.a << endl;


}


S & Max_a( S & S_0, S &  S_1 )
{  
     if (S_0.a >= S_1.a) 
       return S_0;
     else 
       return S_1;
}

And this is the output:

Maximum.a = 3

But I still don't know how to extract the same kind of information from the iterators as in the std::max_element to restrict the comparison to only the key 'a'.

Many thanks.

[antred]

Look, you can pass your own comparison function / functor / lambda to std::max_element(). That comparison function takes two arguments ... const references to 2 instances of your S-struct. Then in that function you implement whatever comparison criteria you want. If you only want to look at the .a members, there's nothing that stops you from doing that.

[phantomotap]

I still don't know how to extract the same kind of information from the iterators as in the std::max_element to restrict the comparison to only the key 'a'.

O_o

Well, you have the idea as far as `Max_a' is concerned. (Though, as antred suggests, the comparator should use constant references.)

Also, as antred says, the comparator you pass to `std::max_element' does not operate on iterators.

That said, the standard iterators are an abstraction of pointers, and you should learn to use them regardless of what you do with `std::max_element'.

S *S0 = new S;
S *S1 = new S;

With this `S0' and `S1', do you know what to change for `Max_a'? That is, do you know how to write `Max_a' in terms of pointers?

That `Max_a' code, properly written, is just a change of type away: `vector<S>::const_iterator' instead of `S *'.

Soma

[FortranLevelC++]

O_o

Well, you have the idea as far as `Max_a' is concerned. (Though, as antred suggests, the comparator should use constant references.)

Also, as antred says, the comparator you pass to `std::max_element' does not operate on iterators.

That said, the standard iterators are an abstraction of pointers, and you should learn to use them regardless of what you do with `std::max_element'.

S *S0 = new S;
S *S1 = new S;

With this `S0' and `S1', do you know what to change for `Max_a'? That is, do you know how to write `Max_a' in terms of pointers?

That `Max_a' code, properly written, is just a change of type away: `vector<S>::const_iterator' instead of `S *'.

Soma

OK, this is the code that I wrote and seems to work. I have created a comparison function that is the optional third argument in std::max_element.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct S {
  string myWord;
  int a;
  int b;
};


static bool CompForMax_a( S & , S &);


int main()
{ 
   vector<S> vec;

   for(int j=0; j<10; j++) { //Initialize:
       S tempS;
       tempS.a = j;
       tempS.b = 5+j;
       tempS.myWord = "aWord";
       vec.push_back(tempS);
   }
    
   std::vector<S>::iterator result;
   result = std::max_element(vec.begin(), vec.end(), CompForMax_a);
   cout << "Maximum element S.a of vector<S> vec is at: " << std::distance(vec.begin(), result) << endl;
   cout << "---------------------------------------------" << endl;


   size_t range = 3 ;
   
   for(vector<S>::iterator itr=vec.begin( ) + 6  ;  itr != vec.end( )  ;  itr++)
   {  
      size_t index = itr - vec.begin();
      vector<S>::iterator first = itr -range;
      //std::max_element(first, last) returns an answer between [first,last) as half-open interval
      //and so we need to further increase last=itr+1 as follows 
      // (or else the last element does not get compared):
      vector<S>::iterator last = itr +  1 ;
      result = std::max_element( first , last, CompForMax_a  );
      cout << "max element of vec[i].a between slot " << index -range  << " and slot "
         << index << " is: " <<  (*result).a << endl;
      cout << "vec[" << index << "].a = " << (*itr).a << endl;
      
   }

}

static bool CompForMax_a( S & S_0 , S & S_1)
{
  return ( S_0.a < S_1.a );
}

And the output is:

Maximum element S.a of vector<S> vec is at: 9
---------------------------------------------
max element of vec[i].a between slot 3 and slot 6 is: 6
vec[6].a = 6
max element of vec[i].a between slot 4 and slot 7 is: 7
vec[7].a = 7
max element of vec[i].a between slot 5 and slot 8 is: 8
vec[8].a = 8
max element of vec[i].a between slot 6 and slot 9 is: 9
vec[9].a = 9



(Without being 100 % sure, since I have not yet mastered this subject completely).

[Elysia]

The arguments should be const ref.
If you have C++11, you can simplify it a bit more by having the sorter directly at the same place as the call to max_element:

result = std::max_element( first , last, [](const S & S_0 , const S & S_1) { return ( S_0.a < S_1.a ); });

[FortranLevelC++]

The arguments should be const ref.
If you have C++11, you can simplify it a bit more by having the sorter directly at the same place as the call to max_element:

result = std::max_element( first , last, [](const S & S_0 , const S & S_1) { return ( S_0.a < S_1.a ); });

Many thanks. Placing the sorting function inside the std::max_element is definitely what I need to make the code more self-contained.

But I have a question about the foundations of C++ in this context. I would like to avoid creating the additional comparison function altogether, and use std::max_element more directly as if the vector were made of simple componenets like int. For instance, It seems to me that once we have the vector<S> vec , then it should be possible to take the "projection" of vec onto a simpler vector vec<int> vec_a , in such a way that each element vec[i] of vec would be projected onto vec_a[i] by means of the equality vec_a[i] = vec[i].a, and this should be done by using references (without the expensive copying of the all elements) only. Then, once we have projected the 'a' type parts of the vector<S> vec onto a vector vector<int> v_a, then we could apply std::max_element directly to v_a , with the benefit of not having to create that additional comparison function.
Or alternatively, there might we a way of deriving a "projected iterator for vector<int> from the iterator of vector<S>", and then with this projected iterator it might be ( this is my imagination only ) possible to apply std::max_element, once again without having to write the additional comparison function.

For example, the syntax might perhaps look like:

vector<S> vec;
/*
 initialize and fill vec...
*/
 // using references, avoiding copying all elements by value:
vector<int> vec_a = & Projection_of_vector (vec,  'S.a') ;
Maximum = *std::max_element(vec_a.begin(), vec_a.end());

Is this possible?

Or perhaps there might instead be a syntax to take the projection of the iterator of vector<S> onto the iterator of vector<int> for the element a, like this:

[code]

vector<int> iterator itr_a = & Projection_of_Iterator(vector<S> iterator);
Maximum = *std::max_element( ??);

[Elysia]

You can define how comparisons of different S objects is done via operator overloading. Example:

struct S
{
	std::string myWord;
	int a;
	int b;
	friend auto operator < (const S& left, const S& right) -> bool { return left.a < right.b; }
};

(If you don't have a C++11 compiler, you should declare the operator as
friend bool operator < (const S& left, const S& right))

That's all. max_element will use operator < to determine which object S is smaller than the other, so if you define that operator for S, everything works beautifully without using a comparator function.

[FortranLevelC++]

You can define how comparisons of different S objects is done via operator overloading. Example:

struct S
{
    std::string myWord;
    int a;
    int b;
    friend auto operator < (const S& left, const S& right) -> bool { return left.a < right.b; }
};

(If you don't have a C++11 compiler, you should declare the operator as
friend bool operator < (const S& left, const S& right))

That's all. max_element will use operator < to determine which object S is smaller than the other, so if you define that operator for S, everything works beautifully without using a comparator function.

Many thanks, it is good to know that operator overloading would also work. Of course, I am beginning to use C++11 also, and g++ seems to work well with Ubuntu Linux. But in the code that you wrote, it seems to me that in the line

friendauto operator < (constS& left, constS& right) -> bool{ return left.a < right.b; }

you intended to write:

friendauto operator < (constS& left, constS& right) -> bool{ return left.a < right.a; }

so that the "<" focuses only on the 'a' components of S, without involving b yet.

However, what if we also want to compare the 'b' components on other occasions?

Perhaps we can put two friend functions inside the struct, one for 'a' and one for 'b', like this:

struct S
{
    std::string myWord;
    int a;
    int b;
    friend auto operator < (const S& left, const S& right) -> bool { return left.a < right.a; }
    friend auto operator < (const S& left, const S& right) -> bool { return left.b < right.b; }
};

But in this case, how will the compiler know which version of "<" we intended to use when we apply the std::max_element() function, was it for the the component 'a' or 'b'? How would you then write the entire code?

[phantomotap]

it should be possible to take the "projection" of vec onto a simpler vector vec<int> vec_a

O_o

This idea is possible in several dozen different ways.

should be done by using references (without the expensive copying of the all elements)

Certainly, using a container of references is a valid approach, but you would still have the linear operation of obtaining a reference to each object.

with the benefit of not having to create that additional comparison function

Of course, this is the real problem with container adaptation.

The cost of creating such container adapters is more expensive than creating a simple comparison function.

there might we a way of deriving a "projected iterator for vector<int> from the iterator of vector<S>"

No. That is the wrong approach, and will not do what you wish.

Adapting each iterator, without deriving from an existing iterator, will get the same job done as you imagine of your idea.

this projected iterator it might be ( this is my imagination only ) possible to apply std::max_element, once again without having to write the additional comparison function

Unless you are quite skilled, you can't make a trivial generic "member accessing" iterator adapter, but yes, you can create an iterator which adapts an existing iterator into doing something very specific for comparisons sake. You would indeed then only need to call upon these iterators as part of the `std::mex_element' statement, but the creation of this facility is, I imagine, beyond your current skill.

(@Elysia: Don't rush to provide the code. If he insists on such a facility, guide him along the creation so the he can learn as you have.)

You can create a class specific versions simply enough, but as before, creating such an adapter is far more complex that simply creating a function. You are only going to get real mileage out of such a facility if it is generic enough to be useful for most classes.

I can guide you in this, but it will be extremely difficult. I suppose you may get lucky enough to get code from someone else, but I will not be giving you anything other than examples.

However, what if we also want to compare the 'b' components on other occasions?

Use the named comparator instead of the operator exactly as you've already learned.

But in this case, how will the compiler know which version of "<" we intended to use when we apply the std::max_element() function, was it for the the component 'a' or 'b'? How would you then write the entire code?

The compiler would not know; such code could not be written.

Elysia gave you a way to do what you needed in the case where you were interested in a "canonical sort".

A "canonical sort" is the way you intend a class to be "collated", and you specify "collation" order by a "key-weighted" sort considering all relevant members, and you would use operator overloading to provide the interface.

A "key-weighted" sort is a sort that considers the order by multiple values each having a particular priority; you would, for example, compare first by `a', then `b', and finally `c' such that objects with sameness over `a' and `b' are sorted by `c'.

This "canonical sort" is extremely useful, but if you want a specific sort, you will need to consider a named function.

I have been using "sort" because "collation" order as provided by a "strict weak ordering" as intended by the binary comparators of the `std::max_element' are used everywhere within the "STL".

In other words, do your job correctly, and the binary comparator you write will be useful for much of the standard algorithms.

Soma

[Elysia]

Many thanks, it is good to know that operator overloading would also work. Of course, I am beginning to use C++11 also, and g++ seems to work well with Ubuntu Linux. But in the code that you wrote, it seems to me that in the line

friendauto operator < (constS& left, constS& right) -> bool{ return left.a < right.b; }

you intended to write:

friendauto operator < (constS& left, constS& right) -> bool{ return left.a < right.a; }

so that the "<" focuses only on the 'a' components of S, without involving b yet.

Yes, that was a typo.

However, what if we also want to compare the 'b' components on other occasions?

The idea I showed here was a simple one. The operator < defines how one object S would be less than another object. In this case, I just picked one typical approach to doing this.
But you have to think about the problem a little: if you have a car, then how would you define "one car to be less than another"? (Yes, I know, this makes no sense; but assume that it does.) You'd have to take into account, maybe, length, colour, maker, etc, etc. But the idea of this function is that I just give you two cards, and you tell me that the first one (left) is less than the other one (right). True or false. How you do that is up to you, but you must do it inside that function by judging all the criterias and necessary information.

Just a silly example to demonstrate the point:

friend auto operator < (const XCar& left, const XCar& right) -> bool { return (left.GetColor() < right.GetColor()  && left.GetLength() < right.GetLength(); }

I can chain several things in the logic there, if you want. The important thing is to return true, or false. It's not a complete example, and it might not even work, but it might give you some ideas.

Perhaps we can put two friend functions inside the struct, one for 'a' and one for 'b', like this:

struct S
{
    std::string myWord;
    int a;
    int b;
    friend auto operator < (const S& left, const S& right) -> bool { return left.a < right.a; }
    friend auto operator < (const S& left, const S& right) -> bool { return left.b < right.b; }
};

But in this case, how will the compiler know which version of "<" we intended to use when we apply the std::max_element() function, was it for the the component 'a' or 'b'? How would you then write the entire code?

Nope, won't compile. You can only have one of the same operator since they must conform to a unique signature.

(@Elysia: Don't rush to provide the code. If he insists on such a facility, guide him along the creation so the he can learn as you have.)

You are right. I did not think such a small example (which I didn't write with the OP's specific problem in mind) would harm, though. I just wrote a typical operator. I didn't actually really factors the OP's code or needs into it. But if you disapprove, I'll be more careful.

[phantomotap]

You are right. I did not think such a small example (which I didn't write with the OP's specific problem in mind) would harm, though. I just wrote a typical operator. I didn't actually really factors the OP's code or needs into it. But if you disapprove, I'll be more careful.

O_o

Sorry, there has been some confusion.

The example you've already posted, the trivial operator, is probably the least necessary to show how operator overloading solves the problem.

I'm fine with that example.

I was referring to the "iterator adapter" of which he dreams; that would be a very complex beast with many avenues ripe for learning.

I would disapprove of you posting "iterator adapter" code.

Soma