Каков наилучший способ получить список индекса перестановки данного вектора

Question

В моем приложении я решаю геометрическую задачу для заданного списка точек.

0 x0 y0
1 x1 y1
...

Файл решения должен содержать определенный порядок точек, представленных в виде списка их индексов.

1
0
...

После решения проблемы у меня есть вектор точечных объектов result = std::vector<Point>() в определенном порядке, а также исходный список точек в виде вектора original = std::vector<Point>().Оба вектора, естественно, имеют одинаковый размер.Чтобы сгенерировать выходной файл, я перебираю вектор result и ищу индекс точки в векторе original.Это довольно неэффективно, потому что для этого нужно O(n^2) времяВ качестве небольшого улучшения я делаю следующее:

std::ofstream out(filename);

std::vector<int> indices(instance.size);
std::iota(indices.begin(), indices.end(), 0);

for(auto &point : instance.result.points)
{
    for(std::size_t i=0; i<indices.size(); i++)
    {
        int id = indices[i];
        if(point == instance.points[id])
        {
            out << id << std::endl;
            indices.erase(indices.begin()+i);
            break;
        }
    }
}

out.close();

Это позволяет мне не возвращаться к пунктам, которые я уже нашел ранее.К сожалению, для экземпляра в 1 миллион точек этот процесс превышает мой лимит времени, и я не хочу, чтобы экспорт моего решения занимал больше времени, чем решение самой проблемы.Есть ли способ эффективно получить индексы премутации некоторого вектора в C ++?При желании решение может использовать много памяти.

Answer 1

Одним из простых и довольно эффективных решений является создание временного std::unordered_map<Point,size_t>, где ключ - это точка, а значение - позиция внутри original, а затем выполните поиск на этой карте. Подробная информация о том, как использовать ваш (или предоставленный библиотекой) тип данных в качестве ключа в std::unordered_map при условии здесь

Answer 2

Вы можете расширить структуру Point, чтобы она содержала оригинальный идентификатор, кроме позиции.