C++ - Alphabatizing Strings

I am currently reading information from an input file. Of that information, there is a name. All the information is read into a struct. There is an array of these structs.

I need to alphabetize the structs by the last name, using a Binary Search Tree.

Do I need to write an operator overload function for ==, <, and >. If so can someone help me get started on that?

Answers


Operator overloads work just like functions or methods. They get a return type and arguments in just the same way. For instance, a binary operator (like <) would be a member function with one argument or a free function with two, one each for each side of the operator. the only thing that's different is instead of having an identifier function name, they use a special syntax, the keyword operator followed by the operator being overloaded. So if we wanted to have a comparable type, we could do it this way:

class MyUserType
{
  private:
    std::string sort_significant;
    std::string sort_insignificant;
  public:
    bool operator<(const MyUserType &) const;
};

bool MyUserType::operator<(const MyUserType & other) const
{
   return sort_significant < other.sort_significant;
}

Yes, you will want to write operator overloads for == and <. (> is not needed; just use the else case after checking e.g. if (a < b); else if (a == b).)

In our case, since we are alphabetizing by last name, one struct is "less than" another if and only if its last name comes before the other's last name alphabetically.

So what exactly is the problem? Do you know how to write operator overloads? Do you know how to compare strings and determine which comes first alphabetically?


You need a way to compare any two instances of the struct. Writing a comparison operator, say, operator<(), might be a convenient way to go about it.

class Record {
    friend bool operator<(const Record&, const Record&);
    std::string name;
    // ...
};

bool operator<(const Record& a, const Record& b)
{
    // return true if the name of a is less than the name of b
}

Because a node inserts either on the left subtree or the right subtree you only need to know if a node is "less than" another node. If it isn't, then it doesn't matter whether it's greater or equal to the other node; it goes on the other subtree either way.

Of course, you might need the equality comparison for some other task. If you do then it's a good idea to go all the way and provide the inequality operator as well.

Also of interest is the rel_ops namespace.


You would normally need to overload <, but if there are other elements in the struct that you might sometime want to sort by, it doesn't really make sense to do that. You should write a separate function that accepts two parameters of your struct, and compares them by last name, returning true if the first should come before the second, false otherwise. Then pass that function to a std::sort. Something like this:

bool compare_by_last_name(const MyStruct & lhs, const MyStruct & rhs)
{
    return lhs.last_name < rhs.last_name;
}

// later

vector<MyStruct> v;

// put some elements in v

std::sort(v.begin(), v.end(), compare_by_last_name);

You will notice I have ignored your statement "Using a binary search tree", because I don't quite know what you mean, but it's probably irrelevant. Did you make your own container class or something?


Need Your Help

Q.all and an array of promises don't seem to be working

node.js q node-mysql

I'm trying to use Q to do some work. I loop through and call a function which saves data to the database and returns a promise. Once those are done I need to do something else, but the Q.all finish...

CSS Menu not aligning properly

css css3 jquery-mobile responsive-design

Im designing a mobile app in jquery mobile. Im trying design a responsive menu but problem is when my menu content is more than 1 line its acting weird. here is a screenshot of what I want and what I