Finding min value out of certain group in list repeatably, faster to sort first?

[sonar87]

If I have if a list of say <string, int> pairs, and wanting to go through and take out one pair at a time, removing which ever has the lowest int, but only the lowest out of ones that have one of a certain group of strings (more strings added as it goes so eventually all items will be removed from the list), then would it be faster to just least the list as it is? Going through the whole list checking each one each time to find which should be removed, or to take the time to use some sorting algorithm to sort the list by int values so the lowest are at the start, so that each time is just goes through until it finds the first case of a string that matches and allows removal? If the second way, sorting first, what sorting algorithm would be a good choice for this?

[Duthomhas]

Er, it depends. What exactly are you trying to accomplish with this?

[sonar87]

I was using the list of to represent graph edges and traversal costs. So pick the lowest cost edge that in among those you have access to, process it, take it out of the list so it's not reprocessed. So I thought maybe sort the list so all the lowest cost ones are first and then just have to keep going through the beginning of that list till you find the lowest that is allowed to be taken.

[Duthomhas]

Ah, yes, you could. I would use a priority queue. But any object which orders the edges will do (such as a set or map), just write your comparison function to sort on string,int order.

[jonnin]

sort it, but only once. Then you should be able to iterate it once, at each node you can take it or not, move to next.

Unless I am missing something, do you need to re-iterate for something?

[JLBorges]

Something like this, perhaps:

#include <string>
#include <unordered_map>
#include <queue>

// priority queue of int (costs)
// with the smallest int (lowest cost) having the highest priority
using pq_of_costs = std::priority_queue< int, std::vector<int>, std::greater<> > ;

// hashtable key: string (vertex) associated data: priority queue of int (costs)
using vertex_edge_costs_map = std::unordered_map< std::string, pq_of_costs > ;

// with N == number of strings in the graph (number of vertices)
//      M == number of edges associated with a vertex (integer values represent the cost)

// add string (vertex), int (edge) pair to map. average complexity: O( log M )
void insert( vertex_edge_costs_map& map, const std::string& str, int v ) { map[str].push(v) ; }

// remove lowest int (lowest cost edge) associated with str (this vertex).
// average complexity: O( log M )
bool remove_lowest_cost_edge( vertex_edge_costs_map& map, const std::string& str )
{
    const auto iter = map.find(str) ; // look up vertex: average O(1)

    if( iter != map.end() ) // found str (vertex)
    {
        iter->second.pop() ; // remove smallest cost edge O( log M )

        // remove the string (vertex) if the last edge associated with it is removed
        if( iter->second.empty() ) map.erase(iter) ; // average O(1)

        return true ;
    }

    return false ; // vertex (str) was not found
}

[sonar87]

Cool. Thanks, everyone!