Определение <
для std::pair
реализует лексикографический порядок, а ""
- минимальный элемент для строк. Отсюда мы получаем:
typedef std::pair<std::string, std::string> StringPair;
typedef std::set<StringPair> Set;
std::string const* find_first(Set const& s, std::string const& key) {
Set::const_iterator const it = s.lower_bound(std::make_pair(key, ""));
// Check that it actually points to a valid element whose key is of interest.
if (it == s.end() or it->first != key) { return 0; }
// Yata!
return &it->second;
}
Хитрость использует lower_bound
соответствующим образом.
Возвращает итератор, указывающий на первый элемент, который не сравнивается с value
.
- Если она возвращает
end()
, то он не нашел ничего интересного.
- В противном случае,
it->first >= key
так мы избавимся от >
случая (интереса не к нам)
Я хотел бы отметить, однако, что это только возвращает первый элемент диапазона. Если вы заинтересованы во всех элементах, попробуйте:
typedef std::pair<Set::const_iterator, Set::const_iterator> SetItPair;
SetItPair equal_range_first(Set const& s, std::string const& key) {
StringPair const p = std::make_pair(key, "");
return std::make_pair(s.lower_bound(p), s.upper_bound(p));
}
Это вернет полный спектр узлов s
, первый элемент которого равен key
. Затем вы просто должны перебирать этот диапазон:
for (Set::const_iterator it = range.first; it != range.second; ++it) {
// do something
}
И вы даже не придется беспокоиться ли возвращение lower_bound
или upper_bound
конца или нет.
- если
lower_bound
возвращает end()
, то и upper_bound
, и цикл пропускается
- , если
lower_bound
указывает на узел, для которого it->first > key
, то upper_bound
будет указывать на тот же узел, и цикл пропускается
Это сила диапазонов: нет необходимости делать специальные проверки, диапазоны просто заканчиваются пустым, когда нет совпадения, и поэтому цикл над ними ... пропускается с одной проверкой.
Почему вы не используете «карту»? Другие примечания: если это 'std :: set', почему он называется' myList'? Вы создали функцию сравнения для 'std :: pair'? Как это выглядит? –