Simultaneous STL container insertion with strong exception guarantee

Question

I want to insert into several STL containers simultaneously, and either have all succeed, or all of them remain unchanged. How can I do this elegantly?

In my example, I have a custom container with various STL containers 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;
};

class MyContainer {
public:
  void Insert(std::vector<std::string> names,
              std::unordered_set<int> 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 categories */
  std::map<std::string, int> name_to_id_;
  std::map<int, 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");
    }
    try {
      this->name_to_id_.insert({*it, id});
    } catch (/* what do I catch here? */) {
      /* 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) {
    try {
      this->categories_.at(*it).insert(id);
    } catch (/* what do I catch here? */) {
      /* 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");
    }
  }
  try {
    this->data_.push_back(data);
  } catch (/* what do I catch here? */) {
    /* 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?

I occurred to me that the insert and push_back statements would have to be wrapped in a try block to truly handle the exception, but what exception do I catch?

Answer 1

If you can modify the constructor of DataItem, you can make it insert stuff to the next container from the constructor of the previous item. Here's a working demo

  #include <vector>
  #include <list>
  #include <functional>
  #include <iostream>
  
  struct mydata
  {   
      int a;
      double b;
      template <typename F>                   
      mydata (int a, double b, F func) : a(a), b(b) { func(); }
  };                                                           
    
  int main()
  {         
      std::vector<mydata> one;
      std::vector<mydata> two;
      std::list<mydata> three;
      std::list<mydata> four; 
                             
      try {               
          one.emplace_back  (1, 2, [&]() {
          two.emplace_back  (1, 2, [&]() { 
          three.emplace_back(1, 2, [&]() { 
          four.emplace_back (1, 2, [ ]() { 
          throw 42; // simulate failure at the last one
          }); }); }); });
      } catch (int x)  {                                          
          // handle the failure
      }                 
       
      std::cout << one.size() << " " 
                << two.size() << " " 
                << three.size() << " " 
                << four.size() << "\n";
  }

The program prints four zeros as expected.

Answer 2

I don't address the actual clean up operation nor what is the most efficient way to do that. You will need to record at what stage the insertion failed and proceed accordingly.

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

class SomeException : std::exception
{
public:
   SomeException(char *c) : std::exception(c) {};

};

class MyContainer {
public:
   void Insert(std::vector<std::string> names,
      std::unordered_set<int> categories,
      DataItem data);

private:
   void CleanUp();

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 categories */
   std::map<std::string, int> name_to_id_;
   std::map<int, std::unordered_set<int>> categories_;
   std::vector<DataItem> data_;
};


void MyContainer::CleanUp()
{
   // Do your clean up here
}

void MyContainer::Insert(std::vector<std::string> names,
   std::unordered_set<int> categories,
   DataItem data) 
{
   bool failed = false;

   /* ensure names, and categories are not empty and data is valid */
   int id = data_.size();
   for (auto it = names.begin(); it != names.end() && !failed; ++it) {
      if (this->name_to_id_.count(*it))
         failed = true;
      try {
         this->name_to_id_.insert({ *it, id });
      }
      catch (...) {
         failed = true;
      }
   }

   for (auto it = categories.begin(); it != categories.end() && !failed; ++it) {
      try {
         this->categories_.at(*it).insert(id);
      }
      catch (...) {
         failed = true;
      }
   }

   try {
      if (!failed)
         this->data_.push_back(data);
   }
   catch (...) {
      failed = true;
   }

   if (failed)
      CleanUp();
}