今天在写跨服匹配的时候遇到一个问题，大概可以描述成这样:
有10个队列，1到10编号
取操作：每次从这些队列中取N个数，取的方式是按1-2-3……-10-1-2的顺序循环。若队列被取空，则跳过继续，要满足取够N个。取出的数从队列中移除。
取操作可能会连续执行，需要保证后一次操作接在上一次操作后的位置继续取元素。
在一次取操作后，可能会向某些队列中添加新元素。
朴素的做法是循环计数遍历，直到找到下一个非空队列为止。
由于空队列是没有价值的，最坏情况是所有元素全在一个队列中，这样每取一个元素要遍历10次。这是我不想见到的。
另一种思路是，如果用一个map容器维护这10个队列，当队列取空就从map中移除，被添加新元素则再加回队列(这里必须用map的原因是添加元素时要指定对应队列，若用list每次添加都需要遍历来确定位置)。这里需要处理当队列被删除和加入容器时，下一次取元素的起始位置的维护。想了一下，细节多很，不是几行代码能搞定的。并且取元素的起始位置和队列容器本身其实并没有关键，凭空增加了代码耦合。除此之外还有不断插删队列map的消耗。
为了改进这种做法，可以构造一个全局迭代器，它不断反回下一个元素所在的队列的下标。其内部维护一个关于下标的环形链表。在遍历时，若发现当前队列为空，则将该下标从链表中删除。而往回加的操作要复杂一些，这也是一开始最困扰我的地方。
假设剩余链表为1-5-6……需要把3加回去，需要找到比3小的最大的元素(以及比3大的最小的元素，这两个数现在一定是相邻的)。于是我们需要额外维护一个set来存放当前剩余的下标，用来来找到这两个数。然后再将3加回入链表。
其实只是一个常数为10的优化。。感觉意义不大_(:ᗤ」ㄥ)_
网友评论