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

Question

我需要在地图中实现类似“第一键旋转”的东西。更详细的解释问题。有一个图：

​​

以下元素被插入：

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

旋转算法可以被重写为：

一个]请注意，在图（第一元件具有最低键元件）：rem_el =地图[0] //符号表示法

b]，从地图移除第一元件

C]设置在地图中所有剩余的元素新的密钥：

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

d]添加想起键用新键映射：最后的关键之和记忆的关键

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; 

这样的地图有n-1个旋转...

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

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

Answer 1

看起来你需要对一个deque，而不是一个地图：

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

Answer 2

旋转的价值观和保持键

一种可能性是使用deque由@Eugene提及。然后，当然，你没有快速的O（log n）访问键。如果你想保持的地图，则以下是可能的“旋转”地图m通过n轮：

void rotate(map<double, double>& m, int n) { 
    vector<double> values(m.size()); 
    int j = 0; 
    for (map<double, double>::const_iterator i = m.begin(); i != m.end(); ++i, ++j) { 
     values[j] = (*i).second; 
    } 
    j = n; 
    for (map<double, double>::iterator i = m.begin(); i != m.end(); ++i, ++j) { 
     m[(*i).first] = values[j % m.size()]; 
    } 
} 

如果要通过各种数轮的转动几次，那么你可以进行矢量values全球并只填写一次。此外，应该考虑旋转n1，然后n2等于旋转n1 + n2。所以，例如获得所有转动，你会打电话：

rotate(m, 1); 
rotate(m, 1); // 1 again 
... 

只是一句话：它是相当有问题的使用兼作键。

旋转值，以及更改键（编辑）

在这种情况下一个完全新的地图需要被构造为@abcdef已经这样做。但是，似乎新问题在问题中没有正确定义。将密钥k1，k2，...，kn变换为k2-k1，k3-k1，...，kn-k1，kn。例如，我们获得重复密钥。当将（-1,2,5,6）变换为（3,6,7,6）时，k [n-1] -k1 = kn。

Answer 3

我认为std :: map是基于树结构的，它的元素有升序。所描述的旋转操作不会改变相关的键位置。所以关键更改不应该制动地图结构。我创建了旋转函数来修改关键值。这似乎是不好的做法，仍然可以在msvs和gcc上使用it。

typedef std::map<double,double> Map; 
typedef Map::iterator MapIter; 

void rotate(Map &m) { 
    if (m.empty()) return; 
    MapIter prev, iter = m.begin(), max_iter = m.end(); 
    Map::key_type rem_key = iter->first; 
    Map::mapped_type rem_val = iter->second; 
    for(prev = iter++; iter != max_iter; prev = iter++) { 
     Map::key_type *key = const_cast<Map::key_type*>(&prev->first); 
     *key = iter->first - rem_key; 
     prev->second = iter->second; 
    } 
    prev->second = rem_val; 
} 

编辑：描述旋转操作不只是在情况下，所有键都是非负的改变相关的密钥位置。在其他情况下，我的算法不正确地修改地图结构，从而无法使用。

Answer 4

我阅读了你的评论，但我仍然想提供一个答案，并显示如何使用原始地图可以完成。所以，这里是代码：

#include <map> 
#include <iostream> 
#include <utility> 

int main() { 
    std::map <double, double> test; 

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

    std::pair<double, double> first = *test.begin(); 
    test.erase(test.begin()); 
    std::map<double, double>::iterator i = test.begin(); 
    while (i != test.end()) { 
     test[i->first - first.first] = i->second; 
     std::map <double, double>::iterator prev = i; 
     ++i; 
     test.erase(prev); 
    } 
    test[test.rbegin()->first + first.first] = first.second; 

    for (i = test.begin(); i != test.end(); ++i) { 
     std::cout << "test[" << i->first << "] = " << i->second << "\n"; 
    } 
} 

的几个注意事项：

• std::map键不能修改，所以你必须删除旧的元素并插入新的;
• 问题陈述保证新插入的元素不会覆盖现有的元素;
• 从映射中删除元素不会使不指向已删除元素的迭代器失效。

Answer 5

我注意到，只要没有通过任何其他方式添加或移除键，就有可能跟踪旋转期间的键改变。

首先，请注意地图中最大的按键从不改变。

现在注意到，除了从地图的一个极端“绕回”到另一个极端的关键值之外，您可以通过跟踪所减去的键的总值来总结旋转的影响。

