Привіт усім! В даній статті розглядається шаблонний клас std::set з бібліотеки C++ STL.
std::set являється контейнером, який може зберігати унікальні елементи у певному порядку. Елементи в контейнері set не можуть бути модифікованими - вони завжди константні, але елементи можуть вставлятися і видалятися. Всередині контейнеру, елементи завжди розміщені у певному порядку, визначеним його спеціальним внутрішнім об'єктом, який призначений для порівняння елементів.
Контейнер std::set зазвичай реалізований у якості бінарного дерева.
Щоб використовувати даний клас, необхідно у файлі, де повинен бути присутній set, вказати наступний рядок:
#include <set> /* файл у якому міститься клас std::set */
Коментар вказувати не обов'язково.
Оголошення класу
template < class T, // set::key_type/value_type (тип елементів)
class Compare = less<T>, // set::key_compare/value_compare (компаратор елементів)
class Alloc = allocator<T> // set::allocator_type (об’єкт виділення)
> class set ;
Методи
iterator set::begin () ;
Повертає ітератор на початок послідовності елементів контейнера.
iterator set::end () ;
Повертає ітератор на не існуючий елемент, який знаходиться за останнім елементом послідовності.
reverse_iterator set::rbegin () ;
Повертає ітератор зворотнього перебору, який вказує на кінець послідовності.
reverse_iterator set::rend () ;
Повертає ітератор зворотнього перебору, який вказує на не існуючий елемент, який знаходиться за першим лементом контейнера.
bool set::empty () const ;
Повертає true, якщо об'єкт класу std::set порожній.
size_type set::size () const ;
Повертає кількість елементів у контейнері.
size_type set::max_size () const ;
Повертає максимально можливий розмір контейнера.
pair<iterator,bool> set::insert (const value_type& val) ;
iterator set::insert (iterator position, const value_type& val) ;
template <class InputIterator> void set::insert (InputIterator first, InputIterator last) ;
Вставляє елементи в послідовність. Варіант з одним параметром, за відсутності елементу з значенням val, спричиняє збільшення послідовності на один елемент з значенням val. У варіантами з двома параметрами, перший параметр призначений для вказування приблизного місця вставки елементу з значенням val, якщо даний елемент ще не присутній у послідовності. Останній варіант призначений для вставки множини елементів у послідовність.
void set::erase (iterator position) ;
size_type set::erase (const value_type& val) ;
void set::erase (iterator first, iterator last) ;
Дані методи видаляють елементи з послідовності. Перший варіант видаляє елемент послідовності, на який вказує ітератор position.
void set::swap (set& x) ;
Даний метод викликає обмін внутрішніми даними між двома контейнерами класу std::set, після чого усі елементи об'єкту x переходять до поточного об'єкту, а елементи з поточного елементу переміщаються до об'єкта x. Після його виклику усі ітератори і вказівники залишаються валідними.
void set::clear () ;
Даний метод спричиняє видалення усіх елементів з поточного об'єкту.
key_compare set::key_comp () const ;
Повертає копію об'єкта порівняння, який використовує поточний контейнер для сортування елементів. Даний метод повертає об'єкт, або вказівник на функцію, який приймає два параметри - елементи які необхідно порівняти. Об'єкт за умовчанням поводить себе як оператор "<".
value_compare set::value_comp () const ;
Повертає копію об'єкта порівняння, який використовує поточний контейнер для сортування елементів.
iterator set::find (const value_type& val) const ;
Виконує пошук у елементах поточного об'єкта класу std::set і повертає ітератор на найдений елемент. Якщо вказаний елемент не присутній в послідовності повертається ітератор аналогічний тому, який повертає метод set::end().
size_type set::count (const value_type& val) const ;
Виконує образунок кількості значень в об'єкті. В зв'язку з тим, що елементи в примірнику даного класу унікальні, даний метод завжди повертає або 1, якщо елемент присутній в послідовності, або 0, якщо ні.
iterator set::lower_bound (const value_type& val) const ;
Повертає ітератор на елемент поточного об'єкту класу set, який повинен повинен бути еквівалентним або більшим за значення val, або ітератор аналогічний ітератору set::end().
iterator set::upper_bound (const value_type& val) const ;
Повертає ітератор на перший елемент, який повинен розміщуватись за елементом з значенням val.
pair<iterator,iterator> set::equal_range (const value_type& val) const ;
Повертає пару ітераторів, які обмежують проміжок, в який заключені елементи з еквівалентним до val значенням. Оскільки елементи в примірниках шаблону унікальні, метод повертає проміжок, який об'єднує максимум один елемент.
allocator_type set:: get_allocator () const ;
Повертає копію об'єкта, який використовується поточним об'єктом для створення примірників послідовності.
Приклади
Приклад #1
Розглянемо приклад використання основних методів контейнера set - додавання, видалення і перебір елементів.
#include <iostream> /* ввід/вивід (об'єкт cout) */
#include <set> /* файл у якому міститься клас std::set */
using namespace std ; /* друкуємо set без std */
/* головна функція програми */
int main (int argc, char** argv)
{
/* створюємо об'єкт множини,
** який буде містити елементи типу вбудованого типу int */
set<int> s1 ;
/* вставляємо в множину елементи за допомогою методу insert
** об'єкт сам приймає рішення, як розмістити елементи по порядку
** відносно внутнішніх встановлених об'єктів порівняння */
s1.insert (1) ;
s1.insert (3) ;
s1.insert (5) ;
s1.insert (7) ;
/* створюємо масив, значення якого перенесемо у об'єкт s1 */
int iArray [] = {11, 13, 17, 19} ;
/* вставляємо в множину декілька елементів,
** які містяться в масиві цілих знакових чисел */
s1.insert (iArray, /* адреса початку масиву */
iArray + sizeof(iArray)/sizeof(iArray[0])) ; /* розраховуємо адресу
** кінцевого елементу */
/* для наглядності */
cout << "s1: " ;
for (set<int>::iterator iter=s1.begin() ; /* створюємо ітератор на початок множини */
iter!=s1.end() ; /* не виходимо за межі послідовності */
++iter) /* інкремент ітератора */
{
/* виводимо у термінал значення,
** на яке вказує ітератор iter в даний момент,
** через синтаксичну конструкцію
** на подобі розйменування звичайного вказівника */
cout << *iter << "; " ;
}
cout << endl ;
/* видаляємо перший елемент з множини */
s1.erase (s1.begin()) ;
/* видаляємо підмножину елементів */
s1.erase (s1.find(5), s1.find(11)) ;
/* видаляємо елемент з значенням 17 */
s1.erase (17) ;
cout << "s1: " ;
/* виводимо результат видалень у термінал */
for (set<int>::iterator iter=s1.begin() ; iter!=s1.end() ; ++iter)
{ cout << *iter << "; " ; }
cout << endl ;
return 0 ;
}
Даний код виведе на термінал наступні дані:
Приклад #2
Розглянемо приклад, в якому Я найчастіше використовую клас set — це наділяння об'єктам створених мною класів певних характеристик. В даному випадку характеристика об'єкта зберігається у об'єктах класу string, тобто рядок символів.
#include <iostream> /* ввід/вивід (об'єкт cout) */
#include <string> /* рядковий тип */
#include <set> /* файл у якому міститься клас std::set */
using namespace std ; /* друкуємо set без std */
/* клас який призначений для
** утримання параметрів товару */
class goods
{
public :
/* метод повертає посилання (reference)
** на об'єкт g_name, який віображає ім'я товару */
string& name () ;
/* методи для управління характеристиками товару */
void add_property (string prop) ; /* додаємо нову властивість */
bool has_property (string prop) ; /* перевіряємо присутність властивості */
void del_property (string prop) ; /* видаляємо властивість з товару */
/* методи делегати */
set<string>::iterator begin () ;
set<string>::iterator end () ;
/* інформація у термінал */
void print () ;
/* конструктори для ініціалізації об'єкта */
goods () ; /* звичайний конструктор без параметрів */
goods (string name) ; /* конструктор встановлює ім'я */
goods (string name, set<string> props) ; /* конструктор встановлює ім'я і параметри */
~goods () ; /* деструктор об'єкта */
private:
/* поля класу */
string g_name ; /* містить ім'я товару */
set<string> g_props ; /* містить властивості товару */
} ;
/*
** реалізвуємо методи класу goods
*/
string& goods :: name ()
{ return g_name ; }
void goods :: add_property (string prop)
{
/* якщо назва властивості не пуста
** додаємо її до поточних */
if (prop.size()>0)
{ g_props.insert (prop) ; }
}
bool goods :: has_property (string prop)
{
/* виконуємо пошук у властивостях товару
** за допомогою find,
** якщо елемент знайдено у послідовності (тобто find повернула
** ітератор, який не вказує на кінець послідовності) -
** повертаємо значення true*/
return ( g_props.find (prop) != g_props.end () ) ;
}
void goods :: del_property (string prop)
{ g_props.erase (prop) ; }
/* методи делегати */
set<string>::iterator goods :: begin ()
{ return g_props.begin () ; }
set<string>::iterator goods :: end ()
{ return g_props.end () ; }
void goods :: print ()
{
/* виводимо основну інформацію на екран */
cout << "Name: " << name() << endl << "Properties: " ;
for (set<string>::iterator iter=begin();
iter!=end();
++iter)
{ cout << *iter << "; " ; }
cout << endl ;
}
goods :: goods ()
{}
goods :: goods (string name)
{ g_name = name ; }
goods :: goods (string name, set<string> props)
{
g_name = name ;
g_props.insert (props.begin(), props.end()) ;
}
goods :: ~goods ()
{}
/* головна функція програми */
int main (int argc, char** argv)
{
/* множина для характеристик за умовчанням
** для продуктів харчування */
set<string> defprops ;
/* додаємо ознаки до множини за умовчанням*/
defprops.insert (string("fresh")) ; /* продукт свіжий */
defprops.insert (string("delitious")) ; /* продукт смачний */
/* створюємо два примірника класу goods -
** перший з назвою "Potato 1" і інший "Tomato 1"
** так як це продукти ініціалізуємо їхні властивості у
** значення за умовчанням */
goods potato (string("Potato 1"), defprops) ,
tomato (string("Tomato 1"), defprops) ;
/* додамо окремі унікальні характеритики до
** кожного об'єкта-продукта */
potato.add_property (string("brown")) ; /* картоплина коричнева */
tomato.add_property (string("berry")) ; /* томат ягода */
/* видалимо властивість fresh з об'єкта potato */
potato.del_property (string("fresh")) ;
/* виводимо основну інформацію про наявні товари */
potato.print () ;
tomato.print () ;
return 0 ;
}
Після запущення програми на виконання ми можемо отримати наступний результат:
В даному прикладі ми створили клас "goods", який призначений для зберігання ім'я товару і його характеристик. В якості контейнера для характеристик ми обрали клас set, тому що нам не важливі індекси характеристик (які є у масивах чи векторах), нам важлива сама характеристика товару. В якій послідовності вона буде розміщеною не важливо. Хоча в даному випадку set виконує деяку оптимізацію совоїм порядком - у сортованій послідовності пошук відбувається набато швидше ніж не у сортованій. В головній функції програми створено два примірника класу "goods": "potato" і "tomato", на яких ми і продемонстрували усю потужність методів цього класу.
Резюме
Шаблонний клас std::set являється хорошим контейнером для збереження відсортованих унікальних елементів. Дозволяє швидко виконувати пошук в множині своїх елементів завдяки своїй внутрішній структурі і простий у використанні. Запобігає всю ручну тяганину з управлінням пам'яті.