获取数组中最小的列表数

Question

我有一个列表数组 (array<list<Client*>, 10>)，我想看看哪个列表中的项目数最少，以便我可以添加到其中。我在这里做一个小型平衡系统，当客户进来时，我想将它们添加到其他客户数量最少的 1 个或 10 个列表中，以保持列表水平。

我是否必须在这里进行冒泡排序，或者是否有一些甜蜜的 stl 方法来处理这样的事情？

Answer 1

这正是 std::min_element 的用途：

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();
          });

这将为您提供一个迭代器，其中 list 的元素最少。

Answer 2

如果当您开始添加列表时列表从零元素开始并且您希望它们保持完美平衡，请考虑只添加到列表循环法样式：

伪代码：

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

Answer 3

如果您确实需要排序，使项目数最少的列表首先出现（而不是 std::min_element 来简单地获得最低的项目，例如 ), then you could use std::partial_sort，例如：

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;});

这里的最后一个参数是用于比较的lambda。您可以将其替换为

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

Live Demo

Answer 4

如果以相同的速率为所有客户端提供服务（从列表中删除），那么循环调度就是显而易见的答案。

但是，如果存在可变性（例如，您正在模拟花费不同时间长度的客户），您可能需要类似集合优先级队列的东西，使用每个集合的长度作为优先级。这会将当前优先级最高的项目（最短列表）放在已知位置（通常是队列中的第一项）。插入新项目后，您（可能）"sift" 向下维护堆属性.

这允许您插入或删除具有 O(log N) 复杂度的项目，其中 std::min_element 之类的东西需要 O(N) 复杂度。

顺便说一句：如果您关心速度，那么 list 很可能也不是一个好的选择。列表具有单独分配的节点，每个节点包含两个指针。这些因素往往会导致引用的局部性差，这通常意味着缓存使用率差。 priority_queue 个矢量（只有一种可能性）通常会更好。

获取数组中最小的列表数

Get the lowest list count in array

c++

arrays

algorithm

stl