看看最小的键发生了什么 - 你可以想象它会被自身减去，产生一个零值。但是现在我们决定0的值太小而无法忍受，就像模块化算术一样，我们可以给它添加一个模数以使其回到范围内。该值是地图中（不变）最大的键。因此，预测密钥转发的规则是减去到目前为止处理的所有最小密钥的总和，然后根据需要添加最大密钥值，以将该值带入范围。类似地，向后推导键的规则将是减去到目前为止所处理的所有最小键的总和，然后根据需要添加最大键值以使该值进入范围。你可以允许用户旋转地图并以O（1）代价查找关键值，只需要处理O（n log n） - （或者可能O（n）），取决于你想要做的是多么棘手和小心）在添加或删除键值时重写地图的工作。

我认为通过顺序指数（例如第一个值，第二个值，第三个值）查找值是相同的原则 - 跟踪一个值以添加或减去迄今总旋转的帐户，并添加或减去地图中的项目总数，以使事情回到范围内。

Answer 6

这是一个有趣的问题，但更多的算法比数据结构。

我注意到，Map^i[n]可以在固定的时间来解决......如果不是修改结构，你调整访问。

从我的问题，值简称为 “周期” 的理解：[15, 20, 12, 18] - >​​- >[12, 18, 15, 20] - >[18, 15, 20, 12]

公式：

• 令N是所述序列的大小 - 1和n [0, N]的序列中的索引
• 设I在[0, N]是迭代
• Value^i[n] = Value[n+i%(N+1)]

的关键是，虽然不同：

• [0.5, 1, 2.3, 3.7] - >[0.5, 1.8, 3.2, 3.7] - >[1.3, 2.7, 3.2, 3.7] - >[1.4, 1.9, 2.4, 3.7]
• 让我们试着看到一个模式：[a, b, c, d] - >[b-a, c-a, d-a, d] - >[c-b, d-b, d-b+a, d] - >[d-c, d-c+a, d-c+b, d]

使图案更加明显：

0: [a , b  , c  , d  , e  , f] 
1: [b-a , c-a , d-a , e-a , f-a , f] 
2: [c-b , d-b , e-b , f-b , f-(a-b), f] 
3: [d-c , e-c , f-c , f-(a-c), f-(b-c), f] 
4: [e-d , f-d , f-(a-d), f-(b-d), f-(b-e), f] 
5: [f-e , f-(a-e), f-(b-e), f-(c-e), f-(d-e), f] 

请注意，这也是循环，因为再次应用转换会产生原始序列。

式（我们重新使用以前的变量）：

Key^i[n] = | n = N => Key[N] 
      | i = 0 => Key[n] 
      | n <= N-i => Key[n+i] - Key[i-1] 
      | n > N-i => Key[N] - (Key[n+i % (N+1)] - Key[i-1]) 

后者3线可以在(Key[n+i % (N+1)] - Key[i-1]) % Key[N]被聚集，如果我们定义（任意地）Key[-1] = 0。

现在我们有了我们的公式，我们需要一个随机访问的结构，我会简单地选择一个vector。下面提供

可编译示例（或见ideone），得到：

[ 0.5: 15, 1: 20, 2.3: 12, 3.7: 18 ] 
[ 0.5: 20, 1.8: 12, 3.2: 18, 3.7: 15 ] 
[ 1.3: 12, 2.7: 18, 3.2: 15, 3.7: 20 ] 
[ 1.4: 18, 1.9: 15, 2.4: 20, 3.7: 12 ] 

实施例：

#include <cassert> 
#include <algorithm> 
#include <iostream> 
#include <vector> 

typedef std::pair<double, double> Pair; 
typedef std::vector<Pair> Vector; 

double key(Vector const& vec, size_t const i, size_t const n) { 
    assert(n < vec.size() && "Wrong index"); 
    if (i == 0) { return vec[n].first; } 

    size_t const N = vec.size() - 1; 

    if (n == N) { return vec.back().first; } 

    double const partial = vec[(n+i) % (N+1)].first - vec[(i-1) % (N+1)].first; 
    return (n <= N-i) ? partial : partial + vec[N].first; 
} // key 

double value(Vector const& vec, size_t const i, size_t const n) { 
    assert(n < vec.size() && "Wrong index"); 
    return vec[(n+i) % vec.size()].second;  
} // value 

