在C ++中找到2D数组的极值点的最佳方法？

I'm looking for a method to find the maximum and minimum values of a 2D integer array in C++. I'm aware of the std::max_element() and std::min_element(), but they only seem to work for one dimensional arrays.

我正在寻找一种方法来在C ++中找到2D整数数组的最大值和最小值。我知道std :: max_element()和std :: min_element(),但它们似乎只适用于一维数组。

The 2D array could be declared and initialized by:

可以通过以下方式声明和初始化2D数组:

int temp[5][5];

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

A simple method could be to do something like:

一个简单的方法可能是这样做:

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

But this doesn't seem very optimized. Is anyone able to give some advice or propose a better idea?

但这似乎没有得到很好的优化。有人能提出一些建议或提出更好的建议吗?

4 个解决方案

#1

You can still use std::min_element and std::max_element like this:

您仍然可以像这样使用std :: min_element和std :: max_element:

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

Live demo

where 4 is the total number of elements.

其中4是元素的总数。

Notice that for readability the above solution uses operator& to get the address to the beginning of the array, but std::addressof is recommended because operator& could be overloaded.

请注意,为了便于阅读,上述解决方案使用operator&将地址输出到数组的开头,但建议使用std :: addressof,因为operator&可能会重载。

If you want you can also declare helper functions for the equivalent bidimensional array begin and end functions:

如果需要,还可以为等效的二维数组开始和结束函数声明辅助函数:

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

I've intentionally avoided the names begin and end because it could generate infinite discussions here.

我故意避免名称开头和结尾,因为它可以在这里产生无限的讨论。

---

Overall, I would recommend defining a matrix type which is implemented as a std::array of M * N elements, and then provide proper begin and end member functions, which can then be used with any standard algorithm.

总的来说,我建议定义一个矩阵类型,它实现为M * N元素的std ::数组,然后提供适当的开始和结束成员函数,然后可以与任何标准算法一起使用。

#2

If there are no other constraints on the contents of your array/matrix, you cannot do better than looking at each element. That means that your solution is actually an optimal solution in terms of asymptotic running time.

如果您的数组/矩阵的内容没有其他限制,那么您不能比查看每个元素做得更好。这意味着您的解决方案实际上是渐近运行时间的最佳解决方案。

I would also argue that it is good in terms of readability, but some might find this easier to read (since it's shorter):

我还认为它在可读性方面很好,但有些人可能会发现这更容易阅读(因为它更短):

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

#3

If you change the type of the array to

如果您将数组的类型更改为

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

and access like

和访问一样

ar[i*n + j]

then you simply write

然后你简单地写

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

#4

Just by changing your structure, you can maybe use iterator

只需更改结构,就可以使用迭代器

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

And use loop like :

并使用循环如:

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