How should maps be created in a loop that need to be used later?

Question

Let's say I have an arbitrary hierarchy of classes. A Books class contains a map made up objects of the Chapter class. Each Chapter has its own map of objects of the Section class.

The class keys are the titles of each corresponding object, e.g. if we have a book with a title of Moby Dick, the book's chapters map would contain chapters like Loomings and The Spouter-Inn, and so on.

Here might be a simple set of classes describing this relationship:

class Section {
  public: 
    string title;
    Section (string t) { title = t; }; 
};

class Chapter {
  public: 
    map <string, Section *> sections;
    string title;
    Chapter (map <string, Section *> s, string t) { sections = s; title = t; };
};

class Book {
  public: 
    map <string, Chapter *> chapters;
    string title;
    Book (map <string, Chapter *> c, string t) { chapters = c; title = t; };
};

If I had a textfile (let's just call it books.txt) of space-separated book, chapter, and section titles, e.g.

Moby_Dick Loomings Section_I
Moby_Dick Loomings Section_II
Moby_Dick The_Spouter-Inn Section_I
Moby_Dick The_Spouter-Inn Section_II
Moby_Dick Loomings Section_I
Moby_Dick The_Carpet-Bag Section_I
Moby_Dick The_Spouter-Inn Section_I
Moby_Dick The_Counterpane Section_I
Moby_Dick Breakfast Section_I
Moby_Dick The_Street Section_I
Frankenstein Chapter_1 Section_I
Frankenstein Chapter_1 Section_II
Frankenstein Chapter_2 Section_I
Frankenstein Chapter_2 Section_II
Frankenstein Chapter_2 Section_III
Frankenstein Chapter_3 Section_I
Frankenstein Chapter_4 Section_I
Frankenstein Chapter_5 Section_I
Frankenstein Chapter_6 Section_I
Pride_and_Prejudice Chapter_1 Section_I
Pride_and_Prejudice Chapter_2 Section_I
Pride_and_Prejudice Chapter_3 Section_I
Pride_and_Prejudice Chapter_4 Section_I
Pride_and_Prejudice Chapter_5 Section_I
Pride_and_Prejudice Chapter_6 Section_I

and so on, I might open the file with ifstream and process each line, adding a new book object to a map of books, and adding to that book object's chapters map each chapter, and to each chapter's section map each section, etc.

Let's say the ultimate goal is to parse the lines of the files describing these book, chapters, and sections into maps, and then be able to list them in alphabetical order.

So I start by collecting the books:

#include <iostream> // cout, cerr, etc.
#include <cstdlib> // exit, EXIT_FAILURE
#include <string>
#include <fstream> // ifstream
#include <sstream> // istringstream
#include <fstream> // ifstream
#include <map> 
using namespace std;

class Section {
  public: 
    string title;
    Section (string t) { title = t; }; 
};

class Chapter {
  public: 
    map <string, Section *> sections;
    string title;
    Chapter (map <string, Section *> s, string t) { sections = s; title = t; };
};

class Book {
  public: 
    map <string, Chapter *> chapters;
    string title;
    Book (map <string, Chapter *> c, string t) { chapters = c; title = t; };
};



int main() {

  map <string, Book *> books;

  string filename = "books.txt";

  ifstream fin(filename.c_str()); // open file 
  string line;

  if (fin.is_open()) {

    while (getline(fin, line)) {
      istringstream sin(line);
      string bookTitle, chapterTitle, sectionTitle;
      sin >> bookTitle >> chapterTitle >> sectionTitle;


      if (books.count(bookTitle)) {
        // the book is already in our map
        // ... now what?
       
      } else {
        // the book doesn't exist yet, so go ahead and create fresh book, chapter, and section objects (and their maps) 
        Section section (sectionTitle); // create new section object
        map <string, Section *> sections; 
        sections[sectionTitle] = & section;

        Chapter chapter (sections, chapterTitle); // create new chapter object
        map <string, Chapter *> chapters; // create new chapters map 
        chapters[chapterTitle] = & chapter; // add chapter to chapters map

        Book book (chapters, bookTitle); // create new book object
        books.insert(make_pair(bookTitle, & book)); // add book to books map
      }


    }
  }

  fin.close();

  map <string, Book *>::iterator book_iter;

  // print our resulting book map
  for (book_iter = books.begin(); book_iter != books.end(); book_iter++) {
    cout << "book: " << book_iter->first << endl;
  }

}

Easy enough, this works well:

$ g++ -Wall -Wextra -std=c++98 -o books books.cpp && ./books 
book: Frankenstein
book: Moby_Dick
book: Pride_and_Prejudice

The problem is when I need to add chapters to existing books in the books map.

So at first I expand this section:

      if (books.count(bookTitle)) {
        // the book is already in our map
        // ... now what?
       
      } else {

It becomes:

      if (books.count(bookTitle)) {
        // the book is already in our map
        Book book = (*books.at(bookTitle));

        if (book.chapters.count(chapterTitle)) {
          // the chapter is already in our map
          // ... now what?

        } else {
          // the chapter doesn't exist yet, so go ahead and create a fresh chapter and section
          Section section (sectionTitle); // create new section object
          map <string, Section *> sections; 
          sections[sectionTitle] = & section;

          Chapter chapter (sections, chapterTitle); // create new chapter object
          book.chapters.insert(make_pair(chapterTitle, & chapter));
        }   
            
      } else {

But now when I run the code, I get:

Segmentation fault: 11

The specific thing that causes the seg fault is book.chapters.count(chapterTitle) - I assume because the book.chapters is no longer accessible.

As each iteration of the loop happens, the variables created in the scope of that iteration is cleaned up, and then I try to go back and reference that map again and it is gone.

So what do I do? I am not sure what the correct way to approach this is.

Answer 1

You have one major issue with your code.

If you store a pointer to an object, you yourself are responsible for making sure that object stays alive for as long as you plan to use the pointer. C++ doesn't have garbage collection. Variables with automatic storage duration dies as soon as they go out of scope.

} else {
    // the book doesn't exist yet, so go ahead and create fresh book, chapter, and section objects (and their maps) 
    Section section (sectionTitle); // create new section object
    map <string, Section *> sections; 
    sections[sectionTitle] = & section;

    Chapter chapter (sections, chapterTitle); // create new chapter object
    map <string, Chapter *> chapters; // create new chapters map 
    chapters[chapterTitle] = & chapter; // add chapter to chapters map

    Book book (chapters, bookTitle); // create new book object
    books.insert(make_pair(bookTitle, & book)); // add book to books map
}

Once we get to the end of that block of code, the book, chapter and section that you created on the stack are destroyed. But you have inserted pointers to them in your containers. Now as soon as you try to use those pointers, they will be dangling. They will point where the objects used to live on the stack, but they have already been destroyed.

If you really want to store pointers in your maps, I would suggest smart pointers. They are smart in the sense that they will manage lifetime of the object for you.

But in your case I don't see any reason to not store objects in the maps directly.

With that part out of the way, we can move on to the logic.

The description of Map::insert reads:

Inserts element(s) into the container, if the container doesn't already contain an element with an equivalent key.

Return value 1-3) Returns a pair consisting of an iterator to the inserted element (or to the element that prevented the insertion) and a bool denoting whether the insertion took place.

With that knowledge we can simplify the logic of your code a bit to something like:

auto [book, book_inserted] = books.insert(make_pair(bookTitle, Book({}, bookTitle)));

Now book is an iterator pointing to one of:

• The new empty book we just created
• The book that was already in the map under bookTitle

book_inserted tells us if our empty book was actually inserted, or if there already was a book stored under that title from earlier. We don't really care either way, we just need the iterator.

Next we can insert the chapter using that iterator

auto [chapter, chapter_inserted] = book->second.chapters.insert(make_pair(chapterTitle, Chapter({}, chapterTitle)));

Last, we use the chapter iterator to insert the section.

chapter->second.sections.insert(make_pair(sectionTitle, Section(sectionTitle)));

Here is a complete example

#include <iostream> // cout, cerr, etc.
#include <cstdlib> // exit, EXIT_FAILURE
#include <string>
#include <fstream> // ifstream
#include <sstream> // istringstream
#include <fstream> // ifstream
#include <map> 
using namespace std;

class Section {
  public: 
    string title;
    Section (string t) { title = t; }; 
};

class Chapter {
  public: 
    map <string, Section> sections;
    string title;
    Chapter (map <string, Section> s, string t) { sections = s; title = t; };
};

class Book {
  public: 
    map <string, Chapter> chapters;
    string title;
    Book (map <string, Chapter> c, string t) { chapters = c; title = t; };
};



int main() {

  map <string, Book> books;

  string filename = "books.txt";

  ifstream fin(filename.c_str()); // open file 
  string line;

  if (fin.is_open()) {

    while (getline(fin, line)) {
      istringstream sin(line);
      string bookTitle, chapterTitle, sectionTitle;
      sin >> bookTitle >> chapterTitle >> sectionTitle;

      auto [book, book_inserted] = books.insert(make_pair(bookTitle, Book({}, bookTitle)));

      auto [chapter, chapter_inserted] = book->second.chapters.insert(make_pair(chapterTitle, Chapter({}, chapterTitle)));

      chapter->second.sections.insert(make_pair(sectionTitle, Section(sectionTitle)));
    }
  }

  fin.close();

  // print our resulting book map
  for (auto book_iter = books.begin(); book_iter != books.end(); book_iter++) {
    cout << "book: " << book_iter->first << endl;
  }

}

Answer 2

The core of the problem is

        Section section (sectionTitle); // create new section object
        map <string, Section *> sections; 
        sections[sectionTitle] = & section;

        Chapter chapter (sections, chapterTitle); // create new chapter object
        map <string, Chapter *> chapters; // create new chapters map 
        chapters[chapterTitle] = & chapter; // add chapter to chapters map

        Book book (chapters, bookTitle); // create new book object

all declare automatic variables scoped by the current code block and store pointers to the previous objects. This is all fine because they will all go out of scope and be destroyed at the same scope and in a safe order. No container outlives the contained.

But...

    books.insert(make_pair(bookTitle, & book));

stores a pointer to the soon-to-expire variable book and books will outlive book. This is fatal.

The trivial solution is NO POINTERS. Each container directly contains the objects they contain rather than references to them. Now the contained cannot go out of scope before the container. The containers will manage the destruction of the contained free of charge, relieving the memory management burden from your shoulders.

class Section {
  public: 
    string title;
    Section (string t): title(t) { }; // using member initializer list rather than 
                                      // assignment in the body of the constructor 
                                      // allows the compiler to more easily apply 
                                      // many useful optimizations 
};

class Chapter {
  public: 
    map <string, Section> sections;
    string title;
    Chapter (map <string, Section> s, string t): sections(s), title(t)  { };

class Book {
  public: 
    map <string, Chapter> chapters;
    string title;
    Book (map <string, Chapter> c, string t): chapters(c), title(t) { };
};

Now

        Section section (sectionTitle); // create new section object
        map <string, Section *> sections; 
        sections[sectionTitle] = & section;

        Chapter chapter (sections, chapterTitle); // create new chapter object
        map <string, Chapter *> chapters; // create new chapters map 
        chapters[chapterTitle] = & chapter; // add chapter to chapters map

        Book book (chapters, bookTitle); // create new book object
        books.insert(make_pair(bookTitle, & book)); // add book to books map

becomes

        Section section (sectionTitle); // create new section object
        map <string, Section> sections; 
        sections[sectionTitle] = section;

        Chapter chapter (sections, chapterTitle); // create new chapter object
        map <string, Chapter> chapters; // create new chapters map 
        chapters[chapterTitle] = chapter; // add chapter to chapters map

        Book book (chapters, bookTitle); // create new book object
        books.insert(make_pair(bookTitle, book)); // add book to books map

section is copied into sections and sections is copied into chapter, etc... Copies all the way down. The originals can go out of scope and expire and the copies live on until removed or the container is destroyed.

That copying sounds ugly, but the modern C++ compiler is smart and offers a few faster alternative like using move semantics to reduce unnecessary copying and a modern compiler will apply copy elision where possible and may make moving or copying unnecessary. Move semantics and copy elision can get complicated and will clutter this answer, so they would be best discussed in a future question, if necessary.

The revision at the bottom of the question suffers a similar problem with one small wrinkle:

Book book = (*books.at(bookTitle));

made a copy of the book in books. Book book is not a pointer or a reference to a book, and the * in *books.at(bookTitle) means "Get me the object at the pointer mapped to bookTitle in books. The rest of the code block operates on the copy and the copy goes out of scope accomplishing nothing. The original in books was not changed.

Book & book = (*books.at(bookTitle));

would make a reference to the Book in books and you can use the referenced to modify the referenced Book.