Что самый эффективный путь состоит в том, чтобы стереть дубликаты и отсортировать вектор?

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

foreach ($data as $index => $student) {

   echo "<br>";
   echo $student['name']." " . "= ";
   echo $student['notes'][$index];
   echo "<br>";
}

Вы должны быть уверены, что вы всегда будете иметь столько же заметок, сколько указатель, к которому вы обращаетесь к мысли

253
задан chema989 23 November 2016 в 08:03
поделиться

11 ответов

Я согласен с Р. Пейт и Тодд Гарднер ; Здесь может быть хорошей идеей std :: set . Даже если вы застряли в использовании векторов, если у вас достаточно дубликатов, возможно, вам лучше создать набор для выполнения грязной работы.

Давайте сравним три подхода:

Просто используя вектор, сортировка + уникальный

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

Преобразовать в набор (вручную)

set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

Преобразовать в набор (с помощью конструктора)

set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

Вот как они работают при изменении количества дубликатов:

comparison of vector and set approaches

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

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

550
ответ дан 23 November 2019 в 02:49
поделиться

С библиотекой Ranges (в C ++ 20) вы можете просто использовать

action::unique(vec);

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

0
ответ дан 23 November 2019 в 02:49
поделиться
void removeDuplicates(std::vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++)
    {
        for (int j = i + 1; j < arr.size(); j++)
        {
            if (arr[i] > arr[j])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    std::vector<int> y;
    int x = arr[0];
    int i = 0;
    while (i < arr.size())
    {
        if (x != arr[i])
        {
            y.push_back(x);
            x = arr[i];
        }
        i++;
        if (i == arr.size())
            y.push_back(arr[i - 1]);
    }
    arr = y;
}
0
ответ дан 23 November 2019 в 02:49
поделиться

Эффективность - сложное понятие. Здесь нужно учитывать время и пространство, а также общие измерения (где вы получаете только расплывчатые ответы, такие как O (n)) по сравнению с конкретными (например, пузырьковая сортировка может быть намного быстрее, чем быстрая сортировка, в зависимости от входных характеристик).

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

Не сосредотачивайтесь только на эффективности времени. Сортировка + уникальность + стирание работает в пространстве O (1), а конструкция множества работает в пространстве O (n). И ни один из них напрямую не поддается распараллеливанию с уменьшением карты (для действительно огромных наборов данных).

7
ответ дан 23 November 2019 в 02:49
поделиться

Вот шаблон, который сделает это за вас:

template<typename T>
void removeDuplicates(std::vector<T>& vec)
{
    std::sort(vec.begin(), vec.end());
    vec.erase(std::unique(vec.begin(), vec.end()), vec.end());
}

назовите это так:

removeDuplicates<int>(vectorname);
17
ответ дан 23 November 2019 в 02:49
поделиться

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

редактировать: 38 секунд ...

7
ответ дан 23 November 2019 в 02:49
поделиться

std :: unique работает только с последовательными запусками повторяющихся элементов, поэтому лучше сначала выполнить сортировку. Однако он стабилен, поэтому ваш вектор останется отсортированным.

21
ответ дан 23 November 2019 в 02:49
поделиться

std :: unique удаляет повторяющиеся элементы, только если они являются соседями: вам нужно сначала отсортировать вектор, прежде чем он будет работать так, как вы предполагаете.

std :: unique определяется как стабильный, поэтому вектор все равно будет отсортирован после выполнения для него уникального.

49
ответ дан 23 November 2019 в 02:49
поделиться

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

6
ответ дан 23 November 2019 в 02:49
поделиться

Как уже говорилось, unique требует отсортированного контейнера. Дополнительно, unique фактически не удаляет элементы из контейнера. Вместо этого они копируются до конца, unique возвращает итератор, указывающий на первый такой повторяющийся элемент, и ожидается, что вы вызовете erase для фактического удаления элементов.

2
ответ дан 23 November 2019 в 02:49
поделиться

Я не уверен, для чего вы это используете, поэтому я не могу сказать это со 100% уверенностью, но обычно, когда я думаю о «отсортированном уникальном» контейнере, я думаю о std :: set . Это может быть лучше для вашего варианта использования:

std::set<Foo> foos(vec.begin(), vec.end()); // both sorted & unique already

В противном случае сортировка перед вызовом unique (как указывалось в других ответах) - это путь.

40
ответ дан 23 November 2019 в 02:49
поделиться
Другие вопросы по тегам:

Похожие вопросы: