Использование контейнера std :: set для элементов диапазона - PullRequest
Новая
       22

Использование контейнера std :: set для элементов диапазона

0 голосов
/ 05 марта 2019

Я бы хотел хранить кучу предметов в контейнере std::set.

Эта структура данных должна обеспечивать быстрое решение о том, является ли конкретный входной диапазон, содержащийся в одном из диапазонов, который хранится в наборе, перегруженным при сравнении std::set, чтобы использовать метод set::find для проверки одного изэлементы в наборе содержат аргумент входного диапазона.

Он также должен поддерживать элемент диапазона, представляющий одну точку (start_range == end_range).

Вот моя реализация: 

#include <iostream>
#include <map>
#include <set>
using std::set;
using std::map;

class range : public std::pair<int,int>
{
public:
    range(int lower, int upper)
    {
        if (upper < lower)
        {
           first = upper;
           second = lower;
        }
        else
        {
           first = lower;
           second = upper;
        }
    }
    range(int val)
    {
        first = second = val;
    }
    bool operator<(range const & b) const
    {
        if (second < b.first)
        {
            return true;
        }
        return false;
    }
};

А вот как я тестирую свою структуру данных: 

int main(int argc, const char * argv[])
{
    std::map<int, std::set<range>> n;

    n[1].insert(range(-50,-40));
    n[1].insert(range(40,50));
    n[2].insert(range(-30,-20));
    n[2].insert(range(20,30));
    n[3].insert(range(-20,-10));
    n[3].insert(range(10,20));

    range v[] = {range(-50,-41), range(30,45), range(-45,-45), range(25,25)};
    int j[] = {1,2,3};
    for (int l : j)
    {
        for (range i : v)
        {
            if (n[l].find(i) != n[l].end())
            {
                std::cout << l << "," << i.first << ","  << i.second << " : " 
                          << n[l].find(range(i))->first  << " "
                          << n[l].find(range(i))->second << std::endl;
            }
        }
    }
}

и вот результаты, которые я получаю: 

1,-50,-41 : -50 -40 --> good 
1,30,45 : 40 50     --> bad
1,-45,-45 : -50 -40 --> good
2,30,45 : 20 30     --> bad
2,25,25 : 20 30     --> good

Так что, как вы можете видеть, мой код действительно отлично поддерживаетдиапазон одной точки (-45 содержится в диапазоне (-50, -40), а 25 - в диапазоне (20,30))

Однако, что касается более широких диапазонов, мой текущий оператор <способен найти отношение contained, которое equal для терминологии set (имеется в виду, что для диапазонов a и b a<b && a<b.

Есть ли способ изменить этот оператор, чтобы он работал?

Ответы [ 3 ]

0 голосов
/ 05 марта 2019

Похоже, идеально подходит для использования Boost Interval Container Library .Короче говоря, вы можете 

#include <boost/icl/interval_set.hpp>

// Helper function template to reduce explicit typing:
template <class T>
auto closed(T&& lower, T&& upper)
{
   return boost::icl::discrete_interval<T>::closed(std::forward<T>(lower),
        std::forward<T>(upper));
}

boost::icl::interval_set<int> ranges;

ranges.insert(closed(1, 2));
ranges.insert(closed(42, 50));

std::cout << contains(ranges, closed(43, 46)) << "\n"; // true
std::cout << contains(ranges, closed(42, 54)) << "\n"; // false

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

0 голосов
/ 05 марта 2019

Ваш оператор сравнения не подходит.

Если вы хотите использовать какой-либо контейнер или алгоритм, основанный на упорядочении в C ++, отношение упорядочения должно быть Строгое слабое отношение упорядочения .Определение можно найти в Википедии , короче говоря, должны соблюдаться следующие правила:

  • Нерефлексивность : для всех х в S это неслучай, когда x
  • асимметрия : для всех x, y в S, если x
  • Транзитивность : Для всех x, y, z в S, если x
  • Транзитивность несопоставимости : Для всех x,y, z в S, если x несопоставимо с y (ни x

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

bool operator<(range const & b) const
{
    return std::tie(first, second) < std::tie(b.first, b.second);
}

Вам нужна карта, а не набор.

Чтобы решитьваша проблема, вам нужна карта, а не набор.

Для непересекающихся интервалов достаточно карты от нижней границы до верхней: 

std::map<int, int> intervals;

.lower_bound и *Операции 1039 * позволяют найти ближайший ключ за время O (log N), и отсюда быстро утверждается удержание.

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

0 голосов
/ 05 марта 2019

Ваш operator < определяет частичный порядок: (30,45) < (40, 50) == false и одновременно (40, 50) < (30, 45) == false, поэтому в терминах std::set и std::map они равны.Вот почему вы получили эти результаты.

Есть документ о частичном порядке: https://en.wikipedia.org/wiki/Partially_ordered_set

Возможно, вы захотите использовать std::unordered_map или определить каким-либо образом общий порядок для ваших диапазонов.

Я предлагаю operator <, который сравнивает среднее арифметическое границ диапазона, то есть (a, b) <(c, d) тогда и только тогда, когда (a + b) / 2 <(c + d) / 2 для всегопорядок.Обратите внимание, что вы можете использовать float для среднего арифметического. </p>

Для тестирования я предлагаю следующий черновик кода (я пишу здесь с нуля и не проверял его).-1 означает, что диапазон не содержит this

int range::firstContainsMe(const std::vector<range> rangesVec)
{
    for (size_t i = 0; i < rangesVec; i++) {
        if (lower >= rangesVec[i].lower && upper <= rangesVec[i].upper) {
            return i;
        }
    }
    return -1;
}
...