C++ std::map，键的旋转

Question

我需要在 map 中实现类似“第一键轮换”的功能。对问题的更详细的解释。有一张 map :

std::map <double, double> test;

插入了以下元素:

test[0.5] = 15;
test[1] = 20;
test[2.3] = 12;
test[3.7] = 18

旋转算法可以重写为:

a] 记住map中的第一个元素(key最低的元素):rem_el = map[0]//记法

b] 从 map 中删除第一个元素

c] 为 map 中所有剩余元素设置新键:

map[i].key = map[i].key - rem_el.key

d] 使用新键将记住的键添加到 map :最后一个键和记住的键的总和

test[rem_el.key + test[n-1].key] = rem_el.value

第一次轮换:

test[0.5] = 20;
test[1.8] = 12;
test[3.2] = 18;
test[3.7] = 15;

第二次轮换:

test[1.3] = 12;
test[2.7] = 18;
test[3.2] = 15;
test[3.7] = 20;

这样的 map 有n-1个旋转...

如何尽可能高效地实现此操作(包含数千个项目的 map )？我使用了所有键的列表和从旋转列表创建的另一个临时映射，但这个过程可能不是最佳的。

我可以要求一些代码示例吗？谢谢。

Answer 1

看起来你需要一对双端队列，而不是 map :

std::deque<std::pair<double, double> > test;

如果需要，您必须自己对它进行分类。然后一切都简单明了:

std::pair<double, double> rem_el = test.front();
test.pop_front();
for (std::deque<std::pair<double, double> >::
     iterator it = test.begin(); it != test.end(); ++it)
{
    it->first -= rem_el.first;
}
assert(!test.empty());
test.push_back(std::make_pair(rem_el.first + test.back().first, rem_el.second));