Zliczanie liczb w tablicy

Witam.
Mam problem. Chciałbym zliczyć występowanie liczb w tablicy (nazwijmy ją t1). Niestety tablica jest dość 'rzadka', tzn między elementami mogą wystąpić dość duże przerwy (np. {1,3,1,5,4567,1}). No i mam kilka propozycji jak to zliczyć:

1. Mogę zwyczajnie utworzyć drugą tablicę (t2) o rozmiarze max(t1 + 1), przejść po wszystkich elementach t1 i inkrementować odpowiedni element w t2. Mniej więcej tak:
Wszystko byłoby dobrze, ale max(t1) może być duże (do INT_MAX) - czyli pamięć będzie wyglądać jak ser szwajcarski - duużo dziur (zera) i mało sera (konkretne liczby).

2. Mogę utworzyć mapę w kórej kluczami będą wartości z t1 a wartościami ilość występowań. Minusem będzie fakt, że później te wartości musiałbym posortować (co będzie mi potrzebne w dalszej części programu).

3. Mogę utworzyć listę struktur (z tylko 2 polami: liczba i jej ilość), i następnie przy każdej wartości z t1 szukać danej wartości w liście. Posortowane niby będzie, ale zabójcze obliczeniowo...


Który sposób wybrać? A może jest jakaś klasa, która zlicza elementy w ten sposób (program powstaje przy użyciu Qt5, może tam coś jest)? Zaznaczam, że zależy mi na jak najkrótszym/prostszym kodzie (prostota przede wszystkim :-)).


PS. To oczywiście nie musi być tablica, dane są wczytywane z pliku, obojętne mi do czego.

Ad1. Ze względu na zakres INT_MAX to rozwiązanie odpada (gigabajty pamięci). Da się to przerobić ale znacznie komplikując rozwiązanie. A co więcej, opłacalność komplikacji tego rozwiązania ma sens tylko przy dużych ilościach "liczb z pliku".

Ad2. Jest to najprostsze rozwiązanie!
A z tego co pisze dokumentacja jest ona od razu posortowana (domyślnie niemalejąco), więc wystarczy że weźmiesz sobie iterator do pierwszego elementu i będziesz szedł kolejno. http://www.yolinux.com​/TUTORIALS/CppStlMultiMap.html

Ad3. rozwiązanie w jakiś sposób podobne do mapy, jednak:
- wcale nie będzie "zabójcze obliczeniowo" - złożoność to tylko n*logn (nie wliczając przechodzenie po poszczególnych elementach listy).
- jak dobrze to zakodzisz to mapa będzie wolniejsza
- ale jak potrzebujesz krótki prosty kod to nie ma sensu tego robić

Ad3. Myślałem, że będzie n*n, ale dopiero po Twojej odpowiedzi sobie uświadomiłem, że można to bez problemu do n*logn przerobić.

Ad2. Człowiek uczy się przez całe życie... Jakby się nad tym zastanowić, to właściwie jest oczywiste, że elementy są tam posortowane (w końcu to pochodna drzewa binarnego). Ale sam bym na to w życiu nie wpadł.

Ad1. A o pamięci nie pomyślałem :-). No ale nawet jeżeli by jej wystarczyło, to: "why hold space for thousands of elements when all we have is five". :-)


Wielkie dzięki za pomoc, jutro spróbuję pobawić się z mapą. A jak coś nie będzie działać, to jeszcze dam znać. :-)

EDIT: Mapa działa dokładnie tak jak chciałem, jeszcze raz dzięki za pomoc.