int main() { 
    Vector vec{ Pair(0.5, 15), Pair(1, 20), Pair(2.3, 12), Pair(3.7, 18) }; 
    sort(vec.begin(), vec.end()); // just to be sure 

    size_t const size = vec.size(); 
    for (size_t i = 0; i != size; ++i) { 
    std::cout << "[ "; 
    for (size_t n = 0; n != size; ++n) { 
     if (n != 0) { std::cout << ", "; } 
     std::cout << key(vec, i, n) << ": " << value(vec, i, n); 
    } 
    std::cout << " ]\n"; 
    } 
} 

Answer 7

这里是另一个想法。

使用两个数据结构而不是一个。将值保存在list<double>中，并将您的地图表示为map<double, list<double>::iterator>。

也就是说，从double键映射到迭代器（即指针）到值列表中。

还记录您已完成的旋转次数总数;称它为k。要执行查找，请在地图中查找关键字，将k添加到迭代器中，并对其进行取消引用。 （是的，这是O（k）。）另外，为了这个工作，你需要一个循环链表;或者更容易，通过处理环绕的列表实现自己的行军。

请注意，一般情况下，您不要旋转列表本身;你只需增加k。所有的费用都是在查找过程中发生的。

请注意，插入仍然为O(log n)，因为在列表中插入不会使其迭代器失效，并且您可以从地图中获取插入到O(log n)时间的列表中的位置。

现在这里是原来的位。当k达到sqrt(n),然后您实际上旋转列表以将k重置为零。此操作为O(n)，但您只需每O(sqrt(n))次旋转执行一次......含义分期付款（即平均）旋转操作的成本也为O(sqrt(n))。并且k永远不会大于sqrt(n)，因此查找也是O(sqrt(n))。

因此，该制剂提供：

插入：O（log n）的 删除：O（log n）的 查找：O（SQRT（n））的 旋转：O（SQRT（n））的

，你可能会或可能不会考虑比其他更好的建议，但至少它的与众不同......

而且这个配方，你可以权衡的转速查找。例如，如果在k达到log n时执行“重置”操作，则平均旋转次数将为O(n/log n)，但查找仍然为O(log n)。 （这里的大多数其他建议要么转走O(n)或插入服用O(n)，所以这个版本的跳动......虽然只有数n倍）。

Answer 8

你可以为O旋转（日志N）

#include<map> 

using namespace std; 

map<double, double> m; 
double diff; //the keys in m are actually diff bigger then in needed map 

void rotate() 
{ 
    double savedValue = m.begin()->second; 
    double removedKey = m.begin()->first - diff;//save the value of first element 
    m.erase(m.begin()); //erase first element 
    diff += removedKey; //do the (key -=) thing 
    m[m.rbegin()->second + removedKey] = savedValue;//add new value 
} 

//dont need to do this, just remember that key = storedKey - diff 
map<double, double> getMap() 
{ 
     map<double, double> res; 
     for(map<double, double>::iterator it = m.begin(); it != m.end(); ++it) 
       m[it->first-diff] = it->second; 
     return res; 
} 

Answer 9

如果旋转后只需要有效地执行查找，那么你应该去Matthieu的解决方案。 在他出色的答案，他只是忘记了，而不是Key^i[n]需要后i旋转给出的关键k一些价值k又会有怎样的等级（指数）n转i的许多功能即逆（如果这样的键是否存在）。

我不认为在分析术语中可以找到反函数，并且在O（1）中以Key^i[n]的方式计算，但是您可以使用二分搜索在O（log n）时间内进行有效查找。

double get(Vector const& vec, size_t const i, double key) { 
    assert(n < vec.size() && "Wrong index"); 
    size_t rank = binarySearch(vec, i, 0, vec.size()-1, key); 
    if (rank < 0) { 
     // not found, return NaN or something 
    } 
    return vec[rank].second;  
} 

size_t binarySearch(Vector const& vec, size_t const i, size_t const low, size_t const high, double value) { 
    if (high < low) 
     return -1; // not found 
    mid = low + (high - low)/2; 
    if (key(vec, i, mid) > value) 
     return binarySearch(vec, i, low, mid-1, value); 
    else if (key(vec, i, mid) < value) 
     return binarySearch(vec, i, mid+1, high, value); 
    else 
     return mid; // found 
} 

该解决方案为您提供了O（1），旋转（你只需要增加旋转计数器和记住它）和O（log n）的查找。 如果你想修改地图（就像插入一个新的元素），你必须使用getMap（）函数重置整个地图，这需要O（n）个时间。

因此，如果您需要在旋转后有效地进行查找和插入（删除等），那么您应该坚持kilotaras的解决方案，它可以为所有操作提供统一的O（log n）时间，包括旋转，查找和修改。