Help with data structures

[MyOnlinePersona]

Hi, I have been tasked with creating an application that uses data structures. Problem is I have never used them and know nothing about them. The app I need to create is for a library system, so the user can search for a book, and then all the information of the book will be returned. So i need to store all this information somehow. I have been looking into certain data structures and came across trees and graphs, would one of these be the best method. I am just looking for someone to say what the best storage method would be so i can research it. Thank you

[lastchance]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Book
{
   string title;
   string author;
   string ISBN;
   // Any other information, publisher, year etc.
};


void findByAuthor( const vector<Book> &collection, const string &str )
{
   for ( const Book &bk : collection )
   {
      if ( bk.author.find( str ) != string::npos )
      {
         cout << "Title: " << bk.title  << '\n'
              << "Author: " << bk.author << '\n'
              << "ISBN: "  << bk.ISBN   << "\n\n";
      }
   }
}


int main()
{
   vector<Book> library;

   library.push_back( { "Hard Times", "Dickens, Charles", "978-1731093240" } );
   library.push_back( { "North and South", "Gaskell", "978-1799191544" } );
   library.push_back( { "Waverley", "Scott, Sir Walter", "978-1981958856" } );
   library.push_back( { "Ruth", "Gaskell, Elizabeth", "978-1357800680" } );

   findByAuthor( library, "Gaskell" );
}

Title: North and South
Author: Gaskell
ISBN: 978-1799191544

Title: Ruth
Author: Gaskell, Elizabeth
ISBN: 978-1357800680

[MyOnlinePersona]

So a vector is the best method? Even if for thousands of books? is it the quickest?
Also I should have added that you should be able to search for the book by name, author, type etc.

[lastchance]

I've amended it to use a procedure findByAuthor().

You can write other similar procedures such as findByTitle().

Note that it is searching on a partial match - no guarantee that you will always name the author in precisely the same way.


Vectors are general-purpose and good for dynamic data.

You could put them in a sorted container like a std::set<Book>, but then you would need to define an ordering for that set and it would be primarily sorted on one parameter, such as author.

MyOnlinePersona wrote:

So a vector is the best method?

No idea. It's my own opinion and you (and everybody else) are free to disagree.

[jonnin]

one generally does data structures from a slower, walk - before- you - run approach.
On that scale, Graphs are a f-22 jet, and you are not quite walking...

roughly, consider these data structures in this order so you don't get tangled up:
arrays (vectors are objectified arrays) {include sort, binary search, and hashing, and circular buffer}
lists {include sorting via mergesort and inserting in order, and double linked and skip linked}
*arrays and lists can give you a sidebar here for stack and queue concepts. *

and then off into c++ specifics: maps and sets and other tools the language offers.

after that, if you want to study advanced concepts, move to these:
trees {the 3 traversals, BST, balancing / red-black, non binary uses}
graphs {shortest path algorithm, and advanced studies}

! 90% or more of c++ is going to use a vector. They are very efficient and flexible. If you need something else, you need to justify WHY to yourself first. Spend a LOT of time learning to manipulate vectors and strings and your C++ will be better for it. The other stuff you can look up if you find yourself with something you can't do cleanly in a vector.

In decades of coding I have *never* used a (pure, full) graph (I have used a few lists and trees and other subgraphs). I played with them a few times, but never USED one in anything REAL. Even when doing neural networks, which are often graph-like conceptually, I did not code it 'as a graph' because I wanted high performance and less gotcha/debugging/oops scenarios and complexity. They get weird quickly and the cons outweigh the pros.

[lastchance]

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct Book
{
   string title;
   string author;
   string ISBN;
   // Any other information, publisher, year etc.
};


ostream & operator <<( ostream &out, const Book &bk )
{
   return out << "Title: "  << bk.title  << '\n'
              << "Author: " << bk.author << '\n'
              << "ISBN: "   << bk.ISBN   << '\n';
}

//------------------------------------------------

struct Library
{
   vector<Book> stock;
   void add( const Book &bk );
   void findByAuthor( const string &str );
   void findByTitle( const string &str );
};

//------------------------------------------------

void Library::add( const Book &bk )
{
   stock.push_back( bk );
}

//------------------------------------------------

void Library::findByAuthor( const string &str )
{
   for ( const Book &bk : stock )
   {
      if ( bk.author.find( str ) != string::npos ) cout << bk << '\n';
   }
}

//------------------------------------------------

void Library::findByTitle( const string &str )
{
   for ( const Book &bk : stock )
   {
      if ( bk.title.find( str ) != string::npos ) cout << bk << '\n';
   }
}

//======================================================================

int main()
{
   Library library;

   library.add( { "Hard Times", "Dickens, Charles", "978-1731093240" } );
   library.add( { "North and South", "Gaskell", "978-1799191544" } );
   library.add( { "Waverley", "Scott, Sir Walter", "978-1981958856" } );
   library.add( { "Ruth", "Gaskell, Elizabeth", "978-1357800680" } );

   string author, title;

   cout << "Enter an author: ";   cin >> author;
   library.findByAuthor( author );
   
   cout << "Enter a title (or part of title): ";   cin >> title;
   library.findByTitle( title );
}

Enter an author: Gaskell
Title: North and South
Author: Gaskell
ISBN: 978-1799191544

Title: Ruth
Author: Gaskell, Elizabeth
ISBN: 978-1357800680

Enter a title (or part of title): South
Title: North and South
Author: Gaskell
ISBN: 978-1799191544