Контейнеры set и unordered_set представляют собой различные структуры данных, каждая из которых имеет свои особенности по скорости выполнения основных операций, включая поиск. Вот как работают эти контейнеры и какова сложность их операций поиска:
Реализуется как сбалансированное двоичное дерево поиска, обычно как красно-черное дерево. Он хранит элементы в отсортированном порядке, что позволяет выполнять двоичный поиск. Сложность поиска: Поиск в нем выполняется за логарифмическое время, \(O(\log n)\), где \(n\) — количество элементов в
set. Эта эффективность достигается за счёт использования структуры сбалансированного дерева, которое позволяет быстро делить данные на меньшие сегменты.Реализуется с использованием хеш-таблицы. Это позволяет, при идеальных условиях, выполнять поиск за константное время. Сложность поиска: В среднем, поиск в нем занимает константное время \(O(1)\). Однако в худшем случае, например, при неудачной работе хеш-функции или при большом количестве коллизий, поиск может деградировать до \(O(n)\). В таких ситуациях все ключи могут оказаться в одной "корзине" или "ведре" (bucket), и для нахождения правильного элемента потребуется просмотреть все элементы в этом ведре.
Для
set#include <iostream>
#include <set>
int main() {
std::set<int> mySet = {5, 3, 9, 1};
auto search = mySet.find(3);
if (search != mySet.end()) {
std::cout << "Found " << *search << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
}
Для
unordered_set#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> mySet = {5, 3, 9, 1};
auto search = mySet.find(3);
if (search != mySet.end()) {
std::cout << "Found " << *search << std::endl;
} else {
std::cout << "Not found" << std::endl;
}
return 0;
}
Ставь 👍 и забирай 📚 Базу знаний