Trouble using std::equal_range

Discussion in 'C++' started by Matthias Kaeppler, Apr 6, 2005.

  1. 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.

    --
    Matthias Kaeppler
    Matthias Kaeppler, Apr 6, 2005
    #1
    1. Advertising

  2. "Matthias Kaeppler" <> wrote in message
    news:d31aqo$2ur$04$-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
    Ivan Vecerina, Apr 6, 2005
    #2
    1. Advertising

  3. Ivan Vecerina wrote:
    > "Matthias Kaeppler" <> wrote in message
    > news:d31aqo$2ur$04$-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
    Matthias Kaeppler, Apr 6, 2005
    #3
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Peter Jansson
    Replies:
    5
    Views:
    6,301
    Ivan Vecerina
    Mar 17, 2005
  2. Jeffrey Walton
    Replies:
    10
    Views:
    938
    Mathias Gaunard
    Nov 26, 2006
  3. Ole Nielsby
    Replies:
    1
    Views:
    1,176
    Ole Nielsby
    Dec 29, 2008
  4. duey

    equal_range

    duey, Mar 6, 2009, in forum: C++
    Replies:
    1
    Views:
    395
  5. duey
    Replies:
    4
    Views:
    700
    Andrew Koenig
    Mar 8, 2009
Loading...

Share This Page