Использование ключа, который учитывает опрокидывание или перенос значения ключа в std :: map - PullRequest
Новая
       40

Использование ключа, который учитывает опрокидывание или перенос значения ключа в std :: map

0 голосов
/ 05 ноября 2018

Возможно ли иметь ключ для std::map, который учитывает опрокидывание или перенос ключа? и если да, то как бы вы реализовали оператор <для этого? </p>

Предположим, что ключ основан на счетчике с максимальным значением N, если возможно иметь оператор <, который учитывает, когда значение ключа переворачивается, чтобы элементы упорядочивались на карте следующим образом: </p> 

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

Кроме того, возможно ли это сделать, если значения ключей можно пропустить? Например, N пропускается, поэтому карта имеет следующие значения: 

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

Ответы [ 3 ]

0 голосов
/ 05 ноября 2018

Вот пример того, как это можно реализовать. Идея состоит в том, чтобы ввести пользовательский шаблон Key, который можно параметризовать с желаемым максимальным значением во время компиляции. Сравнение и базовые арифметические операции предоставляются через библиотеку операторов boost *1003*, так что 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";
0 голосов
/ 06 ноября 2018

Вот решение, которое мне удалось получить.

Ключ на самом деле <unsigned int, unsigned int>, при упорядочении относительно ролловера необходимо учитывать только первое значение ключа. Кроме того, идентификатор равен 1, поэтому значения будут 1, 2, ..., N, 1, 2, ... Наконец, обратите внимание, что MAX 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.Id1 - 25, а Id1 - 1. Второй - рассматривает противоположный случай с Id1 = 25 и rhs.Id1 = 1. MAX_ID / 2 проверяет, что два значения находятся «далеко друг от друга», что указывает на перенос идентификатора.

0 голосов
/ 05 ноября 2018

Да.

Используя < для 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;
}

Посмотри вживую на колиру

...