nth_element question

Discussion in 'C++' started by bsabiston@gmail.com, Apr 19, 2009.

  1. Guest

    Hi,

    I've been trying to figure out why nth_element is going into an
    infinite loop. Is it a requirement that all of the elements in the
    list be different? Ie, can I call nth_element with a list like
    {0,248,248,0,248,248} and expect it to not go into a loop? Debugging
    it, it seems to just forever swap the first and last elements of that
    array.

    Thanks
    B
     
    , Apr 19, 2009
    #1
    1. Advertising

  2. wrote:
    > I've been trying to figure out why nth_element is going into an
    > infinite loop. Is it a requirement that all of the elements in the
    > list be different? Ie, can I call nth_element with a list like
    > {0,248,248,0,248,248} and expect it to not go into a loop? Debugging
    > it, it seems to just forever swap the first and last elements of that
    > array.


    std::nth_element requires random access iterators. You can't specify a
    list. And, no, the elements don't have to be unique. Read FAQ 5.8.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
     
    Victor Bazarov, Apr 19, 2009
    #2
    1. Advertising

  3. Guest

    On Apr 18, 8:44 pm, Victor Bazarov <> wrote:
    > wrote:
    > >   I've been trying to figure out why nth_element is going into an
    > > infinite loop.  Is it a requirement that all of the elements in the
    > > list be different?  Ie, can I call nth_element with a list like
    > > {0,248,248,0,248,248} and expect it to not go into a loop?  Debugging
    > > it, it seems to just forever swap the first and last elements of that
    > > array.

    >
    > std::nth_element requires random access iterators.  You can't specify a
    > list.  And, no, the elements don't have to be unique.  Read FAQ 5.8.
    >
    > V
    > --
    > Please remove capital 'A's when replying by e-mail
    > I do not respond to top-posted replies, please don't ask


    Thank you. But what would I need to do differently? I thought that
    you could pass ordinary pointers to functions that expect iterators.
    For example, I read this when looking up random-access iterators:

    "Because ordinary pointers have the same functionality as random
    access iterators, most of the generic algorithms in the C++ Standard
    Library can be used with conventional C++ arrays, as well as with the
    containers provided by the C++ Standard Library."

    Thanks
    B
     
    , Apr 19, 2009
    #3
  4. Pavel Guest

    wrote:
    > On Apr 18, 8:44 pm, Victor Bazarov <> wrote:
    >> wrote:
    >>> I've been trying to figure out why nth_element is going into an
    >>> infinite loop. Is it a requirement that all of the elements in the
    >>> list be different? Ie, can I call nth_element with a list like
    >>> {0,248,248,0,248,248} and expect it to not go into a loop? Debugging
    >>> it, it seems to just forever swap the first and last elements of that
    >>> array.

    >> std::nth_element requires random access iterators. You can't specify a
    >> list. And, no, the elements don't have to be unique. Read FAQ 5.8.
    >>
    >> V
    >> --
    >> Please remove capital 'A's when replying by e-mail
    >> I do not respond to top-posted replies, please don't ask

    >
    > Thank you. But what would I need to do differently? I thought that
    > you could pass ordinary pointers to functions that expect iterators.
    > For example, I read this when looking up random-access iterators:
    >
    > "Because ordinary pointers have the same functionality as random
    > access iterators, most of the generic algorithms in the C++ Standard
    > Library can be used with conventional C++ arrays, as well as with the
    > containers provided by the C++ Standard Library."
    >
    > Thanks
    > B


    I am slightly confused: that container of which you are trying to get
    the nth element ({0,248 etc) -- is it an array or a list? Maybe just
    give us a complete piece of code that does not work?

    -Pavel
     
    Pavel, Apr 19, 2009
    #4
  5. Guest

    On Apr 18, 11:37 pm, Pavel <dot_com_yahoo@paultolk_reverse.yourself>
    wrote:
    > wrote:
    > > On Apr 18, 8:44 pm, Victor Bazarov <> wrote:
    > >> wrote:
    > >>>   I've been trying to figure out why nth_element is going into an
    > >>> infinite loop.  Is it a requirement that all of the elements in the
    > >>> list be different?  Ie, can I call nth_element with a list like
    > >>> {0,248,248,0,248,248} and expect it to not go into a loop?  Debugging
    > >>> it, it seems to just forever swap the first and last elements of that
    > >>> array.
    > >> std::nth_element requires random access iterators.  You can't specify a
    > >> list.  And, no, the elements don't have to be unique.  Read FAQ 5.8.

    >
    > >> V
    > >> --
    > >> Please remove capital 'A's when replying by e-mail
    > >> I do not respond to top-posted replies, please don't ask

    >
    > > Thank you.  But what would I need to do differently?  I thought that
    > > you could pass ordinary pointers to functions that expect iterators.
    > > For example, I read this when looking up random-access iterators:

    >
    > > "Because ordinary pointers have the same functionality as random
    > > access iterators, most of the generic algorithms in the C++ Standard
    > > Library can be used with conventional C++ arrays, as well as with the
    > > containers provided by the C++ Standard Library."

    >
    > > Thanks
    > > B

    >
    > I am slightly confused: that container of which you are trying to get
    > the nth element ({0,248 etc) -- is it an array or a list? Maybe just
    > give us a complete piece of code that does not work?
    >
    > -Pavel


    It's a pointer to a memory location where I have stored a bunch of
    structs. I'm not at work right now, but I was basically trying to get
    this guy's code to work from this article:

    http://en.literateprograms.org/Median_cut_algorithm_(C_Plus_Plus)

    You can see that he passes in a regular pointer to his code which uses
    the pointers as iterators. But when I tried it, I get infinite loops
    out of the nth_element routine. Is it dependent on the compiler?
    Because this is for the NintendoDS and it's pretty limited.

    Is there any way to actually use 'real' iterators (I still haven't
    wrapped my head around what those really are) and somehow place them
    in this pre-allocated memory space that I need to use? There isn't
    enough memory for me to go allocating a bunch of memory for the
    iterators.

    Thanks
    B
     
    , Apr 19, 2009
    #5
  6. wrote:
    > On Apr 18, 11:37 pm, Pavel <dot_com_yahoo@paultolk_reverse.yourself>
    > wrote:
    >> wrote:
    >>> On Apr 18, 8:44 pm, Victor Bazarov <> wrote:
    >>>> wrote:
    >>>>> I've been trying to figure out why nth_element is going into an
    >>>>> infinite loop. Is it a requirement that all of the elements in the
    >>>>> list be different? Ie, can I call nth_element with a list like
    >>>>> {0,248,248,0,248,248} and expect it to not go into a loop? Debugging
    >>>>> it, it seems to just forever swap the first and last elements of that
    >>>>> array.
    >>>> std::nth_element requires random access iterators. You can't specify a
    >>>> list. And, no, the elements don't have to be unique. Read FAQ 5.8.

    [snip signatures]
    >> I am slightly confused: that container of which you are trying to get
    >> the nth element ({0,248 etc) -- is it an array or a list? Maybe just
    >> give us a complete piece of code that does not work?
    >>
    >> -Pavel

    >
    > It's a pointer to a memory location where I have stored a bunch of
    > structs. I'm not at work right now, but I was basically trying to get
    > this guy's code to work from this article:
    >
    > http://en.literateprograms.org/Median_cut_algorithm_(C_Plus_Plus)
    >
    > You can see that he passes in a regular pointer to his code which uses
    > the pointers as iterators.


    The pointers are treated as random access iterator. This is adapted
    through iterator_traits<>.

    > But when I tried it, I get infinite loops
    > out of the nth_element routine. Is it dependent on the compiler?
    > Because this is for the NintendoDS and it's pretty limited.


    I have seen nothing wrong in how he uses std::nth_element(). I guess the
    bug is in your code.


    > Is there any way to actually use 'real' iterators (I still haven't
    > wrapped my head around what those really are)


    Pointers are fine.

    > and somehow place them
    > in this pre-allocated memory space that I need to use? There isn't
    > enough memory for me to go allocating a bunch of memory for the
    > iterators.


    Iterators usually live on the stack. You need to know that STL may
    allocate some others. I expect your STL is adapted to your environment.

    --
    Michael
     
    Michael DOUBEZ, Apr 20, 2009
    #6
    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. sean
    Replies:
    1
    Views:
    622
    Cowboy \(Gregory A. Beamer\)
    Oct 20, 2003
  2. =?Utf-8?B?UnlhbiBTbWl0aA==?=

    Quick Question - Newby Question

    =?Utf-8?B?UnlhbiBTbWl0aA==?=, Feb 14, 2005, in forum: ASP .Net
    Replies:
    4
    Views:
    694
    Iain Norman
    Feb 16, 2005
  3. =?Utf-8?B?YW5kcmV3MDA3?=

    question row filter (more of sql query question)

    =?Utf-8?B?YW5kcmV3MDA3?=, Oct 5, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    971
    Scott Allen
    Oct 6, 2005
  4. Replies:
    7
    Views:
    546
    P.J. Plauger
    Nov 7, 2006
  5. Scott Meyers
    Replies:
    0
    Views:
    712
    Scott Meyers
    Mar 17, 2011
Loading...

Share This Page