Какой простой способ сортировки этих отдельных, но связанных последовательностей в C ++?

Question

У меня есть два vector объекта, которые содержат разные типы данных, которые упорядочены одинаково. Моя ситуация выглядит примерно так:

struct Info
{
    double opaque_data_not_relevant_to_this_problem[6];
    int data_len;

    bool operator<(const Info &rhs) const
    {
        return (bool) irrelevant_operation_on_opaque_data;
    }
};

vector<Info> vec1;
vector<double> vec2;

Для каждой записи Info в vec1, vec2 содержит последовательность значений double, равную по длине значению data_len в соответствующем элементе в vec1. Например:

vec1[0].data_len == 100 ==> vec2[0:99] correspond to vec1[0]
vec1[1].data_len == 150 ==> vec2[100:249] correspond to vec1[1]
// and so on

Я понимаю, что эта схема не очень оригинальна, и, вероятно, для этого есть "более C ++". Однако другие ограничения в моей среде вынуждают меня к этому типу упаковки данных, поэтому мне нужно обойти это. К сожалению, длина каждой записи данных в vec2 (указанная ее data_len аналогом в vec1) неизвестна до времени выполнения, и длина варьируется от записи к записи.

Моя проблема: я хотел бы отсортировать два вектора по некоторым критериям. Сортировка vec1 проста, так как я могу просто использовать std::sort. В то же время, однако, мне нужно отсортировать vec2 таким образом, чтобы описанный выше порядок все еще сохранялся (то есть первый блок значений в vec2 соответствует vec1[0] после его сортировки). Было бы хорошо, если бы я мог получить какой-то «индексный вектор» из процесса сортировки, который я мог бы затем использовать для переупорядочения vec2 (операция на месте или вне места была бы в порядке), но я не уверен, что это можно сделать с помощью стандартной библиотеки (если она есть).

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

struct SortableInfo
{
    Info info;
    vector<double> data;

    bool operator<(const SortabelInfo &rhs) const { return info < rhs.info; }
};
vector<SortableInfo> vec3;

Затем я бы заполнил vec3 соответствующим образом, основываясь на содержании vec1 и vec2, отсортировав его, а затем вернув данные обратно в отдельные векторы. Тем не менее, это не кажется особенно эффективным. Любые предложения о лучшем способе выполнить это?

Answer 1

Вы можете сохранить в ваших SortableInfo указателях начальные позиции в соответствующих vec2

struct SortableInfo {
    Info info;
    double *start_pos;

    bool operator<(const SortabelInfo &rhs) const { return info < rhs.info; }
}

заполнить ваш vec3, отсортировать его и затем в конце сделать упорядоченную копию вашегоvec2 с использованием отсортированных указателей.

Answer 2

Просто сохранить смещение в Info?

struct Info
{
    int data_len;
    int offset;
    bool operator<(const Info &rhs) const
    {
        return (bool) irrelevant_operation_on_opaque_data;
    }
};

смещение - это просто смещение в вашем vec2 так что теперь вы можете иметь, например,

vec1[0].offset = 350, vec1[0].data_len = 100 ==> vec2[350:450] = your data

Если вы также хотите поддержать удаление, вам нужно переопределить все ваши offset, и это решение может быть не столь эффективным.

Теперь вы можете просто отсортировать и по-прежнему использовать offset для поиска данных.

---

Просто определите новый Struct и используйте его в качестве оболочки.

struct ExtendedInfo
{
    Info info;
    int offset;
}

Answer 3

Я не знаю, каково конкретное ограничение, которое заставляет вас связывать ваши данные таким образом, но ваша опция vec3 близка к объектно-ориентированному способу ведения дел.

То, что я хотел бы сделать, это просто сделать 1 вектор вашей структуры (или класса в зависимости от ваших потребностей) в первую очередь и забыть об отдельных векторах в первую очередь.

Есть ли конкретная причина, по которой вы не можете этого сделать?