Using algorithms on vectors of vectors

Question

If we define a vector of vectors containing ints, then we fill it with some data, what would be the best way to use, say, the max_element algorithm to find the largest int?

Answer 1

What do you mean by best way? The time complexity is always O(n*m). No big difference between different implementations. A simple implementation like below will be sufficient.

#include <vector>
#include <limits>
using namespace std;

int main()
{
  vector<vector<int> > vec;
  int res = numeric_limits<int>::min();
  for (auto i = vec.begin(); i != vec.end(); ++i) {
    auto t = max_element(i->begin(), i->end());
    if (t != i->end() && *t > res)
      res = *t;
  }

  cout << res << endl;
}

Answer 2

How about collecting the inner vectors' maxima into a separate vector first:

vector<vector<int>> outer = ...;
vector<int> localMaxElements;
for (const auto& inner : outer) {
    localMaxElements.push_back(*max_element(inner.begin(), inner.end()));
}
// your final max element:
return max_element(localMaxElements.begin(), localMaxElements.end());

You could also use max_element on the inner vectors:

auto finalMax = max_element(outer.begin(), outer.end(), 
    [](const vector<int>& a, const vector<int>& b) {
        return max_element(a.begin(), a.end()) < max_element(b.begin(), b.end());
    }
);

But the other way (or the solution proposed by gongzhitaao) will most likely be faster.

Answer 3

// ForEach.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <ctime>

struct  FindMaxOfAll
{
public:
    FindMaxOfAll() : maxOfAll(0) {}
    void operator()(std::vector<int>& cont)
    {
        int max = *(std::max_element(cont.begin(), cont.end()));
        if(max > maxOfAll) { maxOfAll = max; }
    }
    int getMaxOfAll() { return maxOfAll; }
private:
    int maxOfAll;
};

int main()
{
    // fill containers with data
    srand (time(NULL));
    std::vector<std::vector<int> > values2d(5); //create 10 vectors of integers, all empty
    std::for_each(values2d.begin(), values2d.end(),
                  [](std::vector<int>& cont) { cont.resize(5); std::generate ( cont.begin(), cont.end(), rand); });
    std::ostream_iterator<int> out_it (std::cout,", ");
    std::for_each(values2d.begin(), values2d.end(),
                  [&](std::vector<int>& cont) { std::copy ( cont.begin(), cont.end(), out_it ); });

    // Find the max of all
    FindMaxOfAll maxOfAll = std::for_each(values2d.begin(), values2d.end(), FindMaxOfAll());
    std::cout << "\n\nthe max of all is " << maxOfAll.getMaxOfAll() << std::endl;
    return 0;
}

That is my answer. Mine is more verbose but also includes how I initialized the vectors. This is the one thing that I have figured out that for_each can be useful for since it can actually maintain and return the state of the functor which allows you to do something like accumulating information. Is it the best? Who knows? What is best? fastest? Fewest lines of code? easiest to understand? That is very subjective. Since the asker has 99k rep I thought maybe it isn't homework after all. It seems like a fun, quick challenge to see the different ways that people would solve it.