Как реализовать оптимизированную структуру данных на основе координат?

Question

Я не знаю, существует ли такая структура, но мне интересно, есть ли что-то похожее на Map / Hash, которое имеет следующее поведение:

• , когдаэлемент назначен на карту, разработчик предоставляет «объект прямоугольника» (x, y, ширина, высота) в качестве ключа к элементу.

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

• для извлечения элемента на карте указывается позиция x и y, а элемент с прямоугольникомвозвращается эта позиция.

Answer 1

Не думаю, что в STL есть что-то готовое, но вы можете проверить полный список контейнеров здесь .

Вы можете довольно легко обернуть свою собственную пользовательскую реализацию.

Как насчет легкого прямоугольника:

struct Rectangle {
    int x;
    int y;
    int width;
    int height;
};

Затем контейнер, который содержит прямоугольники и обрабатывает логику добавления извлечения их:

struct ContainerOfRectangles {
    std::vector<Rectangle> rectangles;

    void AddNew(Rectangle r)
    {
        if (/* some condition is true */)
        {
            rectangles.push_back(r);
        }
    }

    Rectangle GetRectangle(Rectangle referenceRect)
    {
        for (const auto& rectangle : rectangles)
        {
            if (/* some condition on referenceRect and rectangle */)
            {
                return rectangle;
            }
        }
        // Something here if the rectangle wasn't found
        return Rectangle{};
    }
};

Вы можете обменять vector на другой контейнер, если хотите.