Get first and last iterator of a sequence where some condition istrue

[Christopher]

I need to do what the title says.
I have a vector of objects and I have sorted them using std::sort, by
the attributes I am interested in.
I now need to extract the ranges that have those attributes being
equal.

How do I do it?

I can get an iterator to the first using plain old std::find, but am
unsure how to get the last.

I looked at equal range, but it confused me.

 

[Michael DOUBEZ]

I need to do what the title says.
I have a vector of objects and I have sorted them using std::sort, by
the attributes I am interested in.
I now need to extract the ranges that have those attributes being
equal.

How do I do it?

I can get an iterator to the first using plain old std::find, but am
unsure how to get the last.

I looked at equal range, but it confused me.

The equal_range() function returns the range of elements between first
and last that are equal to the value parameter according to the
comparison function used to sort them.

the syntax is:
struct AtributeCompare;//the comparator used to sort them

std:air<iterator,iterator> range=std::equal_range(
begin(),end() //range of search
,value //value to compare to
,AtributeCompare() //comparison functor
);

Then range.first is the iterator to the first element of the range that
is equal to the value and range.second is the iterator to the element
one past the range (like end()).

Note: if you are using boost, there is the boost::tie() helper that can
be used to assign them automatically:

iterator begin_range;
iterator end_range;

boost::tie(begin_range,end_range)=std::equal_range( ... );

 

[Christopher]

The equal_range() function returns the range of elements between first
and last that are equal to the value parameter according to the
comparison function used to sort them.

the syntax is:
struct AtributeCompare;//the comparator used to sort them

std:air<iterator,iterator> range=std::equal_range(
      begin(),end()      //range of search
     ,value             //value to compare to
     ,AtributeCompare() //comparison functor
     );

Then range.first is the iterator to the first element of the range that
is equal to the value and range.second is the iterator to the element
one past the range (like end()).

I gave it a shot. You say the same comparator that it was sorted with?
The compiler complains that my comparator does not have proper
arguments:
error C2664: 'bool DisplayModeEnumerator::SortByResolution:perator ()
(DisplayModeCapability &,DisplayModeCapability &)' : cannot convert
parameter 1 from 'const Resolution' to 'DisplayModeCapability &'

What is the comparator supposed to look like for the equal_range
function?


Comparator
------------------------------------------------------
/**
* Comparator to sort DisplayModeCapability objects by thier resolution
**/
struct SortByResolution
{
bool operator() (DisplayModeCapability & lhs, DisplayModeCapability
& rhs)
{
if( lhs.m_resolution < rhs.m_resolution )
{
return true;
}
return false;
}
};


Calling code
------------------------------------------------------
// Sort the display modes by resolution
std::sort(displayModeCaps.begin(), displayModeCaps.end(),
SortByResolution());

// Seperate the display modes by resolution
DisplayModeCapsByResolution displayModeCapsByResolution;

while( !displayModeCaps.empty() )
{
Resolution resolution = displayModeCaps.front().m_resolution;

std:air<DisplayModeCaps::iterator, DisplayModeCaps::iterator>
range =
std::equal_range(displayModeCaps.begin(), displayModeCaps.end(),
resolution, SortByResolution());

DisplayModeCaps temp(range.first, range.second);
displayModeCapsByResolution[resolution] = temp;

displayModeCaps.erase(range.first, range.second);
}

 

[Michael DOUBEZ]

I gave it a shot. You say the same comparator that it was sorted with?
The compiler complains that my comparator does not have proper
arguments:
error C2664: 'bool DisplayModeEnumerator::SortByResolution:perator ()
(DisplayModeCapability &,DisplayModeCapability &)' : cannot convert
parameter 1 from 'const Resolution' to 'DisplayModeCapability &'

Well, it cannot convert from const to non-const at least. Now I suppose
Resolution inherits from DisplayModeCapability.

What is the comparator supposed to look like for the equal_range
function?


