Нумерация одинаковых строк без изменения их порядка в массиве

[tumanovalex]

Тестовый массив строк

std::string str[] = {"строка", "01строка", "09строка", "04строка", "03строка", "01строка", "09строка", "05строка", "03строка", "строка", "01строка", "06строка", "03строка", "06строка", "09строка", "строка", "01строка", "05строка", "строка", "04строка", "строка", "09строка"};

Мне нужно пронумеровать одинаковые строки - в конец строки прибавить ее номер в формате "_00n" (например, строка_001, строка_002, 01строка_001, 01строка_002 и т.д.). При этом пронумерованная строка должна быть записана в другой массив на то же место, что и в исходном массиве (т.е. строка_001 на 1 место, строка_002 на 10 место и т.д.). Мне не удалось придумать алгоритм решения этой задачи. Подскажите, пожалуйста, алгоритм решения этой задачи средствами C++. Заготовку с исходным массивом прикрепил.
Прикреплённый файлvsTestCpp_Forum.zip (2,12 Кбайт, скачиваний: 18)

[Majestio]

Вот тебе решение. Правда я воспользовался std::vector, т.к. работаем с С++ и не будем тянуть Си-шный гемор.

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <map>
 
int main(int argc, char* argv[])
{
  std::vector<std::string> str = {"строка", "01строка", "09строка", "04строка", "03строка", "01строка",
                                  "09строка", "05строка", "03строка", "строка", "01строка", "06строка",
                                  "03строка", "06строка", "09строка", "строка", "01строка", "05строка",
                                  "строка", "04строка", "строка", "09строка"};
  // служебная "карта"
  std::map<std::string, uint64_t> map;
  // выходной массив
  std::vector<std::string> out;
  
  // собираем выходной массив  
  for(auto &&i:str) {
    map[i] = (map.count(i) > 0) ? map[i] + 1 : 1;
    std::ostringstream oss;
    oss << '_' << std::setfill('0') << std::setw(3) << map[i];
    out.push_back(i + oss.str());
  }
  
  // печать выходнго массива  
  for(auto &&i:out) {
      std::cout << i << std::endl;
  }
                                  
  return 0;
}

Вывод:

строка_001
01строка_001
09строка_001
04строка_001
03строка_001
01строка_002
09строка_002
05строка_001
03строка_002
строка_002
01строка_003
06строка_001
03строка_003
06строка_002
09строка_003
строка_003
01строка_004
05строка_002
строка_004
04строка_002
строка_005
09строка_004

Онлайн исполнение гляди тут.

[tumanovalex]

Спасибо большое за код! Буду в нем разбираться - не использовал раньше auto и map. Раньше программировал на C#, а C++ только сейчас стал изучать.

[ЫукпШ]

Цитата tumanovalex @ 14.06.23, 14:16

Мне не удалось придумать алгоритм решения этой задачи.

Алгоритм может быть и таким - проведём сортировку строк.
Одинаковые строки будут располагаться по-очереди.
Значит, в результате сортировки получим группы одинаковых,
следующих одна за другой.
Надо будет запомнить индекс расположения каждой строки.
Тут можно сделать структуру индекс + строка.
И сортировать массив таких структур, но по строкам.
Зная индекс, после сортировки и преобразования можно
правильно заполнить массив с результатами.

Сообщение отредактировано: ЫукпШ - 15.06.23, 14:07

[tumanovalex]

Я попробовал использовать вектор с парой (std:vector < pair<string, unsigned int>> vsn), потом сортировал вектор. В результате он отсортировался по строке в правильном порядке. Но потом возникла задача правильно добавить элементы в выходной массив, решение которой тоже потребовало дополнительного кода. Может быть это потому, что я плохо разбираюсь в C++.
С кодом Majestio я разобрался. По-моему, короче, чем у него, решения задачи не получится. Решение замечательное, я бы такое не придумал.

[Qraizer]

Цитата Majestio @ 14.06.23, 15:16

    map[i] = (map.count(i) > 0) ? map[i] + 1 : 1;

Тут map[i] слева может быть вычислено до map.count(i), что может ошибочно повести код по ветке > 0, если ключ только-только был создан. Как вариант, ?: можно заменить на if(), и проблем с порядком вычислений подвыражений не будет, но к счастью тут достаточно простого

    ++map[i];

[Majestio]

Цитата Qraizer @ 16.06.23, 12:06

Тут map[i] слева может быть вычислено до map.count(i), что может ошибочно повести код по ветке > 0, если ключ только-только был создан.

Интересно. Аргументируй плс

Добавлено 16.06.23, 12:48

Цитата Qraizer @ 16.06.23, 12:06

но к счастью тут достаточно простого

    ++map[i];

Да, так будет гораздо симпатичнее.

for(auto &&i:str) {
  std::ostringstream oss;
  oss << '_' << std::setfill('0') << std::setw(3) << ++map[i];
  out.push_back(i + oss.str());
}

