ordering container contents using more than one key

[naoki]

Is it possible to sort a given container using two properties of the
content?

example:
class Rectangle {
int x, y;
int width, height;
};

std::list<Rectangle> my_list;

The main problem is to construct an R+ Tree.

 

[red floyd]

Is it possible to sort a given container using two properties of the
content?

example:
class Rectangle {
int x, y;
int width, height;
};

std::list<Rectangle> my_list;

Sure. Just define operator< as you want.

 

[naoki]

Sure. Just define operator< as you want.

operator< returns bool...

bool Rectangle:perator<( const Rectangle& r ) {
return this.x < r.x && this.y < r.y;
}

would work?

sample output data R(y, x) I need:
R(0, 7)
R(0, 8)
R(0, 9)
R(1, 4)
R(1, 5)
R(1, 6)
R(2, 1)
R(2, 2)
R(2, 3)

TIA

 

[Kai-Uwe Bux]

operator< returns bool...

bool Rectangle:perator<( const Rectangle& r ) {
return this.x < r.x && this.y < r.y;
}

would work?

Well, did you try?

sample output data R(y, x) I need:
R(0, 7)
R(0, 8)
R(0, 9)
R(1, 4)
R(1, 5)
R(1, 6)
R(2, 1)
R(2, 2)
R(2, 3)

Decide by primary value first; and only if those values tie, decide by
secondary value. E.g., with x as the primary value and y as the secondary
value, you could use something like:

bool Rectangle:perator<( const Rectangle& r ) const {
if ( this.x < r.x ) {
return ( true );
}
if ( r.x < this.x ) {
return ( false );
}
// at this point, this.x == r.x
return ( this.y < r.y );
}


Best

Kai-Uwe Bux

 

[naoki]

Well, did you try?


Decide by primary value first; and only if those values tie, decide by
secondary value. E.g., with x as the primary value and y as the secondary
value, you could use something like:

bool Rectangle:perator<( const Rectangle& r ) const {
if ( this.x < r.x ) {
return ( true );
}
if ( r.x < this.x ) {
return ( false );
}
// at this point, this.x == r.x
return ( this.y < r.y );

}

Best

Kai-Uwe Bux- Hide quoted text -

- Show quoted text -

Excuse me, I tried after post.
Thanks for the answer

 

[Juha Nieminen]

bool Rectangle:perator<( const Rectangle& r ) const {
if ( this.x < r.x ) {
return ( true );
}
if ( r.x < this.x ) {
return ( false );
}
// at this point, this.x == r.x
return ( this.y < r.y );
}

bool Rectangle:perator<(const Rectangle& r) const
{
if(x == r.x) return y < r.y;
return x < r.x;
}

 

[Kai-Uwe Bux]

bool Rectangle:perator<(const Rectangle& r) const
{
if(x == r.x) return y < r.y;
return x < r.x;
}

That works, too. I guess it is a classic idiom.

I switched to the way I presented for the following two reasons:

a) I can see the logic more clearly since the control flow reflects the
ranking of attributes: the primary entries get compared first, if they do
not decide (return), the secondary entries decide. No need to come back to
the primary entries at a later point.

b) This approach does not use operator==. This can be important in generic
programming where you might only have a strict ordering represented by
operator<.

Now, I just made it a habit to code lexicographic comparison as above.


Best

Kai-Uwe Bux

 

[Victor Bazarov]

bool Rectangle:perator<( const Rectangle& r ) const {
if ( this.x < r.x ) {
return ( true );
}
if ( r.x < this.x ) {
return ( false );
}
// at this point, this.x == r.x
return ( this.y < r.y );
}

[..]

Now, I just made it a habit to code lexicographic comparison as above.

<nit> I hope that you don't have a habit of using the "dot" operator
with 'this', but the "arrow", as in 'this->x' ... </nit>

V

 

[Kai-Uwe Bux]

Kai-Uwe Bux wrote:
bool Rectangle:perator<( const Rectangle& r ) const {
if ( this.x < r.x ) {
return ( true );
}
if ( r.x < this.x ) {
return ( false );
}
// at this point, this.x == r.x
return ( this.y < r.y );
}

[..]

Now, I just made it a habit to code lexicographic comparison as above.

<nit> I hope that you don't have a habit of using the "dot" operator
with 'this', but the "arrow", as in 'this->x' ... </nit>

Ah, good catch. I should have run it by a compiler.


Thanks

Kai-Uwe Bux