title: indices of the k largest elements in an unsorted length n array
body: <p>I need to find the indices of the k largest elements of an unsorted, length n, array/vector in C++, with k &lt; n.  I have seen how to use nth_element() to find the k-th statistic, but I'm not sure if using this is the right choice for my problem as it seems like I would need to make k calls to nth_statistic, which I guess it would have complexity O(kn), which may be as good as it can get?  Or is there a way to do this just in O(n)?</p>
  
  <p>Implementing it without nth_element() seems like I will have to iterate over the whole array once, populating a list of indices of the largest elements at each step.</p>
  
  <p>Is there anything in the standard C++ library that makes this a one-liner or any clever way to implement this myself in just a couple lines?  In my particular case, k = 3, and n = 6, so efficiency isn't a huge concern, but it would be nice to find a clean and efficient way to do this for arbitrary k and n.</p>
  
  <p>It looks like <a href="https://stackoverflow.com/questions/1885591/mark-the-top-n-elements-of-an-unsorted-array">Mark the top N elements of an unsorted array</a> is probably the closest posting I can find on SO, the postings there are in Python and PHP.</p>