На счет обращения к элементу с несуществующим ключом - буду знать)

[tumanovalex]

Спасибо всем ответившим!

[ЫукпШ]

Цитата tumanovalex @ 16.06.23, 11:30

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

Вот именно.
Чтобы получить опыт, надо больше работать.
Поэтому задачу можно модифицировать:
Если будет найдено 5 алгоритмов и сделано 5 реализаций - то это 5
Если 4 - оценка "хорошо".
Меньше 3-х - это "незачёт", всё сначала.

[tumanovalex]

Постараюсь работать больше и пытаться решать задачи разными способами

[Qraizer]

Цитата Majestio @ 16.06.23, 12:36

Интересно. Аргументируй плс

Операнды в выражении между точками следования могут вычисляться в произвольном порядке. Это операции обязаны выполняться в строгом порядке, но вот подготовка операндов для них не обязана соблюдать порядок их появления в выражении. Для операций присваивания есть дополнительное требование, что само присваивание выполняется после вычисления обоих операндов и перед формированием результата самой операции (спецом для каких-нибудь a=b=c+d, где результат b=c+d используется как правый операнд в присваивании a=), но нет требования вычислять правый операнд обязательно ранее левого.

P.S. Замечу, что в ?: вводится точка следования после вычисления условия, так что второй map[i] проблемы переупорядочивания с map.count(i) не имеет.

[Majestio]

Но ведь конструкция

map[i] = (map.count(i) > 0) ? map[i] + 1 : 1;

всё равно отрабатывает как должно? Можешь привести пример, когда "Тут map[i] слева может быть вычислено до map.count(i), что может ошибочно повести код по ветке > 0". Собственно, вопрос в "может быть вычислено". Может при каких условиях, что нужно, чтобы это произошло, и я мог бы это увидеть?

[Qraizer]

Не могу. Не от моего желания зависит, а от желания компилятора.

Добавлено 16.06.23, 18:10
Но можно сэмулировать на чём-то более простом.

#include <iostream>
 
int x[] = { 123, 456 }, *ptr = x;
 
int *print(const char* msg, int *ptr)
{
  std::cout << msg << ", arg is " << ptr << std::endl;
  return ptr;
}
 
int main()
{
  *print("pred", ptr) = *print("post", ptr++);
  std::cout << x[0] << ' ' << x[1] << std::endl;
}

Вызовы Функций и возвраты из них вносят точки следования, поэтому будет чётко видно, какой операнд вычисляется ранее, какой позднее.

D:\Work\delMe>cl -EHs -O1 -Fa q.cpp
Оптимизирующий компилятор Microsoft (R) C/C++ версии 19.36.32534 для x86
(C) Корпорация Майкрософт (Microsoft Corporation).  Все права защищены.
 
q.cpp
Microsoft (R) Incremental Linker Version 14.36.32534.0
Copyright (C) Microsoft Corporation.  All rights reserved.
 
/out:q.exe
q.obj
 
D:\Work\delMe>q
post, arg is 009B1000
pred, arg is 009B1004
123 123
 
D:\Work\delMe>cl -EHs -O2 -Fa q.cpp
Оптимизирующий компилятор Microsoft (R) C/C++ версии 19.36.32534 для x86
(C) Корпорация Майкрософт (Microsoft Corporation).  Все права защищены.
 
q.cpp
Microsoft (R) Incremental Linker Version 14.36.32534.0
Copyright (C) Microsoft Corporation.  All rights reserved.
 
/out:q.exe
q.obj
 
D:\Work\delMe\q>q
pred, arg is 00D43004
post, arg is 00D43000
123 123

При оптимизации по размеру компилятор решил вычислять сначала правый, а если по скорости, то левый.

P.S. Это минимальный пример. Стоит его чуть упростить, например, выкинуть печать x[], эффект пропадает.

[Majestio]

Не не , речь только о "?:" Я почитал, что для выражения "?:" точка следования появляется сразу после вычисления "условия". В нашем этом случае m.count(i) никаких модификаций не производит. Следовательно далее будет выполняться либо 2-е выражение, либо 3-е, в зависимости от 1-го. Как результат - никаких побочек не будет. Потенциальная "дырка" - предвычисление в блоке сравнение (до появления этой первой точки следования). Но у меня тут все ровно.

[Qraizer]

А. Ну да. Я ж так в P.S. и написал, что с ?: проблемы нет. В отличие от =. Левый для = операнд map[i] может быть вычислен раньше, чем начнётся вычисляться правый операнд =, поэтому map.count() уже насчитает 1. Благо, инициализирующее значение по умолчанию для decltype(map)::mapped_type будет равно 0, поэтому отработав true для ?:, получим ту же 1, что и для false. И тем не менее, дефект в коде есть, просто в данном конкретном случае он не приводит в багу. Зато в аналогичной ситуации в другом окружении запросто сможет.