使用一个考虑到std::map中键值的滚动或换行的键

Question

是否可以为std::map设置一个考虑到密钥翻转或换行的密钥？如果是，您将如何实现<操作员要这样做？

假设密钥基于具有最大值N的计数器，是否可能具有<当键值滚动时考虑的运算符，以便在映射中按如下顺序排列项目：

N-2
N-1
N
1
2
3
...

此外，如果键值可以跳过，是否可以这样做？例如，跳过N，使映射具有以下值：

N-2
N-1
1
2
3
...

Answer 1

是。

将<用于std::tuple和bool，可以执行类似的操作

#include <iostream>
#include <string>
#include <map>
#include <functional>
template <typename T>
struct WrappedLess
{
T wrap_point;
bool operator()(const T & lhs, const T & rhs) const
{
return std::make_tuple(lhs < wrap_point, std::ref(lhs)) < std::make_tuple(rhs < wrap_point, std::ref(rhs));
}
};
constexpr int N = 100;
int main() 
{
std::map<int, std::string, WrappedLess<int>> wrapped_values({N-2}); // initally empty
std::map<int, std::string, WrappedLess<int>> more_wrapped_values({
{N-10, "last"}, 
{N-2, "first"}, 
{N-1, "second"}, 
{1, "third"}, 
{5, "fourth"}, 
}, {N-2}); // initialised with some values
for (auto & pair : more_wrapped_values)
std::cout << pair.first << pair.second << std::endl;
}

在coliru 上实时观看

Answer 2

下面是一个如何实现的示例。其思想是引入一个自定义的Key模板，该模板可以在编译时用所需的最大值进行参数化。通过boost运算符库提供比较和基本算术运算，从而可以比较和添加具有相同最大值的Key实例。

#include <boost/operators.hpp>
template <int max>
struct Key : private boost::totally_ordered<Key<max>, boost::addable<Key<max>>> {
int value;
Key(int init = 0) : value(init) { maybeRollOver(); }
Key& operator+=(const Key& rhs) { value += rhs.value; maybeRollOver(); return *this; }
const Key& operator+() const { return *this; }
void maybeRollOver() { if (value > max) value = value % max - 1; }
};

此模板需要两个运算符重载来生成所有比较运算符(请参阅boost文档(：

template <int max>
bool operator==(const Key<max>& lhs, const Key<max>& rhs)
{
return lhs.value == rhs.value;
}
template <int max>
bool operator<(const Key<max>& lhs, const Key<max>& rhs)
{
return lhs.value < rhs.value;
}

以下是如何使用它。

std::map<Key<5>, std::string> testMap;
testMap[0] = "Hello";
testMap[1] = "world";
testMap[6] = "Bye"; // "rolled over to 0, "Hello" is replaced by "Bye";
for (const auto& [key, value] : testMap)
std::cout << key.value << ": " << value << "n";

Answer 3

这是我能够开始工作的解决方案。

密钥实际上是<unsigned int, unsigned int>，相对于滚动的排序只需要考虑密钥的第一个值。此外，ID基于1，因此值将为1, 2, ..., N, 1, 2, ...最后，请注意，MAX ID足够大，这样我们就不会有多个相同的密钥试图同时存在于地图中。也就是说，当我们到达id N时，最初的1、2、3…键早已不见了。

class Mykey(
public:
unsigned int Id1;
unsigned int Id2;
MyKey(unsigned int k1, unsigned in k2)
: Id1(k1), Id2(k2) {}
bool operator<(const MyKey &rhs) const
{
if (Id1 == rhs.Id1)
return Id2 < rhs.Id2;
else if ( (rhs.Id1 > Id1) && (rhs.Id1 - Id1 > MAX_ID/2) )
return false;
else if ( (Id1 > rhs.Id1) && (Id1 - rhs.Id1 > MAX_ID/2) )
return true;
else
return Id1 < rhs.Id1;
}

假设MAX_ID是25，如果考虑rhs的情况，则为第一个else。Id1是25并且Id1是1。第二个则考虑相反的情况，其中Id1=25和rhs。Id1=1。MAX_ID/2正在检查这两个值是否"相距甚远"，表示包裹在ID上。