Карта из целых диапазонов в произвольные одиночные целые числа

Ответ 1

Я бы использовал очень простую вещь: std::map.

class Range
{
public:
  explicit Range(int item);  // [item,item]
  Range(int low, int high);  // [low,high]

  bool operator<(const Range& rhs) const
  {
    if (mLow < rhs.mLow)
    {
      assert(mHigh < rhs.mLow); // sanity check
      return true;
    }
    return false;
  } // operator<

  int low() const { return mLow; }
  int high() const { return mHigh; }

private:
  int mLow;
  int mHigh;
}; // class Range

Тогда пусть имеет отображение:

typedef std::map<Range, int> ranges_type;

И напишите функцию, которая выполняет поиск на этой карте:

int find(int item, const ranges_type& ranges)
{
  ranges_type::const_iterator it = ranges.lower_bound(Range(item));
  if (it != ranges.end() && it->first.low() <= item)
    return it->second;
  else
    return 0; // No mapping ?
}

Основные преимущества:

• Будет проверять, что диапазоны эффективно не перекрываются при вставке в набор (вы можете сделать это так, чтобы он был только в режиме отладки)
• Поддерживает издание диапазонов "на лету"
• Быстрый поиск (двоичный поиск)

Если диапазоны заморожены (даже если их значения не указаны), вы можете использовать Loki::AssocVector, чтобы уменьшить накладные расходы на память и немного улучшить производительность (в основном это отсортированный вектор с интерфейсом карты).

Ответ 2

Лучший подход здесь - это бинарный поиск, но любой эффективный поиск по порядку будет отлично работать. Вам не нужно явно выполнять поиск и структуру данных. Вы можете использовать его косвенно, используя вместо этого стандартный ассоциативный контейнер.

Поскольку ваши диапазоны не перекрываются, решение очень простое. Вы можете сразу использовать std::map для решения этой проблемы только в нескольких строках кода.

Например, это один из возможных подходов. Предположим, что мы сопоставляем диапазон [ int, int ] с значением int. Представим наши диапазоны как замкнутые диапазоны, т.е. Если исходный диапазон [0, 70], рассмотрим вместо этого диапазон [0, 71). Кроме того, позвольте использовать значение 0 как "зарезервированное" значение, которое означает "отсутствие сопоставления" (как вы просили в своем вопросе)

const int EMPTY = 0;

Все, что вам нужно сделать, это объявить карту от int до int:

typedef std::map<int, int> Map;
Map map;

и заполнить его каждым концом ваших закрытых диапазонов. Левый (закрытый) конец должен быть сопоставлен с желаемым значением, на который отображается весь диапазон, а правый (открытый) конец должен быть сопоставлен с нашим значением EMPTY. Для вашего примера это будет выглядеть следующим образом

map[0] = r_a;
map[71] = EMPTY;

map[101] = r_b;
map[251] = EMPTY;

map[260] = r_c; // 260 adjusted from 201
map[401] = EMPTY;

(Я скорректировал ваш последний диапазон, так как в вашем исходном примере он перекрывал предыдущий диапазон, и вы сказали, что ваши диапазоны не перекрываются).

Это для инициализации.

Теперь, чтобы определить, где заданное значение i отображает все, что вам нужно сделать, это

Map::iterator it = map.upper_bound(i);

Если it == map.begin(), то i не находится в любом диапазоне. В противном случае do

--it;

Если it->second (для декрементированного it) - EMPTY, то i не находится в любом диапазоне.

Объединенная проверка пропусков может выглядеть следующим образом

Map::iterator it = map.upper_bound(i);
if (it == map.begin() || (--it)->second == EMPTY)
  /* Missed all ranges */;

В противном случае it->second (для декрементированного it) - ваше отображаемое значение

int mapped_to = it->second;

Обратите внимание, что если исходные диапазоны "касались", как в [40, 60] и [61, 100], тогда диапазоны с закрытым открытием будут выглядеть как [40, 61) и [61, 101), что означает, что значение 61 будет отображается дважды во время инициализации карты. В этом случае важно удостовериться, что значение 61 отображается на нужное значение назначения, а не на значение EMPTY. Если вы сопоставляете диапазоны, как показано выше, в порядке слева (справа), то он будет работать сам по себе.

Обратите внимание, что в карту вставляются только конечные точки диапазонов, что означает, что потребление памяти и производительность поиска зависят только от общего количества диапазонов и полностью не зависят от их общей длины.

Если вы хотите, вы можете добавить элемент "guard" на карту во время инициализации

map[INT_MIN] = EMPTY;

(это соответствует "отрицательной бесконечности" ), и проверка "пропустить" станет проще

Map::iterator it = map.upper_bound(i);

assert(it != map.begin());
if ((--it)->second == EMPTY)
  /* Missed all ranges */;

но это только вопрос личных предпочтений.

Конечно, если вы хотите вернуть 0 для не отображаемых значений, вам вообще не нужно выполнять какие-либо проверки. Просто возьмите it->second из декрементированного итератора, и вы закончите.

Ответ 3

Не хватит ли простого массива? Вы не говорите, сколько у вас элементов, но, безусловно, самая быстрая структура данных - это простой массив.

Если диапазоны:

• 0..9 → 25
• 10..19 → 42

Тогда массив будет выглядеть следующим образом:

[25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42]

Ответ 4

У вас могут быть два отсортированных массива: один для нижних границ, один для верхних границ. Используйте std::lower_bound(lower_bound_array, value) и std::upper_bound(upper_bound_array, value). Если индекс обоих результатов одинаковый, return index + 1. В противном случае return 0.

Если возвращаемые индексы совпадают, это означает, что значение >= нижняя граница и < верхняя граница. Если они этого не сделают, то вы находитесь между диапазонами.

Ответ 5

Идеал является деревом интервалов (специализированное двоичное дерево). Википедия полностью описывает этот метод. Лучше, чем я. Вы не будете намного более оптимальными, чем это, не жертвуя пространством для производительности.

Ответ 6

Простой Связанный список, содержащий записи диапазона, должен быть достаточно быстрым, даже для 50-100 диапазонов. Более того, вы можете реализовать Список пропусков, на верхних границах, чтобы ускорить эти запросы диапазона. Еще одна возможность - Дерево интервала.

В конечном итоге я бы выбрал самый простой: двоичный поиск.

Ответ 7

В вашем примере пробелы перекрываются, но вопрос говорит, что они не будут. Я предполагаю, что диапазон - опечатка. Вы могли бы сохранить хранилища в массиве и использовать индексы в качестве диапазонов. Это довольно легко, но уродливо и не очень удобно. Вам нужно будет инициализировать массив до 0, затем для каждого диапазона, перебрать эти индексы и установить каждый индекс в значение назначения. Очень уродливое, но постоянное время поиска, поэтому, может быть, полезно, если числа не становятся слишком высокими, а диапазоны не меняются очень часто.

Ответ 8

Запишите пределы в set (или map). Когда вы вызываете insert, вы получите возвращаемое значение, которое является парой. Итератор и логическое. Если логическое значение true, то создается новый элемент, который вы должны удалить позже. После этого выполните один шаг с итератором и посмотрите, что вы нашли.

http://www.cplusplus.com/reference/stl/set/insert/ См. Возвращаемое значение

Ответ 9

Это 1-мерный пространственный индекс. Например, двоичное дерево в стиле Quadtree, и есть несколько других широко используемых методов.

Ответ 10

Вы можете найти Minimal Perfect Hashing Function полезным, http://cmph.sourceforge.net/.