Что я могу сделать, чтобы улучшить этот поиск в векторе указателей?
Моя цель - проверить вектор Person* на предмет Person с именем person_name. Вектор отсортирован по именам в алфавитном порядке. Создание временного Person - единственный способ заставить этот вызов lower_bound работать с именем. Есть ли более эффективный способ сделать это или нужен temp для проведения сравнений?
//person_name is a string
Person temp(person_name);
auto it = lower_bound(personVec.begin(), personVec.end(), &temp, personCompare());
if (it != personVec.end() && (*it)->getName() == person_name) {}
else { return false; }
Ответы 1
temp не нужен. Вам нужен компаратор с соответствующей подписью.
Например, при разыменовании результатов personVec.begin() с помощью Person*&
а person_name имеет тип PersonName, тогда у вас может быть компаратор с такой сигнатурой:
bool compare(Person* const& a, PersonName const& b);
Вот простая функция, но подойдут и другие вызываемые объекты с такой подписью. Затем вы можете использовать lower_bound напрямую с person_name:
auto it = lower_bound(personVec.begin(), personVec.end(), person_name, compare);
Ваш общий вопрос был о том, как повысить производительность. Это невозможно предположить, увидев 4 строчки программы. Это должно быть выяснено путем профилирования всей программы при большой загрузке данных и анализа результатов. Например, сортировка personVec может занять больше времени, чем сортировка lower_bound. Тогда использование unordered_set вместо vector может дать гораздо лучшие результаты, чем оптимизация функции поиска в vector.
unordered_map выглядит правильным, но я не уверен в реализации. <Person*, string> Я установил его с помощью хэш-функции и функции равенства. find() использует первый параметр шаблона (ключ), как и хэш и равенство, но я хочу выполнить поиск по входному person_name, а затем получить итератор на указатель, и я смогу сделать это без temp. Не могли бы вы уточнить? @ Пенсионер ниндзя
Я должен уточнить: я исследую unordered_map, потому что читал, что он может быть полезен для того, что я пытаюсь сделать, но я буду использовать unordered_set, если этого достаточно.
Вы делали профилирование готового безупречного продукта с большой загрузкой данных? В противном случае правильный способ - внедрить продукт и забыть о производительности до того, как он станет полностью правильным, а затем профилировать его и выполнять работы по производительности. Только тогда вы знаете, что вам нужно в этом unordered_set<P,H,K,A> или unordered_map<S,P,H,K,A> или любом другом контейнере. Не используйте «Я хочу», используйте «Мне нужно, потому что ...» (заполните пробел). Например, P, должно ли быть Person *, а не Person? Вам нужно, чтобы экземпляр Person был изменяемым или динамически полиморфным?
Перед тем, как перейти к этому шагу, я убедился, что результаты верны. Причина, по которой я использую Person* для вектора, заключается в том, что я создаю программу-график с Person в качестве типа узла, и мне нужна реализация, аналогичная этой [stackoverflow.com/a/44859718/5181816], чтобы иметь доступ ко всем узлам и выполнять несколько задач, пока они доступны, например, соединение и перемещение.
Думаю, я понял это: unordered_map<string, Person*> Это позволяет ему выполнять find() в строке, а затем итератор дает доступ к Person с it->second.
Если вы собираетесь часто использовать поисковые имена, я бы посоветовал unordered_map. Если нет, то зачем беспокоиться о поиске чего-то другого, когда то, что у вас есть, работает? Поместите его в вспомогательную функцию и забудьте о нем, если вы не профилируете, и это узкое место.