Предыдущий пост -
Следующий пост -

std::set

Рубрика: Контейнеры, Дата: 26 May, 2013, Автор:
Tags: ,

std::set – это так называемое множество с уникальными элементами.

Заголовочные файлы:

#include <set>
using std::set;

Рассмотрим конструкторы (Constructs)

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

//тип для сравнения
class comp
{
	bool operator()(const int& a, const int& b)const
	{return a<b;}
};

//функция для сравнения 
bool fncomp(int a, int b){return a<b;}

int main()
{
	//создание пустого множества
	set<int> s;

	//инициализация массивом
	int mas[5]={1,2,3,4,5};
	set<int> s1(mas,mas+5);

	//вызов конструктора копирования
	set<int> s2(s1);

	//инициализация с использованием указателей
	set<int> s3(s2.begin(),s2.end());

	//инициализация с использованием собственного типа для сравнения
	set<int, comp> s4;

	//инициализация с использованием для сравнения
	//указателя на функцию
	bool (*fn_pt)(int,int)=fncomp;
	set<int, bool(*)(int,int)> s5(fn_pt);

	return 0;
}

set::operator=()

Это обычный оператор присваивания, присваивает одно множество другому.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	set<int> s;
	int mass[4]={1,2,3,4};
	set<int> s1(mass,mass+4);

	//выводим размеры множеств
	cout <<"s.size()= "<<s.size()<<endl;//0
	cout <<"s1.size()= "<<s1.size()<<endl;//4
	//присваиваем s s1
	s=s1;
	//выводим снова размеры
	cout <<"s.size()= "<<s.size()<<endl;//4
	cout <<"s1.size()= "<<s1.size()<<endl;//4

	return 0;
}

Теперь рассмотрим итераторы.

Имеется все виды итераторов как прямые так и обратные, константные и не константные. Разберем сейчас прямые и обратные итераторы, не константные.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	//создаем прямой итератор
	set<int>::iterator it;
	//выводим с помощью итератора
	//1 2 3 4
	for(it=s.begin();it!=s.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	//создаем обратный (реверсивный) итератор
	set<int>::reverse_iterator r_it;
	//выводим с помощью реверсивного итератора
	//4 3 2 1
	for(r_it=s.rbegin();r_it!=s.rend();++r_it)
		cout <<*r_it<<' ';
	cout <<endl;

	return 0;
}

Теперь константные итераторы.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	//создаем прямой итератор
	set<int>::const_iterator it;
	//выводим с помощью итератора
	//1 2 3 4
	for(it=s.begin();it!=s.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	//создаем обратный (реверсивный) итератор
	set<int>::const_reverse_iterator r_it;
	//выводим с помощью реверсивного итератора
	//4 3 2 1
	for(r_it=s.rbegin();r_it!=s.rend();++r_it)
		cout <<*r_it<<' ';
	cout <<endl;

	return 0;
}

константные отличаются от не константных тем, что они не могут модифицировать данные.

Рассмотрим емкость (Capacity)

set::empty()

Функция проверяет пустое множество или нет. Если множество пустое, то возвращается true, если нет, то возвращается false.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	if(!s.empty())cout <<"s not empty"<<endl;//s not empty

	return 0;
}

set::size()

Возвращает количество элементов в множестве.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	cout <<"s.size()= "<<s.size()<<endl;//4

	return 0;
}

set::max_size()

Возвращает максимальное количество элементов которое может быть в множестве.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	cout <<"s.max_size()= "<<s.max_size()<<endl;//большое число

	return 0;
}

Модификаторы (Modifiers)

set::insert()

Вставляет элементы в множество.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;
using std::pair;

int main()
{
	//создание пустого множества
	set<int> s;
	//добавляем 10 элементов
	for(int i=0;i<=10;i++)
		s.insert(i*10);

	//создаем пару
	pair<set<int>::iterator,bool> result;
	//создаем инетарор
	set<int>::iterator it;

	result=s.insert(20);
	if(result.second==false)cout <<"element exist"<<endl;

	//вставка массива
	int mass[4]={1,2,3,4};
	s.insert(mass,mass+4);

	//вставка через итератор
	it=s.begin();
	s.insert(it, 35);
	s.insert(it,33);
	s.insert(it,21);

	//вывод содержимого массива
	for(it=s.begin();it!=s.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	return 0;
}

set::erase()

Удаляет элементы с множества.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	set<int> s;

	//добавляем 10 элементов
	for(int i=1;i<=10;i++)
		s.insert(i*10);

	set<int>::iterator it;
	//удаление первого элемента
	it=s.begin();
	it=s.erase(it);//it указывает на второй элемент
	//удаление второго элемента
	it=s.erase(it);//it указывает на 30

	//удаление просто по ключу
	s.erase(60);

	//удаление списка элементов
	it=s.find(70);
	s.erase(it,s.end());

	//вывод оствшихся элементов
	for(it=s.begin();it!=s.end();++it)
		cout <<*it<<' ';
	cout <<endl;

	return 0;
}

set::swap()

