Specyficzne sortowanie – elementy o tym samym kluczu obok siebie

0

Witajcie
Mam taki problem do rozwiązania. Chcę "posortować", a właściwie ustawić dane w postaci par<int, int> obok siebie. Najprosciej będzie pokazać na przykładzie jaki jest cel.

DANE:
1 22
1 3
1 4
22 5
4 6
22 7
7 8
6 9
7 10

Lista wynikowa:
1 22
1 3
1 4
22 5
22 7
4 6
7 8
7 10
6 9

Czyli zależy mi na tym, aby obok (a własciwie za) pierwszego napotkanego elementu ustawic wszystkie, których pierwsza składowa jest taka sama.
Zwykłe cpp std::sort czy cpp list::sort z comparatorem lhs == rhs zmienia kolejnosc danych ( jest niestabilne), a stable sort dla listy par nie działa.
Jakies ciekawe sugestie, propozycje jak to zrobic?

0

Przecież std::sort powinien mieć napisany comparator, gdzie jeden element jest mniejszy od drugiego.

return std::tie(lhs.first, lhs.second) < 
std::tie(rhs.first, rhs.second)

https://ideone.com/1hjxF0

0

Może powiem do czego mi w ogóle to jest potrzebne, bo widzę, że nie bardzo możemy się zrozumieć.
Robię dodawanie elementów o danej wartosci do drzewa. Pierwsza liczba z pary oznacza ojca, druga syna (para to połączenie między ojcem a synem).

1 2
1 3
1 4
3 5
4 6
2 7
7 8
6 9
5 10
10 12
9 13
8 11

to kolejne połączenia w drzewie. Korzeń to zawsze 1. Ma synów 2, 3, 4 . 3 ma syna 5, 4 ma syna 6, 2 ma syna 7, 7 ma syna 8, 6 ma syna 9, 5 ma syna 10 10 ma syna 12, 9 ma syna 13, a 8 ma syna 11 .

Chcę żeby dla kazdego ojca dzieci były obok siebie, tak żebym nie musiał juz zapamietywac ojca, przechodzac do jego brata

0

To nie ma żadnego związku z sortowaniem, no chyba że nie przeszkodzi Tobie zamiana

22 4
1 3
22 3

na

1 3
22 4
22 3
0

To może trzymaj to w vector<pair<int, set<int>>.
Przeszukuje drzewo i szukasz w vectorze wartości. Jeśli jest dodajesz następny element do seta, a jeśli nie ma to dodajesz następny element do vector.

0

takie struktury pomoga rozwiazac problem (linowo):

vector<vector<pair_wzglednie_inny_obiekt_z_danymi>>
unordered_map<int, int>

?

0

Wciąż nie wiem jak ustawić elementy o tym samym kluczu obok siebie, nie zmieniajac im kolejnosci wejsciowej, ale widzę, że nawet jesli to jakos zrobie, to nie rozwiąże to mojego problemu.
Może ktoś wie jak uzyskac inny efekt, a mianowicie dla ponizszych danych, mam sekwencje z jedynką pierwszą, i jakąś drugą liczbą. Nastepne sekwencje to mają pierwszą liczbę taką, jaka wystąpiła w poprzednich jako druga, tylko nie zawsze są dane w tej samej kolejności, jak poprzednie (pokażę na przykładzie)

1 2
1 3
1 4

3 6
2 5 // Tu zła kolejnosc, chcę posortować tak, aby było 2 5, 3 6, 4 7
4 7

5 8
5 9
5 10
//gdyby pojawilo sie 6 x to chcialbym aby bylo przed 5 x, bo 6 wystapilo wczesniej niz 5

0
piotreekk napisał(a):

Korzeń to zawsze 1. Ma synów 2, 3, 4 . 3 ma syna 5, 4 ma syna 6, 2 ma syna 7, 7 ma syna 8, 6 ma syna 9, 5 ma syna 10 10 ma syna 12, 9 ma syna 13, a 8 ma syna 11 .

Chcę żeby dla kazdego ojca dzieci były obok siebie, tak żebym nie musiał juz zapamietywac ojca, przechodzac do jego brata

Przede wszystkim to zastanów się jakie dane będzie zawierać to drzewo i w jaki sposób będziesz te dane przetwarzał.
Bo może się okazać, że zapamiętywanie indeksu rodzica będzie o wiele wydajniejsze niż to układanie które próbujesz osiągnąć.

0

Problem jest taki, że ja implementuję własne drzewo, które tworzy się na podstawie ścieżek, jakie dostaję na wejsciu. Także na przykład dla takich danych

13 

1 2
1 3
1 4
4 6
2 7
3 5
7 8
5 10
6 9
10 12
8 11
9 13

Ma mi się utworzyc drzewo 13 elementowe. 1sza liczba w parze odpowiada ojcu, druga jego potomkowi. 1szy element o numerze 1 root jest domyslny i zawsze ma numer 1. Reszta tworzy sie na podstawie danych. Do tworzenia drzewa używam kolejki (odkładam tam dzieci).

1

Jeśli dobrze rozumiem to kolejność elementów wyniku, zależy od kolejności elementów danych wejściowych.
W takim wypadku nie jest to sortowanie. Przynajmniej nie jest to zwykłe sortowanie, bo porządek wyznaczają dane wejściowe.

Wniosek jest prosty, algorytm musi mieć dwa kroki.
Pierwszy ustalanie porządku.
Drugi sortowanie na podstawie ustalonego porządku.

std::vector<std::pair<int, int>> data;

std::unordered_map<int, size_t> order;
for(auto x : data) {
     if (order.count(x.first) == 0) {
           order.insert({ x.first, order.size() });
     }
}

std::stable_sort(data.begin(), data.end(),
    [order](auto a, auto b)
    {
        return order.at(a.first) < order.at(b.first);
    });

1 użytkowników online, w tym zalogowanych: 0, gości: 1