Index of minimum element in a std::list

Question

If I have a std::vector<int>, I can obtain the index of the minimum element by subtracting two iterators:

int min_index = std::min_element(vec.begin(), vec.end()) - vec.begin();

However, with containers that don't have random access iterators, for example a std::list<int>, this doesn't work. Sure, it is possible to do something like

int min_index = std::difference(l.begin(), std::min_element(l.begin(), l.end()));

but then I have to iterate twice through the list.

Can I get the index of the element with the minimum value with STL algorithms by only iterating once through the list or do I have to code my own for-loop?

Sepulture

Why do you need the index of an element in a std::list? – Emasculate

You could write an iterator that wraps list::iterator and keeps track of its index as it goes. It would have limited use, since inserting/removing elements from the container would invalidate the indexes stored in your iterators, but you could use min_element and other algorithms on it, then grab the index out of the return value. – Rizzo

You could use std::set or sort your container and always know where the minimum element is ... – Beckford

If you want to do this, a list is probably the wrong data structure for the job. – Houdini

I need a list because (a) the order is important (so i can't use a set) and (b) the iterators need to be valid after inserting an element. Indexes are only rarely needed for the user. – Sepulture

In you want to iterate only once, that is you want O(n), complexity, a for loop will do also O(n), for a static list, i.e. no elements are added. If you do add elements, then the index might change, and you will have find the index again by performing O(n) comparisons. If you would use std::vector instead the index would be preserved upon insertion and you would only have to perform O(1) comparisons every time instead of O(n). I don't think that you can do it with std::list if elements can be added /removed to the list . – Stumer

@Niklas B. : Maybe he has his reasons... i.e. that is the container he has to work upon. – Stumer

@g24l: I agree, but I don't think that this could be solved in one line without writing additional code, so maybe switching the data structure is a better idea. – Emasculate

If the indexes are only rarely needed, why are you concerned about the difference between a O(2n) loop and a O(n) loop for finding them? Your std::distance example, while theoretically slower than a single pass for-loop, is pretty much guaranteed to be correct on the first try. – Maddening

@NiklasB. : well I don't disagree, if he can change the container, then I would advise him to do so. However, if for some reason, the std::list is the output of some blackbox process, which he may not modify, then we this is a problem to consider. – Stumer

I have to say though, that there is no sense in getting the index for any practical reason I can think of. Finding the minimum value, that would be of interest. – Stumer

Answer 1

You'll have to write your own function, for example:

template <class ForwardIterator>
  std::size_t min_element_index ( ForwardIterator first, ForwardIterator last )
{
  ForwardIterator lowest = first;
  std::size_t index = 0;
  std::size_t i = 0;
  if (first==last) return index;
  while (++first!=last) {
    ++i;
    if (*first<*lowest) {
      lowest=first;
      index = i;
    }
  }
  return index;
}

Prawn