Меняет местами множества.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);
	set<int> s1;

	//вывод размеров
	cout <<"s.size()= "<<s.size()<<endl;//4
	cout <<"s1.size()= "<<s1.size()<<endl;//0

	//делаем обмен и выводим размеры
	s.swap(s1);
	cout <<"s.size()= "<<s.size()<<endl;//0
	cout <<"s1.size()= "<<s1.size()<<endl;//4
}

set::clear()

Функция удаляет все элементы с множества.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	int mass[4]={1,2,3,4};
	set<int> s(mass,mass+4);

	//вывод размера
	cout <<"s.size()= "<<s.size()<<endl;//4

	//удаляем все элементы из множества
	s.clear();

	//вывод размера
	cout <<"s.size()= "<<s.size()<<endl;//0

	return 0;	
}

set::emplace и set::emplace_hint

Мы эти функции пока не будем рассматривать это новый стандарт.

Рассмотрим наблюдатели (observers)

set::key_comp()

Функция сравнивает ключи.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	set<int> s;
	//заполняем
	for(int i=0;i<=5;i++)
		s.insert(i);
	//создаем тип на key_compare
	set<int>::key_compare comp=s.key_comp();
	//создаем итератор
	set<int>::iterator it=s.begin();
	//обозначаем минимальное значение
	int max=*s.rbegin();
	//выводим в цикле значение множества
	do
	{
		cout <<*it<<' ';
	}
	while(comp((*it++),max));
	cout <<endl;

	return 0;
}

set::value_comp()

Функция подсчитывает элементы с одинаковыми ключами.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	//создание пустого множества
	set<int> s;
	//заполняем пустое множество
	for(int i=0;i<=5;i++)
		s.insert(i);

	//создаем тип для заполнения
	set<int>::value_compare comp=s.value_comp();
	//создаем итератор
	set<int>::iterator it=s.begin();
	//создаем метку для максимального элемента
	int max=*s.rbegin();

	//вывод в цикле
	do
	{
		cout <<*it<<' ';
	}
	while(comp((*it++),max));
	cout <<endl;

	return 0;
}

Операторы (Operations)

set::find()

Эта функция устанавливает указатель на элемент, значение которого передается функции.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	//создание пустого множества
	set<int> s;

	//заполнение множества
	for(int i=0;i<5;i++)
		s.insert(i);

	//создаем итератор
	set<int>::iterator it;
	it=s.find(3);
	cout <<"*it= "<<*it<<endl;

	it=s.find(4);
	cout <<"*it= "<<*it<<endl;

	return 0;
}

std::count()

Эта функция принимает значение элемента и возвращает количество элементов в множестве. Если данного элемента нет во множестве, то возвращается ноль. Так как set это множество которое не может содержать два одинаковых элемента, то count никогда не вернет значение больше единицы.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	//создание пустого множества
	set<int> s;

	//заполнение множества
	for(int i=0;i<5;i++)
		s.insert(i*2);

	//использование функции count для подсчета количества
	//не уникальных элементов в множестве
	//в set максимум может быть 1
	for(int i=0;i<10;i++)
	{
		if(s.count(i)!=0)
			cout <<"element "<<i<<" in set"<<endl;
		else
			cout <<"element "<<i<<" not in set"<<endl;
	}

	return 0;
}

set::lower_bound() и set::upper_bound()

Эти функции используются для создания границ множества. Щас приведу примерчик как это можно использовать.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	//создание пустого множества
	set<int> s;
	//заполнение пустого множества
	for(int i=0;i<10;i++)
		s.insert(i);
	//создание итераторов для set
	set<int>::iterator itLow, itUp, it;
	itLow=s.lower_bound(3);
	itUp=s.upper_bound(7);
	//выводим, то что находится между границами
	//3 4 5 6 7
	for(it=itLow;it!=itUp;++it)
		cout <<*it<<' ';
	cout <<endl;

	return 0;
}

set::equal_range()

Функция принимает значение элемента и возвращает пару указателей, first указывает на значение элемента, а second  на предыдущий. Это в данном случае. На самом деле функция наверно подсчитывает, количество элементов со значением и сохраняет в пары, где first это начало элементов, а second это тот елемент которому не должен равнятся first.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;
using std::pair;

int main()
{
	//создание пустого множества
	set<int> s;
	//заполняем множество
	for(int i=0;i<10;i++)
		s.insert(i*10);
	//создание пары
	pair<set<int>::iterator,set<int>::iterator> p;
	//подсчитываем эквивалентные элементы
	p=s.equal_range(30);
	//выводим то что у нас имеется в парах
	cout <<*p.first<<' '<<*p.second<<endl;//30 40

	return 0;
}

Рассмотрим аллокатор (Allocator)

set::get_allocator()

Функция выделяет память.

#include <iostream>
using std::cout;
using std::endl;
#include <set>
using std::set;

int main()
{
	//пустое множество
	set<int> s;
	//указатель на область памяти
	int* p;
	p=s.get_allocator().allocate(5);

	//заполняем выделенную память
	for(int i=0;i<5;i++)
	{
		*p=i;
		p++;
	}
	//выведем то что у нас находится по указателю на область
	//памяти p
	for(int i=0;i<5;i++)
		cout <<*p<<' ';
	cout <<endl;

	//удаляем выделенную память
	s.get_allocator().deallocate(p,5);

	return 0;
}

В общем все пока на этом. Теперь рассмотрим multiset.

rss