Всім доброго часу доби!
Отже, приступимо. Як багато хто знає, "set" перекладається з англійської як "безліч". Звідси можна зробити логічний висновок, що set - це якась структура даних, яка реалізує безліч як математичний об'єкт. В С ++ 11 є дві різні реалізації безлічі. Перша прийшла до нас з С ++ 98. Це звичайний set і заснований він на реалізації червоно-чорного дерева. Друга реалізація - unordered _ set. яка була "узаконена" з введенням стандарту З ++ 11. Вона заснована на хеш-таблицях.
Для сету визначені наступні корисні для нас операції:
Як і для безліч інших контейнерів stl, щоб оголосити set, необхідно прописати
Можна також використовувати конструктор, щоб відразу форматувати контейнер. Ініціалізацію можна провести іншим контейнером або парою ітераторів [first. last).
Виконується за допомогою перевантаженої функції insert. Синтаксис її виклику:
Ось її основні варіанти:
Приймає value - значення, яке слід вставити в безліч і повертає пару - итератор, який вказує на вставлений елемент і bool'еву змінну, що позначає "успішність" вставки. Тобто 1 - вставка сталася, 0 - немає. Ця функція виконується за логарифм від розміру контейнера, тобто, за O (logn).
Приймає значення value і итератор hint і намагається вставити елемент якомога ближче до Ітератор hint. Якщо вставка буде проведена відразу після або перед ітератора hint. то функція відпрацює за O (1). інакше за O (logn).
Додає в set всі елементи, що знаходяться на проміжку [first; last) за O ((last - first) logn). InputIt повинен відповідати вимогам InputIterator. тобто підтримувати такі операції:
При цьому всі покажчики і ітератори на елементи set залишаються в робочому стані. Варто також відзначити, що set підтримує лише одне входження елемента з однаковим значенням, якщо ж в безлічі вже є елемент з таким значенням, він доданий не буде. Однак, є структура multiset. яка підтримує множинні входження одного і того ж елемента. Однак, операції над нею, за винятком невеликих нюансів тотожні операціями над set і тому тут вона розглядатися не буде.
Існує кілька різних функцій для пошуку елементів в set. Ось вони:
Вважає кількість входжень елемента з ключем key в контейнер. Очевидно, що в силу властивостей контейнера, ця функція повертає або 0, або 1. Працює за O (logn).
Знаходить елемент з ключем key. Якщо елемент знайдений, повертає ітератор на нього, інакше на end () контейнера. Працює за O (logn).
Повертає ітератор на перший елемент в множині, який більше, або дорівнює шуканого. O (logn).
Повертає ітератор на перший елемент в множині, який строго більше шуканого. O (logn).
Зверніть увагу! Для правильного використання цих функцій, треба викликати їх як функції-члени контейнера.
Існує також перевантажена функція erase (). яка дозволяє видаляти елементи. Ось її основні варіанти:
Видаляє елемент, що знаходиться в позиції, зазначеної ітератором. Амортизована складність - O (1).
Видаляє всі елементи з ключовим значенням key. Зрозуміло, що, якщо це просто set. а не multiset. кол-во таких елементів не перевищує 1. Працює за O (logn + count (key)).
Видаляє всі елементи в діапазоні [first; last). Працює за O (logn + distance (first. Last)).
Тепер поговоримо про map. Назва походить від mapping - асоціативний масив. Операції на ньому практично тотожні set. проте в елементах контейнера зберігається не одне значення, а пари ключ-значення. Сортування в даному випадку буде проходити таким же чином, як при звичайній сортування пар - спочатку пріоритетом йде порівняння перших елементів в парі, потім, в разі їх рівності, порівнюються другі елементи. Також варто відзначити дуже зручну реалізацію звернення за індексами. Наприклад, ось такий код:
Спочатку створить в контейнері test _ map пару ( "ten", 10), а потім змінить другий елемент в ній на 8.
unordered _ set і unordered _ map підтримують більшість операцій, які підтримуються set і map. але, в середньому, виконують їх за О (1). Незважаючи на це, їх не завжди вигідно використовувати, тому що unordered означає невпорядкований, тобто елементи в них не підтримуються в відсортованому порядку. У зв'язку з цим, ми не зможемо використовувати такі контейнери для, наприклад, пирамидной сортування, а також ми не зможемо за О (1) одержувати доступ до найбільшого і найменшого елементу, як в set і map. І, як наслідок невпорядкованості, ми не зможемо використовувати на цих контейнерах операції lower _ bound і upper _ bound.
Наостанок можу запропонувати кілька завдань, які можна досить легко (порівняно з рішенням без STL) вирішити з використанням цих структур даних:
P.S. розумію, що в статті матеріал розкритий не повністю, хоч я і намагався це зробити. Якщо після прочитання залишилися якісь питання або зауваження, можете їх висловити.
stl. set. map