Настройка индекса в векторе в C ++

Question

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

Например:

values  -> 3 2 4 1 5
indices -> 1 2 3 4 5    //yeah I know C++ indexing starts with 0. Well, while printing, I will add 1

result  -> 4 2 1 3 5    //Bear with me. I know its confusing. I will clarify below

Теперь результат был получен путем сортировки элементов и печати их более ранних индексов.

Как:

values(sorted)           -> 1 2 3 4 5
indices(before sorting)  -> 4 2 1 3 5

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

Я попробовал другой подход, пытаясь не использовать второй вектор. Итак, вот подход:

while (!vec_students.empty()) {
    std::vector<int>::iterator iterator = std::min_element(vec_students.begin(), vec_students.end());
    std::cout << std::distance(vec_students.begin(), iterator) + 1 << " ";
    vec_students.erase(iterator);
}

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

while (!vec_students.empty()) {
    static int i = 0;    //yeah I know standard static variables are initialised to 1.
    std::vector<int>::iterator iterator = std::min_element(vec_students.begin(), vec_students.end());
    std::cout << std::distance(vec_students.begin(), iterator) + i << " ";
    vec_students.erase(iterator);
    i++;
}

Теперь мысль выглядит так: Начальное решение:

vector:  2 3 1
expected output: 3 1 2 (For explanation refer above)
first index = indexof(min(2,3,1)) -> 2 (while printing add 1) -> 3
second index = indexof(min(2,3)) -> 0 (while printing....) -> 1
third index = indexof(min(3)) -> 0 (while...) -> 1

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

, поэтому я добавил дополнительные 1010 * штук. Решение работает:

vector: 2 3 1         i = 0
first index = indexof(min(2,3,1)) -> 3 -> add i -> 3 -> increment i -> i = 1
second index = indexof(min(2,3)) -> 0 -> add i -> 1 -> increment i -> i = 2
third index = indexof(min(3)) -> 0 -> add i -> 2 -> increment i -> i = 3

и программа заканчивается.

Но в вышеприведенном случае вместо 3 1 2 я получаю 3 2 3 (первое значение справа, остальные увеличены на 1)

Что не так с моими логи c?

Answer 1

индекс всех элементов уменьшается на определенное значение.

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

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>

int main() {
  std::vector<int> v{3, 2, 4, 1, 5};
  auto const* beg = v.data();
  auto sz = v.size();
  while (sz--) {
    auto const min = std::min_element(v.begin(), v.end());
    std::cout << &*min - beg << ' ';
    *min = std::numeric_limits<int>::max();
  }
}

Это не будет работать должным образом, если в вашем векторе INT_MAX. В любом случае, создание второго вектора может дать лучшие решения. Пример:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

int main() {
  std::vector<int> v{3, 2, 4, 1, 5};
  std::vector<int const*> addresses;
  addresses.reserve(v.size());
  std::transform(v.cbegin(), v.cend(), std::back_inserter(addresses),
                 [](auto const& elm) { return &elm; });

  std::sort(addresses.begin(), addresses.end(),
            [](int const* const ptr1, int const* const ptr2) {
              return *ptr1 < *ptr2;
            });

  for (auto* p : addresses) {
    std::cout << p - v.data() << ' ';
  }
}

Answer 2

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

Ну, не совсем, только те после должны быть выполнены с удаленным элементом.

---

пример.

[2,1,3] => [2,3]

индекс 2 остается на 0,

, в то время как индекс 3 становится 1 с 2

---