Il metodo migliore per trovare i punti estremi di un array 2D in C++?

Question

Sto cercando un metodo per trovare i valori massimi e minimi di un array intero 2D in C++. Sono a conoscenza dello std::max_element() e dello std::min_element(), ma sembrano funzionare solo per array monodimensionali.

La matrice 2D potrebbe essere dichiarato e inizializzato da:

int temp[5][5]; 

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

Un metodo semplice potrebbe essere quella di fare qualcosa di simile:

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]; 
     } 
    } 
} 

Ma questo non sembra molto ottimizzato. Qualcuno è in grado di dare qualche consiglio o proporre un'idea migliore?

Answer 1

È comunque possibile utilizzare std::min_element e std::max_element in questo modo:

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

Live demo

dove 4 è il numero totale di elementi.

Si noti che per migliorare la leggibilità la soluzione di cui sopra utilizza operator& per ottenere l'indirizzo per l'inizio della matrice, ma std::addressof è raccomandato perché operator& potrebbe essere sovraccarico.

Se si vuole si può anche dichiarare funzioni di supporto per l'array bidimensionale equivalente begin e end funzioni:

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

Ho intenzionalmente evitato i nomi begin e end perché potrebbe genera discussioni infinite qui.

---

complesso, consiglio definisce un tipo matrix che è implementato come un std::array di M * N elementi, e quindi fornire funzioni proprie begin e end utente, che possono poi essere utilizzati con qualsiasi algoritmo standard.

Answer 2

Se non ci sono altri vincoli sul contenuto della matrice/matrice, non si può fare di meglio che guardare ciascun elemento. Ciò significa che la soluzione è in realtà una soluzione ottimale in termini di tempo di esecuzione asintotico.

Vorrei anche sostenere che è buono in termini di leggibilità, ma alcuni potrebbero trovare questo più facile da leggere (dal momento che è più corto):

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

Se si cambia il tipo di matrice per

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

e l'accesso come

ar[i*n + j] 

allora è sufficiente scrivere

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

Answer 4

Solo cambiando la struttura, si può forse utilizzare iteratore

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() 
} 

E l'uso ciclo come:

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