nth_element question

[bsabiston]

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

 

[Victor Bazarov]

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

 

[bsabiston]

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

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

 

[Pavel]

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

 

[bsabiston]

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

 

[Michael DOUBEZ]

(e-mail address removed) 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

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.