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:ath*,
const boost::filesystem:ath*,bool>
{
bool operator() (const boost::filesystem:ath *lhs,
const boost::filesystem:ath *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:ath*,
const boost::filesystem:ath*,bool>
{
bool operator() (const boost::filesystem:ath *lhs,
const boost::filesystem:ath *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 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:ath*,
const boost::filesystem:ath*,bool>
{
bool operator() (const boost::filesystem:ath *lhs,
const boost::filesystem:ath *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:ath*,
const boost::filesystem:ath*,bool>
{
bool operator() (const boost::filesystem:ath *lhs,
const boost::filesystem:ath *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.