C ++ - Алфавитные строки

Question

Я сейчас читаю информацию из входного файла.Из этой информации есть имя.Вся информация читается в структуре.Существует массив этих структур.

Мне нужно алфавитировать структуры по фамилии, используя двоичное дерево поиска.

Нужно ли написать функцию перегрузки оператора для ==<и>.Если да, может ли кто-нибудь помочь мне начать это?

Answer 1

Вам нужен способ сравнить любые два экземпляра структуры. Написание оператора сравнения, скажем, operator<(), может быть удобным способом сделать это.

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
}

Поскольку узел вставляет либо в левое поддерево, либо в правое поддерево, вам нужно знать только, находится ли узел "меньше" другого узла. Если это не так, то не имеет значения, больше он или равен другому узлу; в любом случае оно идет на другое поддерево.

Конечно, вам может понадобиться сравнение на равенство для какой-то другой задачи. Если вы это сделаете, то хорошей идеей будет пройти весь путь и предоставить оператор неравенства.

Также представляет интерес пространство имен rel_ops.

Answer 2

Да, вы захотите записать перегрузки операторов для == и <. (> не требуется; просто используйте регистр else после проверки, например, if (a < b); else if (a == b).)

В нашем случае, так как мы алфавитируем по фамилии, одна структура «меньше» другой, если и только если ее фамилия предшествует алфавиту фамилии другого.

Так в чем именно проблема? Вы знаете, как писать операторские перегрузки? Вы знаете, как сравнивать строки и определять, что происходит в алфавитном порядке?

Answer 3

Операторские перегрузки работают так же, как функции или методы. Они получают возвращаемый тип и аргументы точно так же. Например, бинарный оператор (например, <) будет функцией-членом с одним аргументом или свободной функцией с двумя, по одному для каждой стороны оператора. отличается только тем, что вместо имени функции идентификатора используется специальный синтаксис, ключевое слово operator, за которым следует перегруженный оператор. Поэтому, если мы хотим иметь сопоставимый тип, мы можем сделать это следующим образом:

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;
}

Answer 4

Обычно вам нужно перегрузить <, но если в структуре есть другие элементы, по которым вы, возможно, захотите когда-нибудь отсортировать, это не имеет смысла делать это.Вы должны написать отдельную функцию, которая принимает два параметра вашей структуры и сравнивает их по фамилии, возвращая true, если первое должно предшествовать второму, иначе false.Затем передайте эту функцию в std :: sort.Примерно так: </p>

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);

Вы заметите, что я проигнорировал ваше утверждение «Использование бинарного дерева поиска», потому что я не совсем понимаю, что вы имеете в виду, но это, вероятно, не имеет значения.Вы сделали свой собственный класс контейнера или что-то?