Repeat after me...
"When I do a search in C++ and I don't use
std::sort and
std::find I shall go and punch myself in the head OR, preferably as I don't like pain, I shall rewrite my class so it can be put in a collection and sorted and searched."
Having said that, how can you write a class that enables objects of the class to stick an object in a collection so you can use
std::sort and
std::find? For simple objects the answer is remarkably, er, simple: You just need a less than operator (for
std::sort) and an equality operator (for
std::find).
If you use these two you don't need any explicit loops AND the implementations of
std::sort (usually uses an O(nlogn) sort at first and then switches to an O(n squared) algorithm when the partitions get small enough) and
std::find (usually uses a binary search, O(logn) ) aren't too bad. Time them and see with your data set.
Just to show you how easy this is have a look at the following code. It's not complete but it shows how simple sorting and searching can be if you know how to implement your classes:
#include <string>
#include <ostream>
#include <vector>
#include <algorithm>
class book
{
public:
book( const std::string &title, const std::string &author )
: title_( title ), author_( author )
{
}
friend bool operator<( const book &, const book & );
friend bool operator==( const book &, const book & );
friend std::ostream &operator<<( std::ostream &, const book & );
private:
std::string title_;
std::string author_;
};
bool operator<( const book &a, const book &b )
{
return a.author_ < b.author_;
}
bool operator==( const book &a, const book &b )
{
return a.author_ == b.author_;
}
std::ostream &operator<<( std::ostream &output_to, const book &to_output )
{
return output_to << "Title: " << to_output.title_
<< "\nAuthor: " << to_output.author_;
}
const book books_you_should_read[] =
{
book( "The C++ Programming Language", "Stroustrup, Bjarne" ),
book( "Standard C++ IOStreams and Locales", "Langer, Angela" ),
book( "Exceptional C++", "Sutter, Herb" ),
book( "Effective C++", "Myers, Scott" ),
book( "Accelerated C++", "Koenig, Andrew" )
};
void book_test( std::ostream &output )
{
std::vector<book> library( std::begin( books_you_should_read ),
std::end( books_you_should_read ) );
std::sort( std::begin( library ), std::end( library ) );
auto found = std::find( std::begin( library ),
std::end( library ),
book( "Anything", "Stroustrup, Bjarne" ) );
if( found != std::end( library ) )
{
output << "Found:\n" << *found << std::endl;
}
else
{
output << "Couldn't find a book by God" << std::endl;
}
}
This code isn't a paragon of C++ coding because:
- Everything's inline
- book isn't a useful class - up to you to make it useful
- I haven't used any PIMPs or other compilation firewalls
- It doesn't show all the members you need to write a class that works like a built in type
It's good because:
- It is really simple, all the complexity is managed by the class
- No explicit loops
- Very little conditional code
Oh, and if this is homework:
- Please use this as inspiration in your C++ practice, it ain't perfect but the salient points aren't too bad
- If you copy this and hand it in may you burn in your own hell of personal guilt
- If you copy this and hand it in AND get a good mark then demand your course fee back, your lecturer is crap either by not teaching you the right things or in the wrong order. Either way he's a muppet that's doing you no favours
- Please see the list of books it'd be good for you to read. Start with "Accelerated C++" and go from there
Edited because I hate this editor, it tries to be too effing clever and so was I, so I fixed a bug
PS: From solution 4...
You're starting to do the sort of thing that databases do. You could take a leaf out of their book and construct indexes of all the possible values you could sort and find on. So instead of sorting and finding on the
vector of books you'd do it on a collection of
book proxy objects, one or more of which would represent the author in the vector of books.
Instead of sorting and searching an array you might as well go the whole hog and use a pair of
std::multimaps:
std::multimap<const std::string &, const book &> book_title_name_index;
std::multimap<const std::string &, const book &> author_name_index;
Then hack out each word (sans punctuation) in the title and author of each book sticking the word and the book in the map for each word in the title. So "The Two Towers" by J.R.R.Tolkien would have three entries in the
book_title_name_index, one against "The" (you might like to weed out common words that appear frequently), "Two" and "Towers" and one "Tolkien" in the
author_name_index as you don't want initials munging up the works.
Then you'll be able to use either the
find function on
multimap to find a book with the word match, e.g:
auto book_location = book_title_index.find( "Towers" );
if( book_location != end( book_title_index ) )
{
std::cout << "found:" << *book_location;
}
or use the
equal_range function to get any books that match the criteria you set.
So the method is...
- Save the objects you want to work with somewhere easily accessible
- Stick the objects by reference one or more times into one or more
multimaps that are keyed by the search parameters you want to use.
- Use
find or
equal_range to get the objects you're interested in.
Submit an article or tip