Choose data structure and algorithm for assigning books to category

Question

I want to write following project:

Books in library are described as following: author; title; label1, label2, label3...

Book may have few labels. Sample data in txt file:

Herbert; Dune; sci-fi; desert;
Shakespeare; Hamlet; tragedy, baroque;

I want to display books by labels. For example:

desert:
Herbert; Dune;

sci-fi:
Herbert; Dune;

tragedy:
Shakespeare; Hamlet;

baroque:
Shakespeare; Hamlet;

Which data structure should I use to store books data? I don't want to get all labels and iterate over all books. I'm open to any ideas.

Answer 1

This depends on more factors. For example, how much are you willing to trade space for time?

I don't want to get all labels and iterate over all books. I'm open to any ideas.

If you want to focus on that look-up and make that as fast as possible (while allowing compromises on other operations, eg insertion) then the following might be an option.

You can keep a std::map< label, std::vector<book> > m that stores each book several times, once for each label. Then the look up is simply:

auto books = m["label1"]; // all books with label "label1"

You do not need to store copies of the books when you add a level of indirection and store indices or iterators to the container that stores the actual instances:

 std::vector<book> books;
 std::map< std::string, std::vector<unsigned>> m;
 for ( const auto& ind : m["label1"]) {
     book b = books[ind];
     // ...
 }

However, depending on the size of books, looking up books at random indices in the vector can be rather expensive while with the above this is avoided at the cost of storing each book multiple times.