Я хочу решить следующую задачу — мне дан вектор целых чисел. Я хочу «сжать» этот список, в котором элементы будут заменены числами 0 через n - 1, где n — количество уникальных элементов в векторе, при которых сохраняется относительный порядок элементов, т. е. если ранее vector[index1] < vector[index2], то это все еще верно после сжатия. Другими словами, каждый элемент заменяется его рейтингом среди исходного вектора.

Например, учитывая вектор {1, 3, 10, 6, 3, 12}, элементы будут заменены на 0 через 4 так как есть 5 уникальных значений. Для сохранения порядка он будет преобразован в {0, 1, 3, 2, 1, 4}.

Прямо сейчас, чтобы завершить это, я использую следующий алгоритм:

#include <iostream>
#include <map>
#include <set>
#include <vector>

using namespace std;

int compress_vector(vector<int>& vec) {
  // function compresses the vector passed in by reference
  // and returns the total number of unique elements
  map<int, int> m;
  set<int>      s;
  for (auto i : vec) s.insert(i);
  int counter = 0;
  for (auto i : s) {
    m[i] = counter;
    counter++;
  }
  for (auto& i : vec) i = m[i];
  return s.size();
}

int main() {
  vector<int> vec = { 1, 3, 10, 6, 3, 12 };  //

  int size = compress_vector(vec);

  // Should output "0 1 3 2 1 4", then a newline, then a "5"
  for (auto i : vec) cout << i << " ";
  cout << endl;
  cout << size;

  return 0;
}

Однако мне кажется, что эта функция довольно беспорядочная — она ​​использует карты, наборы и счетчики. Хотя это функционально, есть ли Быстрее или же очиститель способ сделать это?

Спасибо

Улучшения алгоритма

Я действительно не понимаю, что должен делать этот алгоритм. Ваше описание неполное и расплывчатое (например, вы говорите vector[index1] < vector[index2]… Но что это index1 и index2?), и единственный пример не проясняет. Это выглядит как будто вы просто пытаетесь получить отсортированную позицию каждого элемента в векторе. Так что вполне возможно, что есть много лучший алгоритм, который может решить эту проблему; у меня нет возможности узнать, когда то, что вы пытаетесь сделать, не имеет для меня смысла.

Однако я может посмотрите, что делает ваша существующая реализация, и хотя бы немного улучшите ее.

Вы используете набор, чтобы получить все уникальные элементы в векторе, а затем вы используете карту, чтобы получить … Я не знаю, что-то что-то считается (отсортированный индекс?). Я не могу вам помочь со второй частью. Но я может помочь вам с первой частью, потому что вам не нужен набор. Вы можете использовать карту для получения уникальных значений, например:

auto compress_vector(std::vector<int>& vec)
{
    auto m = std::map<int, int>{};

    // You don't need the set. You can use the map's keys to get the unique
    // values.
    for (auto i : vec)
        m[i] = 0;

    // And then you can recover the "set" of unique values by just iterating
    // on the map's keys.
    auto counter = 0;
    for (auto [i, _] : m)
        m[i] = counter++;

    // The above loop may be optimized by avoiding the duplicate lookup:
    //  for (auto& p : m)
    //      p->second = counter++;

    for (auto& i : vec)
        i = m[i];

    return m.size();
}

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

auto compress_vector(std::vector<int>& vec)
{
    auto s = std::set<int>{};

    for (auto i : vec)
        s.insert(i);

    // The values of the map are just the indices of the set.
    for (auto& i : vec)
        i = std::distance(s.begin(), s.find(i));

    return s.size();
}

В зависимости от множества факторов мощь быть более эффективным, чтобы отказаться от набора и вместо этого использовать отсортированный вектор:

auto compress_vector(std::vector<int>& vec) {
    // Take care of the degenerate case of an empty input vector first.
    //
    // Not strictly necessary, but will save a lot of work.
    if (vec.empty())
        return 0;

    // You could also do this:
    //  if (vec.size() == 1)
    //  {
    //      vec[0] = 0;
    //      return 1;
    //  }

    // A second container, either a map, set, or second vector, is probably
    // unavoidable, because we need to keep track of the original values while
    // also changing the vector's contents, in order to know the sorted
    // indices.
    //
    // Note that this is the lazy way of building the sorted vector. If there
    // are a lot of duplicate values, it *might* be faster to:
    //  1)  reserve vec.size()
    //  2)  for each element in vec, do a lower_bound() search, to find if
    //      it's already in sorted, and if not, then you have the insert
    //      position
    auto sorted = vec;
    std::sort(sorted.begin(), sorted.end());
    sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());

    // Transform each element in the input vector into the index of the
    // element in the sorted vector.
    std::transform(vec.begin(), vec.end(), vec.begin(),
        [&sorted](auto i)
        {
            // Instead of std::find(), you could also use a binary search,
            // like std::lower_bound().
            return static_cast<int>(
                std::distance(
                    sorted.begin(),
                    std::find(sorted.begin(), sorted.end(), i)
                )
            );
        }
    );

    return sorted.size();
}

