A question regarding stl nth_element
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 9 of 9

Thread: A question regarding stl nth_element

Hybrid View

  1. #1
    Join Date
    Jul 2005
    Posts
    910

    A question regarding stl nth_element

    Here is the code,
    Code:
    	vector<int> vec;
    
    	for(int i=0;i<10;++i)
    		vec.push_back(i);
    
    	random_shuffle(vec.begin(), vec.end());
    
    	nth_element(vec.begin(), vec.begin()+7, vec.end());
    No matter how I choose the second argument passed to nth_element, the elements in vec are always sorted as,
    0,1,2,3,4,5,6,7,8,9
    What is the use of second argument here?Thanks.

  2. #2
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,088

    Re: A question regarding stl nth_element

    Did you read the documentation? What are you expecting it to do differently?

  3. #3
    Join Date
    Apr 1999
    Posts
    27,427

    Re: A question regarding stl nth_element

    Quote Originally Posted by LarryChen View Post
    No matter how I choose the second argument passed to nth_element, the elements in vec are always sorted as,
    0,1,2,3,4,5,6,7,8,9
    What is the use of second argument here?Thanks.
    http://www.cplusplus.com/reference/a...m/nth_element/

    Regards,

    Paul McKenzie

  4. #4
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,565

    Re: A question regarding stl nth_element

    Try using a larger number than 10. Looking at the code in Visual C++ 2010, it looks
    like if the number of elements is less than or equal to 32, it just does an insertion
    sort. So try adding 100 elements.

  5. #5
    Join Date
    Jul 2005
    Posts
    910

    Re: A question regarding stl nth_element

    Quote Originally Posted by Philip Nicoletti View Post
    Try using a larger number than 10. Looking at the code in Visual C++ 2010, it looks
    like if the number of elements is less than or equal to 32, it just does an insertion
    sort. So try adding 100 elements.
    I tried adding 100 elements this time, here is the code and results.
    Code:
    	vector<int> vec;
    
    	for(int i=0;i<100;++i)
    		vec.push_back(i);
    
    	random_shuffle(vec.begin(), vec.end());
    
    	nth_element(vec.begin(), vec.begin()+3, vec.end());
    I tried n=3 and n=7. but the results are exactly the same,
    vec[100](0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,24,28,21,42,29,41,40,30,32,33,31,23,37,27,35,38,39,25,26,36,20,34,19,22,43,98,96,58,82,86,90,62,59,97,55,78,68,50,61,46,44,83,56,87,60,84,95,57,54,81,77,70,89,99,79,73,76,65,66,88,64,47,52,72,53,67,94,85,75,74,69,45,91,93,51,48,80,71,63,49,92)
    It looks like before 18, the numbers are sorted. What does it mean? Thanks.

  6. #6
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,088

    Re: A question regarding stl nth_element

    There's nothing wrong with those results. It's doing what it's documented to do. What's the issue?

  7. #7
    Join Date
    Jul 2005
    Posts
    910

    Re: A question regarding stl nth_element

    Quote Originally Posted by GCDEF View Post
    There's nothing wrong with those results. It's doing what it's documented to do. What's the issue?
    The issue is that since no matter what is passed to the second parameter of nth_element, the result is always the same, why would we need the second parameter?Thanks.

  8. #8
    GCDEF is offline Elite Member Power Poster
    Join Date
    Nov 2003
    Posts
    12,088

    Re: A question regarding stl nth_element

    It takes all values in the container and rearranges the container so that all values less than the nth element will occur before it in the result, and all values greater will occur after. That's all it says about the sort order. So, if your vector contains

    1,3,9,8,2,6,0,4,5 and you use 7 for your second argument, which in this case is the value 4, all values less than 4 will be placed first in the vector, followed by 4, followed by all values greater than 4. Other than that, the sort order isn't specified. So it may look like

    1,3,2,0,4,5,6,9,8 or 0,3,2,1,4,8,6,9,5 or any other combination such that all values before the nth element are <= the nth element and all values after it are >=.
    Last edited by GCDEF; June 19th, 2013 at 12:15 PM.

  9. #9
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,565

    Re: A question regarding stl nth_element

    The issue is that since no matter what is passed to the second parameter of nth_element, the result is always the same, why would we need the second parameter?Thanks.
    How many values of n did you try ? What happens if you use 40 ?

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center