Najlepsza metoda wyszukiwania punktów extrema w tablicy 2D w C++?

Question

Poszukuję metody znalezienia maksymalnej i minimalnej wartości dwuwymiarowej tablicy 2D w C++. Jestem świadomy std::max_element() i std::min_element(), ale wydaje się, że działają tylko w jednowymiarowych tablicach.

Tablica 2D mogą być zadeklarowane i inicjowany przez:

int temp[5][5]; 

for(int x = 0; x < 5; x++) 
{ 
    for(int y = 0; y < 5; y++) 
    { 
     temp[x][y] = some_random_number; 
    } 
} 

prosta metoda może być coś jak:

int min = high_number; 
int max = low_number; 

for(int x = 0; x < 5; x++) 
{ 
    for(int y = 0; y < 5; y++) 
    { 
     if(temp[x][y] < min) 
     { 
      min = temp[x][y]; 
     } 
     if(temp[x][y] > max) 
     { 
      max = temp[x][y]; 
     } 
    } 
} 

Ale to nie wydaje się bardzo zoptymalizowany. Czy ktoś może udzielić porady lub zaproponować lepszy pomysł?

Answer 1

Można nadal używać std::min_element i std::max_element takiego:

int arr[2][2] = {{434, 43}, {9826, 2}}; 
auto pair = std::minmax_element(&arr[0][0], &arr[0][0] + 4); 

Live demo

gdzie jest 4 całkowita liczba elementów.

Należy zauważyć, że dla czytelności powyższe rozwiązanie używa operator&, aby uzyskać adres na początku tablicy, ale zaleca się std::addressof, ponieważ operator& może być przeciążone.

Jeśli chcesz, możesz też zadeklarować funkcje pomocnicze dla równoważnego dwuwymiarowego tablicy begin i end funkcje:

template<typename T, std::size_t N, std::size_t M> 
auto bi_begin(T (&arr)[N][M]) { 
    return std::addressof(arr[0][0]); 
} 

template<typename T, std::size_t N, std::size_t M> 
auto bi_end(T (&arr)[N][M]) { 
    return bi_begin(arr) + N * M; 
} 

Live demo

ja celowo unika nazwy begin i end ponieważ może generować nieskończone dyskusje tutaj.

---

Ogólnie polecam definiowania matrix typ, który jest zaimplementowany jako std::array z M * N elementów, a następnie dostarczyć odpowiednie funkcje begin i end członkowskich, które następnie mogą być używane z każdego standardowego algorytmu.

Answer 2

Jeśli nie ma żadnych innych ograniczeń dotyczących zawartości macierzy/macierzy, nie można zrobić nic lepszego niż patrzenie na każdy element. Oznacza to, że twoje rozwiązanie jest właściwie optymalnym rozwiązaniem pod względem asymptotycznego czasu działania.

Chciałbym również twierdzą, że jest dobry pod względem czytelności, ale niektórzy mogą znaleźć to łatwiejsze do odczytania (ponieważ jest krótsza):

for(int x = 0; x < 5; x++) 
{ 
    for(int y = 0; y < 5; y++) 
    { 
     min = std::min(temp[x][y], min); 
     max = std::max(temp[x][y], max); 
    } 
} 

Answer 3

Jeśli zmienić typ matrycy do

constexpr int n = 5; 
constexpr int m = 7; 
std::array<int,n*m> ar; 

i dostęp jak

ar[i*n + j] 

to po prostu napisać

auto min = std::min_element(ar.begin(), ar.end()); 
auto max = std::max_element(ar.begin(), ar.end()); 

Answer 4

Tylko zmieniając strukturę, można być może użyj iteratora

int main() 
{ 
    int c_array[5] = {}; 
    std::array<int, 5> cpp_array = {}; 
    std::vector<int> cpp_dynarray(5); 

    auto c_array_begin = std::begin(c_array); // = c_array + 0 
    auto c_array_end = std::end(c_array);  // = c_array + 5 

    auto cpp_array_begin = std::begin(cpp_array); // = cpp_array.begin() 
    auto cpp_array_end = std::end(cpp_array);  // = cpp_array.end() 

    auto cpp_dynarray_begin = std::begin(cpp_dynarray); // = cpp_dynarray.begin() 
    auto cpp_dynarray_end = std::end(cpp_dynarray);  // = cpp_dynarray.end() 
} 

i wykorzystanie pętli jak:

mypointer = arr; 
for(auto it = arr.begin(); it != arr.end(); ++it) { 
     min = std::min(*mypointer, min) 
     max = std::max(*mypointer, max) 
}