By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
445,778 Members | 1,947 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 445,778 IT Pros & Developers. It's quick & easy.

Trouble using std::equal_range

P: n/a
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*>::iterat or> >]

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.

--
Matthias Kaeppler
Jul 23 '05 #1
Share this Question
Share on Google+
2 Replies


P: n/a
"Matthias Kaeppler" <no****@digitalraid.com> wrote in message
news:d3*************@news.t-online.com...
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
--
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Jul 23 '05 #2

P: n/a
Ivan Vecerina wrote:
"Matthias Kaeppler" <no****@digitalraid.com> wrote in message
news:d3*************@news.t-online.com...
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


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

--
Matthias Kaeppler
Jul 23 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.