Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Trouble using std::equal_range

Reply
Thread Tools

Trouble using std::equal_range

 
 
Matthias Kaeppler
Guest
Posts: n/a
 
      04-06-2005
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*>::iterat or> >]

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.

--
Matthias Kaeppler
 
Reply With Quote
 
 
 
 
Ivan Vecerina
Guest
Posts: n/a
 
      04-06-2005
"Matthias Kaeppler" <(E-Mail Removed)> wrote in message
news:d31aqo$2ur$04$(E-Mail Removed)-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: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.


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





 
Reply With Quote
 
 
 
 
Matthias Kaeppler
Guest
Posts: n/a
 
      04-06-2005
Ivan Vecerina wrote:
> "Matthias Kaeppler" <(E-Mail Removed)> wrote in message
> news:d31aqo$2ur$04$(E-Mail Removed)-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: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.

>
>
> 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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Trouble using a Printer on a Wireless Home Network =?Utf-8?B?TGVzbGllIFVuZGVyd29vZA==?= Wireless Networking 2 12-26-2007 07:52 AM
i have no trouble to send , ihave trouble reciving mail --any ideas John Penney Computer Support 4 08-29-2006 08:45 PM
Trouble using a hostname in the address field for the Radius client in IAS Ned Cisco 0 08-11-2005 02:59 PM
Trouble using the vbTab in string F. Algr°y ASP .Net 1 01-06-2004 01:39 AM
trouble with caching or caching the trouble Hypo ASP .Net 6 08-01-2003 07:11 AM



Advertisments