C++ retrieving an index value in a vector while using min_element or max_element

Question

I'm working on a problem here where I have two vector objects in my code: one is a vector<string>, and the other a vector<unsigned> that I'm passing as a const ref to some function. I'm using these functions to find the minimum or maximum value out of one vector, but I need the index value of the minimum or maximum so that I can index into the other vector. My code looks something like this:

std::string getTopEmployee( const std::vector<std::string>& names, const std::vector<unsigned>& ratings ) {
    // Find Largest Value in ratings
    std::size_t largest = *std::max_element( ratings.begin(), ratings.end() );
    // How to get the index?
    // I do not need the largest value itself.

    return names[index];
}

std::string getWorstEmployee( const std::vector<std::string>& names, const std::vector<unsigned>& ratings ) {

   // Find Smallest Value in ratings
   std::size_t smallest = *std::min_element( ratings.begin(), ratings.end() );
    // How to get the index?
    // I do not need the smallest value itself.

    return names[index];
}

The two vectors passed into this function are of the same size: and we are assuming that there are no two values in the ratings vector that are equal in value. Sorting the second vector is not an option.

Tamqrah

Hint: What values do std::min_element and std::max_element return? You're not using them, instead you're dereferencing them. – Weeds

@Weeds without dereferencing them they return a pointer or an iterator. – Tamqrah

OK, so do the math on that pointer and the start of the container. – Weeds

@Weeds that's were I'm a bit lost... shaking my head here; and it should be something simple too. – Tamqrah

Both Remy Lebeau & DAle posted excellent answers and they both answer the question. Not sure who to accept. Remy answered first with what library function to use, but DAle showed how to do it for both random access containers with O(1) constant and non random containers with O(n) linear time complexities. It's a tough call. – Tamqrah

@FrancisCugler Your call, but please accept one. – Scrutineer

Answer 1

std::min_element() and std::max_element() work with iterators, not indexes.

For an indexable container like std::vector, you can convert an iterator to an index using std::distance(), eg:

std::string getTopEmployee( const std::vector<std::string>& names, const std::vector<unsigned>& ratings ) {
    // Find Largest Value in ratings
    auto largest = std::max_element( ratings.begin(), ratings.end() );
    if (largest == ratings.end()) return "";
    return names[std::distance(ratings.begin(), largest)];
}

std::string getWorstEmployee( const std::vector<std::string>& names, const std::vector<unsigned>& ratings ) {
    // Find Smallest Value in ratings
    auto smallest = std::min_element( ratings.begin(), ratings.end() );
    if (smallest == ratings.end()) return "";
    return names[std::distance(ratings.begin(), smallest)];
}

Activator

I tried using this and the code seems to work for the first function in finding the value of the largest and it is returning the correct string. However, for some reason the second function it is return an empty string and I don't know why. I'm using the same two vectors being passed to these two function consecutively. – Tamqrah

Okay I found my problem. Some where else the sizes of my vectors were resized with X amount of elements before being populated and there were only Y valid elements to work on where Y < X. I had to add an extra variable in another part of code to get a count of total valid objects and then resize the vectors before using them in these functions. Now I'm getting the appropriate strings. – Tamqrah

Thank you guys for the help. I knew it was something simple, but was having coders block... – Tamqrah

Answer 2

For std::vector or any other container with random-access iterators you can use arithmetic operators (let's assume for simplicity that containers are not empty):

 auto maxi = std::max_element(ratings.begin(), ratings.end());
 return names[maxi - ratings.begin()];

Complexity: O(1).

For containers with iterators that are at least input iterators, you can use std::distance:

 auto maxi = std::max_element(ratings.begin(), ratings.end());
 return names[std::distance(ratings.begin(), maxi)];

Complexity: O(1) with random-access iterators, O(n) with not random-access.

Weissmann

Thank you for the help; Remy was a little bit ahead of you. I know the difference between random access and iterative containers and their time complexities. I was just wrapping my head around something simple... I was just having a case of coders block... – Tamqrah

Just make sure the containers are not empty, or at least handle the case where the algorithms return the end iterator, otherwise you end accessing a non-existant index 0. – Activator

@RemyLebeau, you are right, thanks. I'll add a comment about empty containers. – Weissmann

I had to accept Remy's answer for he was first to answer that pointed me in the right direction of solving my problem. Your answer also provides excellent insight for others who may read this about the time complexity of the different containers. – Tamqrah