0

Как сортировать по признаку того что ключ данного элемента является значением другого? т.е надо сортировать по тому что значение первого является ключом второго std::map< sNode, sNode > test; И вообще можно ли так сделать?

8
  • Сортировать? Или сделать выборку таких элементов, что величины содержат ключ текущего элемента? 31 авг 2017 в 19:37
  • Что именно вы хотите сделать? std::map внутри строит дерево, сортируя ключи по признаку больше/меньше-равно. Если сортировать по признаку равно/не равно, то дерево очень глупое получится, в нем поиск медленный будет как перебор. Если вам нужна "двунаправленная" карта, то просто добавляйте пары и (k, v), и (v, k). Можете завернуть данные в структуры, где будет дополнительное поле, которое говорит, чем это изначально было, ключом или значением.
    – user239133
    31 авг 2017 в 19:46
  • Предположим так: берем ключ каждого и смотрим есть ли в мапе пара с значением = этому ключу. Если нет таких то это последний, берем значение его, и ищем среди ключей элементов, и так с каждым следующим найденным в цикле. 31 авг 2017 в 19:51
  • @Disastricks, а ну тогда просто берете вторую карту и не мучаете себе мозги.
    – user239133
    31 авг 2017 в 19:52
  • почему последний, если начнем с рандомного то может не пройтись по всем 31 авг 2017 в 19:53

1 ответ 1

1

То, что вы хотите сделать, в общем случае может быть неразрешимо (например, при цикле - если у вас есть, скажем, пары (1,2) (2,3) (3,1) - какая должна быть первой?) или неоднозначно (например, (1,2) (2,3) (2,4)). Неясно, как обрабатывать вариант несвязанных пар - типа (1,2) (3,4) (5,6).

Но в принципе - рассматривая значения пар как вершины некоторого графа, а сами пары - как его ребра - вы получаете задачу топологической сортировки, стандартной реализации в стандартной библиотеке C++ которой не имеется.

Но она достаточно легко реализуется самостоятельно.

3
  • это не топологическая сортировка... Это проще делается. ru.stackoverflow.com/questions/669182/… Вот вроде бы ответ.
    – pavel
    1 сен 2017 в 7:58
  • @pavel Тогда задача как минимум отвратно сформулирована...
    – Harry
    1 сен 2017 в 11:47
  • да мне вообще кажется что как дубликат можно закрыть...
    – pavel
    1 сен 2017 в 11:53

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.