Trouble using std::equal_range

  • Thread starter Matthias Kaeppler
  • Start date
M

Matthias Kaeppler

Hello,

I am having trouble getting std::equal_range to perform as I wish, and I
can't find my error.

Here's the situation:
I have a vector of pointers to filesystem path objects (a file list,
basically). This vector is partitioned each time the file list was
rebuilt into paths which are directories and paths which are not. The
directories comes first.
Here is the code so far:

// build file list
// ...
m_first_file = partition(m_files.begin(), m_files.end(),
bind(&is_directory, *_1));

m_first_file is an iterator to the first file in the vector.
Now I sort both partitions using std::stable_sort:

std::stable_sort( m_files.begin(), m_first_file, SortedByNameA() );
std::stable_sort( m_first_file, m_files.end(), SortedByNameA() );

The predicate looks like this:

struct SortedByNameA
: std::binary_function<const boost::filesystem::path*,
const boost::filesystem::path*,bool>
{
bool operator() (const boost::filesystem::path *lhs,
const boost::filesystem::path *rhs) const {
std::string path1( lhs->leaf() );
std::string path2( rhs->leaf() );
boost::algorithm::to_lower( path1 );
boost::algorithm::to_lower( path2 );
return path1 < path2;
}
};

Okay, this was only the background story. Here comes the critical part:
At some point of program execution I now want to find a specific path in
this vector. Until recently I used std::find_if( <path equals some
pathname> ).
This however is kind of a waste of time, since the vector is sorted, so
I can as well use a binary search algorithm and may probably get away
consuming less time. I decided to pick std::equal_range to do that:

path p( "<some path>" );

// first search the directory partition
FilePtrIterPair pair = std::equal_range( m_files.begin(), m_first_file,
&p, EqualPaths() );

if( pair.first != pair.second ) // found it
else // search the non-directory partition analogous to above

[Note: FilePtrIterPair is a typedef for
pair<vector<path*>::iterator,vector<path*>::iterator> >]

The predicate is defined as follows:

struct EqualPaths
: std::binary_function<const boost::filesystem::path*,
const boost::filesystem::path*,bool>
{
bool operator() (const boost::filesystem::path *lhs,
const boost::filesystem::path *rhs) const {
std::string path1( lhs->leaf() );
std::string path2( rhs->leaf() );
boost::algorithm::to_lower( path1 );
boost::algorithm::to_lower( path2 );
return !(path1 < path2) && !(path2 < path1);
}
};


Now, this yields strange results. I suppose I have undefined behavior
somewhere, but I can't figure out where and why.

Any hints would be welcome.
 
I

Ivan Vecerina

Matthias Kaeppler said:
I am having trouble getting std::equal_range to perform as I wish, and I
can't find my error. ....
The predicate is defined as follows:

struct EqualPaths
: std::binary_function<const boost::filesystem::path*,
const boost::filesystem::path*,bool>
{
bool operator() (const boost::filesystem::path *lhs,
const boost::filesystem::path *rhs) const {
std::string path1( lhs->leaf() );
std::string path2( rhs->leaf() );
boost::algorithm::to_lower( path1 );
boost::algorithm::to_lower( path2 );
return !(path1 < path2) && !(path2 < path1);
}
};


Now, this yields strange results. I suppose I have undefined behavior
somewhere, but I can't figure out where and why.

The predicate you pass to equal range should be the same
as the one used to sort the sequence -- equivalent to operator <.
;)

Cheers,
Ivan
 
M

Matthias Kaeppler

Ivan said:
The predicate you pass to equal range should be the same
as the one used to sort the sequence -- equivalent to operator <.
;)

Cheers,
Ivan

Oh, hehe, this explains a LOT of course. Thanks Ivan, works like a
breeze now.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top