CODEWITHSUNDEEP
c++arraysalgorithmstl
user441521
user441521

Reputation: 6998

Get the lowest list count in array

I have an array of lists (array<list<Client*>, 10>) and I want to see which list has the lowest item count in it so I can add to that. I'm doing a small balancing system here and as clients come in I want to add them to 1 or the 10 lists which has the lowest number of other clients to keep the lists level.

Would I have to do a bubble sort here or is there some sweet stl way to handle something like this?

Upvotes: 2

Views: 103

Answers (4)

Jerry Coffin
Jerry Coffin

Reputation: 490663

If all the clients are serviced (removed from the lists) at the same rate, then round-robin scheduling is the obvious answer.

If, however, there's variability (e.g., you're simulating customers who take different lengths of time) you probably want something like a priority queue of collections, using the length of each collection as the priority. This will place the current highest priority item (shortest list) in a known location (usually the first item in the queue). After you insert a new item, you (potentially ) "sift" that down the heap to maintain the heap property.

This allows you to insert or remove an item with O(log N) complexity, where something like std::min_element would require O(N) complexity.

As an aside: if you care about speed, chances are pretty good that list isn't a great choice either. A list has individually allocated nodes, and each node contains two pointers. These factors tend to lead to poor locality of reference, which generally implies poor cache usage. A priority_queue of vectors instead (for only one possibility) will often work better.

Upvotes: 1

AndyG
AndyG

Reputation: 41220

If you actually need it sorted such that the list with the lowest item count appears first (and not std::min_element to simply get the lowest item like Barry suggested), then you could use std::partial_sort, e.g.:

std::array<int,10> myArray{10,9,8,7,6,5,4,3,2,1};
std::partial_sort(myArray.begin(),myArray.begin()+1,myArray.end(), 
   [](const int& lhs, const int& rhs){return lhs < rhs;});

Where the last parameter here is a lambda for comparison. You'd replace it with something like 

[](const list<Client*>& lhs, const list<Client*>& rhs){return lhs.size() < rhs.size();)

Live Demo

Upvotes: 1

Diniden
Diniden

Reputation: 1125

If the lists start at zero elements when you start adding to them and you want to keep them perfectly balanced, consider just adding to the lists round robin style:

Pseudo Code:

index = 0
list to add to = lists[index % list length]
index++

Upvotes: 5

Barry
Barry

Reputation: 303890

That's precisely what std::min_element is for:

std::array<std::list<Client*>, 10> arr;

auto it = std::min_element(arr.begin(), arr.end(), 
          [](const std::list<Client*>& a, const std::list<Client*>& b){
              return a.size() < b.size();
          });

That'll give you an iterator into which list has the fewest elements.

Upvotes: 5

Related Questions