Код ревью

using namespace std;

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

int compress_vector(vector<int>& vec)

«Out» параметры (параметры функции, принимаемые не-const ссылка, а затем измененная с помощью «возвращаемого» значения), как правило, не очень хорошая идея. Обычно они усложняют использование функций, поскольку возлагают на пользователя ответственность за создание места для возврата. Что, если мне нужен исходный вектор и «сжатый» вектор? Теперь мне нужно разобраться с болью, связанной с настройкой результата вручную, а не просто написанием auto result = compress_vector(input);. И если вектор, который я хочу «сжать», уже const (что часто бывает), я должен снова сделать копию.

Я знаю, что есть аргумент в пользу того, что параметры out могут быть более эффективными, но здесь это не применимо, потому что вы все равно создаете целые карты, наборы и / или копии вектора в функции.

Еще лучше было бы использовать аргумент итератора вывода.

for (auto i : vec) s.insert(i);

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

for (auto i : vec) s.insert(i);
int counter = 0;
for (auto i : s) {
  m[i] = counter;
  counter++;
}
for (auto& i : vec) i = m[i];

Разместите код. Есть ТРИ петли здесь, замятые все вместе. Это три полностью отдельных логических раздела функции. Каждый раздел должен быть отделен от других пустой строкой, чтобы было понятно, где находятся «абзацы» функции. (И, конечно же, первая и последняя петли не должны быть отдельными линиями.)

Вам также следует подумать об использовании алгоритмов вместо голых циклов по двум причинам. Во-первых, они делают ваш код более понятным: голый цикл может делать ЧТО-НИБУДЬ… Но алгоритм точно объясняет, что происходит. Также алгоритмы много проще оптимизировать.

Итак, большой кусок кода выше может быть:

std::for_each(vec.begin(), vec.end(), [&s](auto i) { s.insert(i); });

auto counter = 0;
std::for_each(s.begin(), s.end(), [&m, &counter](auto i) { m[i] = counter++; });

std::for_each(vec.begin(), vec.end(), [&m](auto& i) { i = m[i]; });

Конечно, все три алгоритма for_each() здесь, потому что я действительно не понимаю, что должны делать циклы. for_each() это то, что вы используете, когда ничто другое не имеет смысла. Вы заметите, что в модифицированном алгоритме, который я написал выше, я использовал более конкретные алгоритмы, например transform(), unique(), и find() потому что я понял, что происходит.

return s.size();

У вас здесь ошибка. s.size() дает беззнаковый тип, что достаточно проблематично, но реальная проблема в том, что тип может быть (и часто бывает) больше, чем int. Но вы заставляете его втиснуть в int, что может вызвать усечение или другие странности. Если ты абсолютно уверен, что хочешь compress_vector() возвращаться int, то вы должны хотя бы утверждать, что размер вектора меньше максимального значения int. Или, с другой стороны, может быть, вы действительно не хотите compress_vector() возвращаться int? Я не понимаю, что вы хотите от этой функции, поэтому не могу угадать, какой ответ правильный.

В main():

for (auto i : vec) cout << i << " ";

Еще раз, это не должно быть в одной строке. Кроме того, вам, вероятно, не нужна целая строковая константа вместо пробела; вы, наверное, имеете в виду ' ', нет " ".

cout << endl;

std::endl действительно не имеет здесь смысла. Если вам нужна новая строка, используйте новую строку: std::cout << 'n';.

return 0;

Вам это не нужно main().

Резюме

Поскольку ваше описание проблемы настолько расплывчато и неполно, а ваши примеры предполагаемого использования настолько ограничены и не раскрывают, невозможно дать хорошие рекомендации. В этой функции так много необъяснимого, и так много вопросов без ответа: действительно ли нужно изменять входной вектор; не мог бы он вместо этого просто вернуть новый вектор? Почему он возвращает количество уникальных элементов; это действительно важная информация? Почему он возвращает это значение как int, скорее, чем std::size_t или же std::vector::size_type? И так далее.

Лучшее, что я могу сделать, это предложить предложения базового уровня, основанные на буквальных операциях в данном коде; Другими словами, я могу только дать предложения по настройке существующего алгоритма … Я не могу предложить лучше алгоритмы, если таковые имеются.

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