{quote}
set - множество - хранит упорядоченные по возрастанию элементы в виде дерева каждый ровно один раз
multiset - мультимножество - хранит упорядоченные по неубыванию элементы в виде дерева
каждый элемент может встречаться несколько раз
{quote}
Объявление
{quote}
set<string> s; // множество строк, строки упорядочены по возрастанию
// добавление одинаковых игнорируется
// каждое строка может встречаться один раз
multiset<int, greater<int> > s; // множество чисел, числа упорядочены по убыванию
// одинаковые числа добавляются
// каждое число может встречаться несколько раз
{quote}
Использование
{quote}
s.insert(t) // вставить элемент t в множество s
s.find(t) // найти t в s
проверить, есть ли элемент t во множестве s
нет, если s.find(t)==s.end()
есть, если s.find(t)\!=s.end()
s.end - адрес "сразу за последним элементом "
s.erase(s.find(h)) // найти в s элемент h и удалить его
s.erase(h) // в multiset удаляет все элементы со значением h
s.clear() // удалить все элементы из s
s.empty() // множество пустое?
s.size() // количество элементов в s

\*s.begin() // взять первый - наименьший элемент из s (если элементы хранятся по возрастанию)
// - наибольший элемент из s (если элементы хранятся по убыванию)
\*s.rbegin() // взять последний
\*--s.end() // взять последний - наибольший элемент из s (если элементы хранятся по возрастанию)
// - наименьший элемент из s (если элементы хранятся по убыванию)
// s.end - адрес "сразу за последним элементом"
{quote}
Заметим, что первый, последний элементы и empty берутся за O(1),

а insert, find, erase выполняются за O(LogN)
{code:title=part.cpp|borderStyle=solid}
set <pair< pair<int,int> , pair<int,int> > > s; // множество четвёрок чисел
set <pair< pair<int,int> , pair<int,int> > >::iterator is; // итератор по множеству
for (is=s.begin(); is!=s.end(); is++)
for (is=s.begin(); is!=s.end(); is++)
{
int x1,y1,x2,y2;
x1=is->first.first; // обращение к элементам четвёрки
y1=is->first.second; // с помощью итератора
x2=is->second.first;
y2=is->second.second;
{code}
Задача из курса "Методы алгоритмизации"
Олимпиады по информатике\Стек\07_Rub6 - "aPhone
[http://dl.gsu.by/task.jsp?nid=256579&cid=15]

Решение

Можно симулировать процесс, описанный в условии задачи.

А можно заметить, что если сначала все строки прочитать,
а потом обрабатывать их с конца, то задача может существенно упроститься
Список строк пустой
Пока не обработали все строки
- если текущей строки нет,
Тогда выводим её, и заносим её в список
иначе пропускаем
Довыводим <Empty> если нужно

Для того, чтобы не писать самим процедуры
добавления строки в список проверки и проверки наличия строки в списке
(а также для ускорения этих процедур) можно
определить тип множество строк (set<string> s)
и использовать стандартные функции.
s.insert(t) - вставить строку t в множество s
s.find(t) - проверить, есть ли строка t во множестве s
есть, если s.find(t)==s.end()
{code:title=prog.cpp|borderStyle=solid}
#include <bits/stdc++.h>
using namespace std;
string x[1000];
set<string> s;
int main()
{
freopen("aphone.in","r",stdin);
freopen("aphone.out","w",stdout);
int n,m,i;
cin >> m >> n;
for (i=0; i<n; i++) cin >> x[i];
for (i=n-1; (i>=0) && (m>0); i--)
if (s.find(x[i])==s.end())
{ s.insert(x[i]); cout << x[i] << endl; m--;};
for (i=0; i<m; i++) cout << "<Empty>" << endl;
}
{code}
Подробнее о set
[http://informatics.mccme.ru/mod/book/view.php?id=492&chapterid=215]