Exagon Exagon - 3 months ago 11
C++ Question

Algorithm for finding most present value in containers

I have the following problem I have a vector of

std::set
's now I want to compute the element, which is in the most of the sets.
For example:
If the sets are {1,2,3,4}, {2,4,5} and {2,7,8} i want the algorithm to output 2, because 2 is in 3 sets and every other element isnt.
My current attempt in solving this uses a map, which maps a counter tovevery value in the sets and then iterates over all the sets.
I am sure I need to iterate over all the sets, but can I solve this using some algorithms in the
<algorithm>
header?

Ven Ven
Answer

A solution using for_each:

std::set<std::set<std::string>> sets {s1,s2,s3,s4}; // incurs a copy on each set
std::unordered_map<std::string, int> all;
std::for_each(sets.begin(), sets.end(), [&all](const std::set<std::string> &s) { // outer loop: each set in sets
    std::for_each(s.cbegin(), s.cend(), [&all](const std::string &string) { // nested loop
         all[string]++;
    });
});
for (const auto &p : all)
    std::cout << p.first << " = " << p.second << "\n";

See it live on Coliru!

Another solution using a single vector and accumulate:

std::set<std::string> s1 {"a", "b", "c"};
std::set<std::string> s2 {"a", "x", "d"};
std::set<std::string> s3 {"a", "y", "d"};
std::set<std::string> s4 {"a", "z", "c"};
std::vector<std::string> vec;
// flatten sets into the vector.
vec.insert(vec.begin(), s1.begin(), s1.end());
vec.insert(vec.begin(), s2.begin(), s2.end());
vec.insert(vec.begin(), s3.begin(), s3.end());
vec.insert(vec.begin(), s4.begin(), s4.end());
for (const auto &p : std::accumulate(vec.begin(), vec.end(), std::unordered_map<std::string, int>{}, [](auto& c, std::string s) { c[s]++; return c; })) // accumulate the vector into a map
    std::cout << p.first << " = " << p.second << "\n";

See it live on Coliru!

If the cost of the copy is too big a burden, you can instead use a partially-applied function on each of the std::sets:

std::set<std::string> s1 {"a", "b", "c"};
std::set<std::string> s2 {"a", "x", "d"};
std::set<std::string> s3 {"a", "y", "d"};
std::set<std::string> s4 {"a", "z", "c"};
std::unordered_map<std::string, int> all;
auto count = [&all](const auto& set) { std::for_each(set.begin(), set.end(), [&all](std::string s) { all[s]++; }); };
count(s1); // apply a for_each on each set manually.
count(s2);
count(s3);
count(s4);
for (const auto &p : all)
    std::cout << p.first << " = " << p.second << "\n";

See it live on Coliru!