Можно создать дубликат:
How to make a fast search for an object with a particular value in a vector of structs or classes? c++Найти элемент в векторе со свойством
Есть ли более быстрый способ найти объект внутри вектора с заданным значением некоторого параметра, чем при использовании итераторов и останавливается, когда я нахожу ? У меня есть вектор
где
class Simple{
public:
string name;
int id;
}
Не зная ничего о векторе (отсортированных или нет, и т.д.), быстро вы можете получить линейное время (так же, как с помощью итераторов).
Но вы можете использовать std::find_if, чтобы украсить код - хотя он все равно будет работать в линейном времени.
Если вы запрашиваете контейнер несколько раз, вы можете отсортировать его (O(n*log(n))), а затем использовать двоичный поиск (O(log(n))). Но это только платит, если количество запросов сопоставимо с количеством элементов.
std::vector<Simple> на std::map<int, std::string>.Первый вариант имеет смысл только в том случае, если у вас достаточно запросов - сортировка сама по себе очень дорога. Второе предложение просто неверно. Его версия позволяет ему иметь несколько объектов 'Simple' с одним и тем же членом' int', но с разными строками и наоборот. –
Прочтите внимательно, пожалуйста. Я не писал, что кто-то должен сортировать. –
Если он не сортирует, как он может получить отсортированный вектор? –
Я не думаю, что есть более быстрый способ. – nhahtdh
Нет, если не существует специального упорядочения вектора. Если он отсортирован, например, вы можете использовать lower_bound, upper_bound, equal_range и т. Д., Которые будут быстрее. – jcoder
Метод шаблона find() из STL должен сделать это, хотя он итерации через весь вектор. – m0skit0