c++ - 如何找到数组组的最大值

Question

我有六个 float 类型的数组。所有这些数组中的任何特定索引都代表我的一组值。例如如果索引为 0，则所有六个数组的 0 索引代表一组值，我需要从中找到最大值。同样，对于所有其他索引也是如此。

array1  array2  array3  array4  array5  array6    
0       0       0       0       0       0 
1       1       1       1       1       1

等等。

我需要找出所有这些数组中特定索引的最大值，并将其存储在另一个数组或列表中。

Answer 1

接受在标准 c++ 中执行此操作的挑战，这里什么也做不了。

我已尝试尽可能通用地实现算法 reduce_minelement(不假设任何特定的容器类型或值数组的数量等)。

我提供了几个版本，从标准的 c++98 代码开始(它有一些问题，主要是为了将数据初始化到 STL 容器中)。

普通标准 C++98

现场观看:http://ideone.com/2BlsK

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

template <typename Containers>
    std::vector<typename Containers::value_type::value_type> 
        reduce_minelement(const Containers& containers)
{
    typedef typename Containers::value_type slice_t;
    typedef typename Containers::const_iterator slice_ci;
    typedef typename slice_t::value_type element_t;
    std::vector<element_t> result;
    result.reserve(containers.size()); // pre-allocated

    for (slice_ci it=containers.begin(); it!=containers.end(); ++it)
    {
        result.push_back(*std::max_element(it->begin(), it->end()));
    }

    return result;
}

typedef int ints_t[6];
static const ints_t s_data[] = { 
    { 19152,     1, 21193, 17574,  8484, 30333 },
    { 20189, 18837, 30734,     2, 22440,  3534 },
        { 3, 26118, 19367, 17877, 24605,  7838 },
    { 30885, 20135,    -4, 31316, 11838,  8926 },
    { 26830, 20209, 27286, 16105, 16601, 28304 },
    { 10208, 28062, 15612, 26270, 19234, 21326 },
     { 5208, 17473,  3383, 15659, 32494, 24231 },
    { 31685, 22500, 18860, 21318, 18893, 21385 },
    { 14295, 17163,  8920, 15986, 13448, 21143 },
    { 20199,  8954,   599, 17459,  3884,  8634 },
    { 16768, 20563,  6727, 26305, 11053,  6418 },
     { 7446,  6853,  5283,  6193, 28291,  4205 },
    { 27056, 17514,  5359, 29656, 10910,  6034 },
    { 21984,  1261,  2404, 17644, 25969,  1735 },
      { 797,  8457, 23584, 29363, 26362, 17383 },
      { 768, 11018, 14991,     0, 28720,  6159 },
};

int main()
{
    std::vector<std::vector<int> > data;

    for (const ints_t *it=s_data; it!=s_data+(sizeof(s_data)/sizeof(*s_data)); ++it)
        data.push_back(std::vector<int>(*it+0, *it+sizeof(*it)/sizeof(**it)));

    std::vector<int> reduced = reduce_minelement(data);

    std::copy(reduced.begin(), reduced.end(), std::ostream_iterator<int>(std::cout, ", "));

    return 0;
}

普通标准 C++11

编译时支持 c++0x。好处是

• 大大改进了初始化
• 更灵活(现在可以是锯齿状数组，查看演示数据)
• 易读性(基于范围的 for 而不是迭代器循环)，auto 类型推导
• 更少的 typedef 将事物联系在一起

注意 不幸的是，由于codepad.org/ideone.com 使用gcc 4.5.1 编译器，因此尚不支持基于范围的for；实时查看稍作修改的版本:http://ideone.com/xevL0

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

template <typename Containers>
    std::vector<typename Containers::value_type::value_type>
         reduce_minelement(const Containers& containers)
{
    std::vector<typename Containers::value_type::value_type> result;
    result.reserve(containers.size()); // pre-allocate

    for (auto& slice: containers)
        result.push_back(*std::max_element(slice.begin(), slice.end()));

    return result;
}

static const std::vector<std::vector<int> > data = { 
       { 52,    1, 93, 74 },
        { 2,   18, 67, 77 },
       { 85,   35, -4     },
       { 48 },
       { 68,   18, 91,  0 },
};

int main()
{
    auto reduced = reduce_minelement(data);
    std::copy(reduced.begin(), reduced.end(), std::ostream_iterator<int>(std::cout, ", "));

    return 0;
}

具有提升范围的 C++0x

• 更简洁的代码
• 允许直接在非 STL 容器(如 C 风格数组)上操作。 这导致 reduce_minelement 中的类型推导稍微复杂一些。抽象是有代价的；)

注意 数据(s_data)被省略，因为它与上面相同；您可以放入其他示例中的任一 s_data 定义，它会编译并运行。

注意 没有在线编译器服务支持 Boost 库 header ，因此您只能在家里看到这个现场。

#include <vector>
#include <boost/range.hpp>
#include <boost/range/algorithm.hpp>
#include <iterator>

using boost::range_value;
using boost::range_iterator;

template <typename Containers>
    std::vector<typename range_value<typename range_value<Containers>::type>::type> 
         reduce_minelement(const Containers& containers)
{
    std::vector<typename range_value<typename range_value<Containers>::type>::type> result;
    result.reserve(boost::size(containers)); // pre-allocate

    for (auto& slice: containers)
        result.push_back(*boost::max_element(slice));

    return result;
}

typedef int ints_t[6];
static const ints_t s_data[] = { 
    { 19152,     1, 21193, 17574,  8484, 30333 },
    { 20189, 18837, 30734,     2, 22440,  3534 },
        { 3, 26118, 19367, 17877, 24605,  7838 },
    { 30885, 20135,    -4, 31316, 11838,  8926 },
    { 26830, 20209, 27286, 16105, 16601, 28304 },
    { 10208, 28062, 15612, 26270, 19234, 21326 },
     { 5208, 17473,  3383, 15659, 32494, 24231 },
    { 31685, 22500, 18860, 21318, 18893, 21385 },
    { 14295, 17163,  8920, 15986, 13448, 21143 },
    { 20199,  8954,   599, 17459,  3884,  8634 },
    { 16768, 20563,  6727, 26305, 11053,  6418 },
     { 7446,  6853,  5283,  6193, 28291,  4205 },
    { 27056, 17514,  5359, 29656, 10910,  6034 },
    { 21984,  1261,  2404, 17644, 25969,  1735 },
      { 797,  8457, 23584, 29363, 26362, 17383 },
      { 768, 11018, 14991,     0, 28720,  6159 },
};

int main()
{
    boost::copy(reduce_minelement(s_data), std::ostream_iterator<int>(std::cout, ", "));

    return 0;
}

---

通用性:字符串呢？

所有三个版本对于元素类型都是完全通用的。其他一些地方可能需要调整(比如 ostream_iterator 类型)但实际实现并不介意你是否抛出 floats，std::strings、整数 或者实际上是任何类似的类型。

Demo，基于上一个版本:

typedef std::string elements_t[3];
static const elements_t s_data[] = { 
    { "the", "quick", "fox" },
    { "jumped", "over", "the" },
    { "lazy", "blue", "moon" },
};

int main()
{
    boost::copy(reduce_minelement(s_data), 
       std::ostream_iterator<std::string>(std::cout, ", "));

    return 0;
}

输出:

the, the, moon,

Q.E.D.

希望这对您来说很有趣。这是给我的。