Comparator
------------------------------------------------------
/**
* Comparator to sort DisplayModeCapability objects by thier resolution
**/
struct SortByResolution
{
bool operator() (DisplayModeCapability & lhs, DisplayModeCapability
& rhs)

Replace the signature with:
bool operator()(
const DisplayModeCapability & lhs,
const DisplayModeCapability& rhs
)const

 

[Christopher]

Well, it cannot convert from const to non-const at least. Now I suppose
Resolution inherits from DisplayModeCapability.

Replace the signature with:
bool operator()(
     const DisplayModeCapability & lhs,
     const DisplayModeCapability& rhs
     )const

Nay, Resolution is simply a member of DisplayModeCapability



#ifndef RESOLUTION_H
#define RESOLUTION_H

// Standard Includes
#include <string>


//------------------------------------------------------------------------------------------
/**
* Resolution
**/
struct Resolution
{
Resolution(unsigned width, unsigned height);
Resolution(const Resolution & rhs);
~Resolution();

Resolution & operator = (const Resolution & rhs);
bool operator == (const Resolution & rhs) const;
bool operator != (const Resolution & rhs) const;
bool operator < (const Resolution & rhs) const;
bool operator > (const Resolution & rhs) const;
bool operator <= (const Resolution & rhs) const;
bool operator >= (const Resolution & rhs) const;

/**
* Forms a string of form "WidthXHeight"
**/
const std::string AsString() const;


unsigned m_width;
unsigned m_height;
};



#endif
-------------------------------------------------------------

#ifndef BASEDISPLAYATTRIBUTES_H
#define BASEDISPLAYATTRIBUTES_H

// EngineX Includes
#include "Resolution.h"

// Windows Includes
#include <dxgi.h>

//------------------------------------------------------------------------------------------
/**
* This structure is not intended for use.
* It is only provided as a common set of attributes to inherit from.
**/
struct BaseDisplayAttributes
{
BaseDisplayAttributes(const unsigned adapterIndex,
const unsigned monitorIndex,
const Resolution & resolution,
const DXGI_FORMAT format,
const unsigned refreshRateNumerator,
const unsigned refreshRateDenominator);

BaseDisplayAttributes(const BaseDisplayAttributes & rhs);

~BaseDisplayAttributes();

BaseDisplayAttributes & operator = (const BaseDisplayAttributes &
rhs);
bool operator == (const BaseDisplayAttributes & rhs);
bool operator != (const BaseDisplayAttributes & rhs);


unsigned m_adapterIndex;
unsigned m_monitorIndex;
Resolution m_resolution;
DXGI_FORMAT m_backbufferFormat;
unsigned m_refreshRateNumerator;
unsigned m_refreshRateDenominator;
};


#endif



-------------------------------------------------------------
#ifndef DISPLAYMODECAPABILITY_H
#define DISPLAYMODECAPABILITY_H

// EngineX Includes
#include "DisplayMode.h"
#include "BaseDisplayAttributes.h"

// Windows Includes
#include <dxgi.h>

//------------------------------------------------------------------------------------------
/**
* Display mode capability
**/
struct DisplayModeCapability : public BaseDisplayAttributes
{
DisplayModeCapability(const unsigned adapterIndex,
const unsigned monitorIndex,
const Resolution & resolution,
const DXGI_FORMAT backbufferFormat,
const unsigned refreshRateNumerator,
const unsigned refreshRateDenominator);

DisplayModeCapability(const DisplayModeCapability & rhs);

~DisplayModeCapability();

DisplayModeCapability & operator = (const DisplayModeCapability &
rhs);

bool operator == (const DisplayModeCapability & rhs);

bool operator != (const DisplayModeCapability & rhs);


/**
* Query whether a display mode is acceptable for use according to
this display mode capabilty
**/
bool CompareDisplayMode(const DisplayMode & displayMode);
};

#endif

-----------------------------------------------------------

 

[Bart van Ingen Schenau]

Nay, Resolution is simply a member of DisplayModeCapability

Then you either need to create a dummy DisplayModeCapability object
with the requested Resolution, or you need to extend the comparator to
compare Resolution objects with DisplayModeCapability object.

The second option is the most elegant, but I am not sure if it is
required to work.
For that option, you need this comparator:

struct SortByResolution
{
bool operator()(
const DisplayModeCapability& lhs,
const DisplayModeCapability& rhs
)const
{
return (lhs.m_resolution < rhs.m_resolution);
}
bool operator()(
const Resolution& lhs,
const DisplayModeCapability& rhs
)const
{
return (lhs < rhs.m_resolution);
}
bool operator()(
const DisplayModeCapability & lhs,
const Resolution& rhs
)const
{
return (lhs.m_resolution < rhs);
}
};

Bart v Ingen Schenau