我有一张 map (xi,f(xi)) 并且我的 f(xi) 也在严格增加。我需要这样交换 key 和值
我的函数的输入:
一张 map
//keys : x0, x1, x2, ..., xn
// vals : f(x_0) f(x1), f(x2), ..., f(xn)
我的函数输出: 一张 map
// key : left_val f(x_0) f(x1), ..., f(xn-1)
// vals : x0, x1, x2, ..., xn
(这里left_val是输入参数,我知道它低于f(x0))。 我知道我可能没有使用正确的结构,但我确实需要 log(n) 插入和有序键的唯一性......
您将如何有效地实现(即不复制 map )?
提前致谢。
最佳答案
这是一种不寻常的情况,因为您想要更改 std::map
键,这通常是被禁止的,以避免会破坏顺序的更改。如果你有信心自己确保这个不变性,那么你可以修改 std::map
如下:
#include <iostream>
#include <map>
int main()
{
typedef std::map<double, double> Mdd;
Mdd m;
m[1] = 4;
m[2] = 6.5;
m[3] = 7.2;
m[4] = 9.3;
m[5] = 12;
double x = 2.3;
for (Mdd::iterator i = m.begin(); i != m.end(); ++i)
{
double old_second = i->second;
i->second = i->first;
const_cast<double&>(i->first) = x;
x = old_second;
}
for (Mdd::const_iterator i = m.begin(); i != m.end(); ++i)
std::cout << i->first << "->" << i->second << '\n';
}
输出:
2.3->1
4->2
6.5->3
7.2->4
9.3->5
所有这一切都是使用 const_cast
来坚持对 key 的写访问。严格来说,我怀疑标准不会要求在这样的 hacker 之后实现工作,但实际上我无法想象一个不需要的实现。你需要决定你想用 x
的最终值做什么 - 在你的问题中是 f(xn)
......我已经放弃了它正如您的问题所建议的那样。
就效率而言,这会在 map
上进行一次按顺序传递,如果希望使用这样的容器,这是不可避免的。没有 map 的复制或额外的堆分配。转换后,根据上面关于标准不保证支持的警告,您可以期望有一个“正常”有效映射,可以在其中安全地插入和删除元素。
关于c++ - 在 map 中交换键和值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16412625/