Sortowanie i maksymalna wielkość tablicy ?

pytanie zadane 26 grudnia 2015 w C i C++ przez Kabiszon Użytkownik (890 p.)

Witam !

Mam do was dwa szybkie pytanka :)

1) Chciałbym posortować takie cudo pair <pair <int, int>, int> pary[1000005]; , ale problem tkwi w tym, że chciałbym aby tylko ta wewnętrzna para została posortowana a ten drugi element z zewnętrznej pary nie miał wpływu na sortowanie. Trochę rozjaśniając to mam kilka punktów na układzie współrzędnych i pary.first.first = x, pary.first.second = y a pary.second to numer tego punktu i teraz chcę posortować po x.

2) Jaki jest dokładny maksymalny rozmiar tablicy jednowymiarowej typu int w c++ ?

Z góry dzięki za odpowiedź :)

2 odpowiedzi

odpowiedź 26 grudnia 2015 przez adrian17 Ekspert (344,860 p.)
wybrane 26 grudnia 2015 przez Kabiszon

Najlepsza

1. Przekaż do std::sort dodatkową funkcję która będzie mu mówiła, według czego sortować. Powiedz jeśli chcesz konkretny przykład.

2. Teoretycznie maksymalna liczba elementów jest równa maksymalnej wartości typu size_t (std::numeric_limits<std::size_t>::max()). Konkretniej sizeof() dowolnego obiektu musi być wielkością typu size_t, więc dla typu int teoretyczny maksymalny rozmiar tablicy wynosi max_size_t / sizeof(int) elementów.

W praktyce wszystko zależy od implementacji, która może nie skompilować programu który próbuje alokować zbyt dużą tablicę, oraz środowiska (systemu, maszyny) która zazwyczaj nie pozwoli zaalokować więcej miejsca niż jest dostępne (w RAMie+pamięć wirtualna jeśli alokujesz na stercie, na stosie jeśli alokujesz na stosie. Stos zazwyczaj nie przekracza kilku megabajtów.)

komentarz 26 grudnia 2015 przez Kabiszon Użytkownik (890 p.)

Bardzo bym poprosił o konkretny przykład :)

komentarz 26 grudnia 2015 przez adrian17 Ekspert (344,860 p.)

// aliasy typow dla czytelnosci
typedef pair<int, int> XY;
typedef pair<XY, int> Para;

bool porownaj_pary(const Para &lhs, const Para &rhs){
    return lhs.first.first < rhs.first.first;
}

int main()
{
    Para pary[10005];
    sort(begin(pary), end(pary), porownaj_pary);

    // albo z lambda zamiast osobnej funkcji:

    sort(begin(pary), end(pary),
    	[](const Para &lhs, const Para &rhs){
    		return lhs.first.first < rhs.first.first;
    	}
    );
}