How to implement an iterator for a two leveled map in C++?

Question

Consider we have a map std::map<Level1Key, std::map<Level2Key, T>>, and we will consider some operations on T here.

We will have using TwoLevelMap = std::map<Level1Key, std::map<Level2Key, T>>; here, for simplicity.

Also, this is a simplified version of my real problem, in which I can't use (level1, level2) as key. So we will only discuss in the "two-level" map context.

---

The first case is find. If we can't find (level1, level2), we have some output something like map.end(). However, I really understand that we can't have an universal representation like std::string::npos here, so there comes the first trouble.

Should I use std::map<Level2Key, T>::end()? However, it is not plausible, because we don't know which end it should compare to. For example, it have to be like the following, which is quite ugly, since we have to access m.at(level1key) first! Such operation will throw!

if (m.find(level1key, level2key) == m.at(level1key).end()) {
}

---

The second case is erase by an iterator. Consider the following case, hoe can we implement magicErase, if we only knows level2_iter?

m.magicErase(level2_iter);

So we can only do this, which always requires to search the map(costy).

m.magicErase(level1_key, level2_key);

To my intuition, could there be something like TwoLevelIter for this?

struct TwoLevelIter {
    Level1Iter iter1;
    Level2Iter iter2;
};

Then we have to write a special magicErase like

void magicErase() {
    iter->level1.erase(iter->level2);
}

---

So, I want to know what is the best practice to solve my problem here?

Answer 1

You could wrap your nested map up into a class with a custom iterator. For example:

#include <iostream>
#include <map>
#include <string>

template <typename Level1Key, typename Level2Key, typename T>
class TwoLevelMap
{
public:
  using Level2Map = std::map<Level2Key, T>;
  using Level1Map = std::map<Level1Key, Level2Map>;

  class iterator
  {
  public:
    Level1Map* map = nullptr;
    typename Level1Map::iterator first;
    typename Level2Map::iterator second;
    using value_type = std::pair<Level1Key, std::pair<Level2Key, T>>;

    auto operator<=>(const iterator&) const = default;

    iterator& operator++()
    {
      second++;
      if (second == first->second.end())
      {
        first++;
        if (first == map->end())
        {
          second = {};
        }
        else
        {
          second = first->second.begin();
        }
      }
      return *this;
    }

    iterator operator++(int)
    {
      iterator old = *this;
      operator++();
      return old;
    }

    iterator& operator--()
    {
      if (first == map->end() || second == first->second.begin())
      {
        if (first == map->begin())
        {
          throw std::logic_error("invalid iterator");
        }
        first--;
        second = first->second.end();
      }
      second--;
      return *this;
    }

    iterator operator--(int)
    {
      iterator old = *this;
      operator--();
      return old;
    }

    value_type operator*()
    {
      return { first->first, { second->first, second->second } };
    }
  };

  iterator insert_or_assign(const Level1Key& level1, const Level2Key& level2, const T& value)
  {
    auto it = map.find(level1);
    if (it == map.end())
    {
      it = map.insert({ level1, {{level2, value}} }).first;
      return { &map,  it, it->second.begin() };
    }
    else
    {
      return { &map,  it, it->second.insert_or_assign(level2, value).first };
    }
  }

  iterator find(const Level1Key& level1, const Level2Key& level2)
  {
    auto first = map.find(level1);
    if (first == map.end())
    {
      return end();
    }
    auto second = first->second.find(level2);
    if (second == first->second.end())
    {
      return end();
    }
    return { &map, first, second };
  }

  iterator erase(iterator pos)
  {
    auto second = pos.first->second.erase(pos.second);
    if (pos.first->second.empty())
    {
      auto first = map.erase(pos.first);
      return { &map, first, first == map.end() ? typename Level2Map::iterator() : first->second.begin() };
    }
    else
    {
      return { &map, pos.first, second };
    }
  }

  iterator begin()
  {
    return { &map, map.begin(), {map.empty() ? typename Level2Map::iterator() : map.begin()->second.begin() } };
  }

  iterator end()
  {
    return { &map, map.end(), typename Level2Map::iterator() };
  }

private:
  Level1Map map;
};

int main() {
  TwoLevelMap<std::string, std::string, int> map;
  map.insert_or_assign("a", "b", 1);
  map.insert_or_assign("a", "c", 2);
  map.insert_or_assign("a", "d", 3);
  map.insert_or_assign("b", "a", 4);
  std::cout << "forward\n";
  for (auto value : map)
  {
    std::cout << value.first << ", " << value.second.first << ", " << value.second.second << "\n";
  }
  std::cout << "reverse\n";
  for (auto it = --map.end(); it != map.begin(); it--)
  {
    auto value = *it;
    std::cout << value.first << ", " << value.second.first << ", " << value.second.second << "\n";
  }
  std::cout << "find\n";
  auto it = map.find("a", "b");
  std::cout << it.second->second << "\n";
  std::cout << (map.find("c", "d") == map.end()) << "\n";
  map.erase(it);
  std::cout << (map.find("a", "b") == map.end()) << "\n";
}

This is just an initial framework, you'll need to implement any other methods you need.

Answer 2

Not relay thing you ask for, but IMO better approach.

Instead organizing your data into std::map<Level1Key, std::map<Level2Key, T>>, you should change your approach and just do: std::map<std::pair<Level1Key, Level2Key>, T>>. This way all your problems are solved immediately out of the box. You have to just add some braces when invoking API:

template <typename Level1Key, typename Level2Key, typename T>
using TwoLevelMap = std::map<std::pair<Level1Key, Level2Key>, T>;

int main()
{
    TwoLevelMap<std::string, std::string, int> map;
    map.insert_or_assign({"a", "b"}, 1);
    auto it = map.find({"a", "b"});
    std::cout << it->second << "\n";
    std::cout << (map.find({"c", "d"}) == map.end()) << "\n";
    map.erase(it);
    std::cout << (map.find({"a", "b"}) == map.end()) << "\n";
    map.insert_or_assign({"z", "b"}, 4);
    map.insert_or_assign({"z", "a"}, 11);

    for (auto& [kyes, v] : map) {
        std::cout << "k1: " << kyes.first << "  k2: " << kyes.second << "  value = " << v << '\n';
    }
}

It is possible you have some requirement where this solution is not a good for your application logic.

https://godbolt.org/z/1K7ovY74x