Map: Group Tuple keys Together with Empty Elements

Question

Introduction

We have std::map<key,std::vector<std::string>> m; where the key is represented by std::tuple<std::string, std::string,std::string>. But there is a constraint, the last field of the tuple can be an empty string. If the last element of the tuple is an empty string then we should merge it with the with elements of the map having same first and second elements.

Input:
o1("1","1","1") 
o2("1","1","1")
o3("1","1","1")
o4("2","2","2")
o5("2","2","2") 
o6("2","2","")
o7("2","2","")

Output:
Key: 1 1 1 ==> size: 3
Key: 2 2 2 ==> size: 4

Indeed, (1,1,1) are grouped together and (2,2,2), (2,2,"") are grouped together. I have to do the merge in 2 steps and I have to use 2 maps to do that.

Is there a way to improve how I merge the keys together?

---

#include <iostream>
#include <tuple>
#include <map>
#include <vector>
#include <algorithm>
            
using key = std::tuple<std::string, std::string,std::string>;
        
/* Object we want to merge */
struct Object {
    Object(const std::string& x, const std::string& y, const std::string& z ):_x(x),_y(y),_z(z){}
    std::string _x;
    std::string _y;
    std::string _z;
    /* This object has more data members */
};
        
std::map<key,std::vector<Object>> mergeObjects(const std::vector<Object> &v) {
   /* Holds the objects without empty elements */
   std::map<key,std::vector<Object>> m;
   /* Holds the objects with last empty element */
   std::map<key,std::vector<Object>> m1;
   
   /* Step 1: Fill maps m and m1 based on whether z is empty or not*/      
   for(const auto &o:v) {
       /* if "z" is empty then put "o" in m1 else in m */
       if(o._z.empty()) {
            m1[std::make_tuple(o._x, o._y, o._z)].push_back(o);
        } else {
            m[std::make_tuple(o._x, o._y, o._z)].push_back(o); 
        }
    }
    
    /* Step 2: Merge elements. Find elements of m1 in m that have the same first and second elements */
    for(const auto& [k,v]: m1){
        auto[x, y, z] = k;
        /* Find first occurrence of k in m */
        auto it = std::find_if(m.begin(), m.end(),[&](const std::pair<key, std::vector<Object>>& k1){
            auto[x1, y1, z1] = k1.first;
            return (x == x1 and y == y1);
        });
        /* If key found then merge and concatenate vectors*/
        if(it != m.end()) {
            it->second.insert(it->second.end(),v.begin(), v.end());
        }
   }
   return m;
}
        
int main() {
   /* What we receice as input */
   Object o1("1","1","1"), o2("1","1","1"), o3("1","1","1"), o4("2","2","2"), o5("2","2","2"), o6("2","2",""),o7("2","2","");
   std::vector<Object> v = {o1, o2, o3, o4, o5, o6, o7};
    
   /* Merge Objects together if applicable */
   std::map<key,std::vector<Object>> m =  mergeObjects(v);
   
   /* Print Merged Objects */
   for(const auto&[k,v]: m){
        std::cout << "Key: " << std::get<0>(k) <<" " << std::get<1>(k) <<" "<<std::get<2>(k) <<" ===> Size: "<< v.size() << std::endl;
    }
    return 0;
}

Answer 1

The problem is not well-defined

Your explaination and the code make it look like this is a well-defined problem, but it actually raises some questions. Consider this input:

o1("1", "1", "");
o2("2", "2", "2");
o3("2", "2", "3");
o4("2", "2", "");
o5("2", "2", "");
o6("2", "", "");
o7("2", "", "2");

What should happen with o1? Should it appear in the merged objects or not? What of o4 and o5, should they both be merged with o2, both with o3, or should they be distributed over o2 and o3? And is only the last tuple element special when it is empty, or is the middle one being empty also something to consider?

The answers to these questions will influence the algorithm you should use to merge the items.

Merging using a single pass

It is possible to merge the elements using a single pass. While looping over the vector of Objects, consider the order in which we see items with the last tuple item being empty or non-empty. If we see elements with the last item non-empty, then you can just add it to m. If an element follows with the last item non-empty, but we already have an element in m which matches the first two items of the tuple, then we can just append it there. The problem of course is when you start with an element with the last tuple element empty. A possible solution is to add it to m anyway. The moment we encounter an element with the same first two elements and the third one non-empty, we can merge them (which involves deleting the item with an empty last tuple element from m).

However, a single-pass algorithm is not necessarily more efficient or more elegant than a two-pass algorithm, so I wouldn't automatically consider your approach bad.

Improving efficiency

I would rather focus on making the algorithm more efficient. The first pass is rather straight-forward. The only thing to improve here is that you don't need m1 to be an ordered map, instead you can in principle use a std::unordered_map, however since std::hash is not overloaded for std::tuple, that will not compile unless you add your own hash function.

The second pass can be greatly improved. The problem is that std::find_if() is doing a linear search, and since you have to do that for every element in m1, this has complexity \$\mathcal{O}(N^2)\$. But we can be smarter than that, since a std::map is ordered, and supports lookups in \$\mathcal{O}(\log N)\$ time. You can do that with lower_bound():

for (const auto& [k,v]: m1) {
    if (auto it = m.lower_bound(k); it != m.end()) {
        auto [x, y, z] = k;
        auto [x1, y1, z1] = it->first;
        if (x == x1 and y == y1) {
            it->second.insert(it->second.end(), v.begin(), v.end());
        }
    }
}

While that improves the time complexity of your algorithm, another issue is that you are copying objects, instead you can move them using move iterators.

Unnecessary use of tuples

Using tuples is sometimes handy, but you already have a nice type holding three strings: Object. Why not declare your maps like so?

std::map<Object, std::vector<Object>> m;

Now you can get rid of std::make_tuple, structured bindings still work, and instead of std::get<0>(k) you can just write k._x. The only issue is that your Object doesn't have a comparison operator. You will have to add one yourself so that std::map knows how to order your Objects. In C++20 this is very easy, just add:

friend auto operator<=>(const Object& lhs, const Object& rhs) = default;

Consider changing the data structure

Some of the issues you have merging the elements come from the decision to store things in a std::map<key, std::vector<Object>>. If it is possible to change this data structure, you have some opportunities to make the merging even faster, and at the same time use less memory. The idea is that instead of a single map, you have an outer map of tuples of two strings, and inside you have a map of a string to an integer:

std::map<std::tuple<std::string, std::string>, std::map<std::string, std::size_t>> m;

Then adding the input into that data structure becomes:

for (const auto &o: v) {
    m[{o._x, o._y}][o._z]++;
}

Maybe this is already good enough; for a given key k with three non-zero elements you can write:

auto size = m[{k._x, k._y}][k._z] + m[{k._x, k._y}][{}];
std::cout << "Key: " << k._x << " " << k._y << " " << k._z << " size: " << size << '\n';

But if you want to merge them, you can simply loop over the elements of the outer map and check if the inner map has an element with an empty string, and then move its count to that of (one of the other) element(s) with a non-empty string:

for (auto& [k, v]: m) {
    if (auto it1 = k.find({}); it1 != k.end()) {
        if (auto it2 = k.upper_bound({}); it2 != k.end()) {
            *it2 += *it1;
            k.erase(it1);
        }
    }
}