Mapa <int, struct>

Witam

Zastanowiło mnie ostatnio jak zrobić w C# mapę zawierającą nie unikalny int i strukturę, z takim zastrzeżeniem, że mapa miałaby być tablicą lub jakimś zbiorem elementów. Wszystkie drogi doprowadzają mnie do Dictionary, IDictionary lub KeyValuePair niestety rozwiązania te nie bardzo pasują mi w formach jakie występują ze względu na powyższe wymogi.
Dane mają wyglądać mniej więcej tak:
1, "aaa", "bbb", 11
1, "vv", "dd",43
4, "rr", "ee",32

chciałbym mieć możliwość posortowania po pierwszym parametrze liczbowym.

No jeśli nieunikalny, to raczej nie mapa. Jeśli ten int nie może być częścią tej struktury, to po prostu opakuj te dwie rzeczy w inny typ i wrzuć do listy. A posortuj używając LINQ.