What is the best way of cleaning up STL associative container insertions when ensuring exception safety?

In my simplified example, I have a custom container with various STL containers (std::unordered_set is one of them) as data members. An insertion operation inserts into various containers, but if one of them fails, the changes need to be undone to ensure all invariants are still valid. How can I do this (nicely)?

My first intuition is to go backwards through all insertions that were made and undo them. This seems excessive though as I hope my example will illustrate.

Example (Sorry if not "minimal enough"):

struct DataItem {
  int x;
  float y;
  char c;
};

enum class Categories {kFirst, kSecond, kThird};

class MyContainer {
public:
  void Insert(std::vector<std::string> names,
              std::unordered_set<Categories> categories,
              DataItem data);
private:
  /* invariant: if a string 'name' is mapped to an id 'i' in 'name_to_id_'
                it must be the position of a 'DataItem' object in 'data_'
                and contained in at least one of the three categories */
  std::map<std::string, int> name_to_id_;
  std::map<Category, std::unordered_set<int>> categories_;
  std::vector<DataItem> data_;
};

MyContainer::Insert(std::vector<std::string> names,
                    std::unordered_set<Categories> categories,
                    DataItem data) {
  /* ensure names, and categories are not empty and data is valid */
  int id = data_.size();
  for (auto it = names.begin(); it != names.end(); ++it) {
    if (this->name_to_id_.count(name)) {
      /* Clean up all names inserted so far by iterating backwards to names.begin()
         using this->name_to_id_.erase */
      throw SomeException("Insertion failed");
    }
    this->name_to_id_.insert({*it, id});
    if (!this->name_to_id_.count(name)) {
      /* Clean up all names inserted so far by iterating backwards to names.begin()
         using this->name_to_id_.erase */
      throw SomeException("Insertion failed");
    }
  }
  for (auto it = categories.begin(); it != categories.end(); ++it) {
    this->categories_.at(*it).insert(id);
    if (!this->categories_.at(*it).count(id)) {
      /* Clean up all names and all categories id was inserted into so far by
         iterating backwards to categories.begin() using
         this->categories_.at(*it).erase(id) */
      throw SomeException("Insertion failed");
    }
  }
  this->data_.push_back(data);
  if (this->data_.size() == id) {
    /* Once again clean up all categories and names... */
    throw SomeException("Insertion failed");
  }
}

Even without writing out the cleanups, this seems excessive. Especially considering that insert and push_back should rarely fail to begin with. Is this really what I need to do?

Also, the safest way to erase changes made that I could determine for the std::unordered_set's and the std::map was a combination of find and erase, but I couldn't find anything on find's exception safety. Does it always succeed?