Библиотека STL (Standart Template Library)

Источник: cyberguru

STL - Standart Template Library. Стандартная библиотека шаблонов. Эта библиотека представляет большой набор данных структур и алгоритмов. Кстати она разработана, что очень приятно Александром Степановым и Менг Ли работающих в Hewlett-Packard Lab, им помогал Д. Л. Муссер из Ренсселэровского политехнического института. STL - это не просто расширение, недавно он был принят комитетом по стантартизации ANSI/ISO в качестве составляющей стандартной библиотеки C++. STL поддерживает как компилятор Borland, для которого его реализовала Rogue Wave Software так и Microsoft. У STL есть несколько версий. Мы с Вами посмотрим стандартную версию для VC++ Microsoft естественно. В чем же главная идея STL ?. Это уменьшение зависимости от стандартных библиотек С++. Главная беда стандартных библиотек это очень тесная их связь с данными, что делает их очень неудобными для работы с типами данных пользователя. STL позволяет работать с любыми типами данных и производить над ними операции.

Первое главное отличие STL это то, что она отделяет структуры данных от алгоритмов, которые с ними работают. Вторая главная особенность в том, что она не объектно-ориентированная. Это может выглядеть как недостаток, но это наверно не так. Она работает немного на другом уровне. На самом деле объектно-ориентированное программирование это только миф созданный Вашим компилятором. Я совершенно точно гарантирую, что способен написать код, который будет получать доступ к защищеным данным класса откуда угодно. Правда для этого нужно делать вставку на ассемблере. Кроме того код у неё очень компактен.

Пробуем

Сейчас мы с вами с помощью STL решим задачу безразмерного массива целых чисел. Это просто если делать с помощью STL.

Создаем проект Win 32 Console с именем StlStep2 как Hello Word. И пишем код.

 // StlStep2.cpp : Defines the entry point for the console application. #include "stdafx.h"
#include "vector"
#include "iostream.h"
using namespace std;
void main()
{
vector< int > MyArray;
for (int x=0;x < 10;x++)
MyArray.push_back(x); 
vector< int >::iterator i; 
for (i=MyArray.begin(); i!=MyArray.end();++i)
cout << *i << endl; 
}

Ну как ? Много нового? Все новое. Вместе с VC++ поставляються и все необходимые файлы для работы с STL при этом есть некоторые особенности, например, Вы заметили, что при объявлении vector не использовалось расширение *.h. Его можно не использовать, но кроме того его и нет. Данный файл идет без расширения.

Данный пример это просто проба. Для использования STL нам нужно получить некоторые знания, в том числе и теоритические. Вот дальше мы и будет изучать.

Если вы программировали на чистом C и решали подобные задачи, то можете представить какой код нужно написать для подобной задачи. Явно больше.

Пространство имен

Пространство имен namespace это новый элемент языка и для работы с STL мы обязаны принять его во внимание. Этот элемент создан для программ созданых из многих файлов, в которых есть опасность конфликта имен.

Объявляется пространство имен командой namespace:

C++ Спецификация
namespace [идентификатор]
{
описание для этой рабочей области 
}

Для использования рабочей области применяется команда using namespace:

C++ Спецификация
using namespace [идентификатор]

Посмотрим ? Создавайте проект Win32 Console, как Hello Word с именем TestNameSpace. И код. Объявляем различные области.

 // TestNameSpace.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
namespace spaceA
{
int MyVal=10;
}
namespace spaceB
{
int MyVal=10;
}
namespace spaceC
{
int MyVal=10;
}
void main()
{
}

А вот так они используются.

 // TestNameSpace.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
#include "iostream.h"
namespace spaceA
{
int MyVal=10;
}
namespace spaceB
{
int MyVal=20;
}
namespace spaceC
{
int MyVal=30;
}
void Test()
{
using namespace spaceB;
cout << MyVal << " " << "spaceB" << endl;
}
void main()
{
using namespace spaceA;
cout << MyVal << " " << "spaceA" << endl;
Test();
cout << spaceC::MyVal << " " << "spaceC" << endl;
}

Запустите посмотрите результат. Все работает как часы.

Шаблоны функций - основа STL

Можно смело сказать, что основу STL составляют шаблоны. Именно они позволяют значительно сократить количество кода для программирования алгоритмов.

Давайте расмотрим задачу, смысл которой в одинаковых математических расчетах для разных типов. Представьте, что Вам нужно вычислять функцию:

(x*x)-(2*x)

Для типа int и double. Что делается классически ??? Пишутся две функции. Например так:

#include "stdafx.h"
#include "iostream.h"int FuctInt(int x)
{
return (x*x)-(2*x);
}
double FuctDouble(double x)
{
return (x*x)-(2*x);
}
void main()
{
cout << "Int " << FuctInt(25) << endl;
cout << "Double " << FuctDouble(3.12) << endl;
}

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

#include "stdafx.h"
#include "iostream.h"
template 
T fuct(T value)
{
return (value*value)-(2*value);
}
int FuctInt(int x)
{
return (x*x)-(2*x);
}
double FuctDouble(double x)
{
return (x*x)-(2*x);
}
void main()
{
cout << "Int " << FuctInt(25) << endl;
cout << "Double " << FuctDouble(3.12) << endl;
cout << "----------- template ---------------" << endl;
cout << "Int " << fuct(25) << endl;
cout << "Int " << fuct(3.12) << endl;
}

Шаблон начинается словом template, после описания фигурные скобки:

template < [список типов] [, [ список аргументов ]] >
{
реализация функции
return
}

Обратите внимание на return. Это именно шаблон функции, а не шаблон класса.

Шаблоны классов

В прошлый раз я заикнулся про шаблоны классов. Раз сказал надо показать. Шаблоны классов очень сильно похожи на шаблоны функций и решают теже задачи. То есть они помогают производить одинаковые операции с разными типами данных. Давайте прошлый пример переложим на классы:

#include "stdafx.h"
#include "iostream.h"class CFucntInt
{
public:
CFucntInt(int value)
{
x=value;
}
int GetValue()
{
return (x*x)-(2*x);
}
private:
int x;
};
class CFucntDouble
{
public:
CFucntDouble(double value)
{
x=value;
}
double GetValue()
{
return (x*x)-(2*x);
}
private:
double x;
};
void main()
{
CFucntInt cI(25);
CFucntDouble cD(3.12);
cout << "CFunctInt " << cI.GetValue() << endl;
cout << "CFucntDouble " << cD.GetValue() << endl;
}

Ну, а теперь с шаблоном !!!

#include "stdafx.h"
#include "iostream.h"template < class T >
class Funct
{
public:
Funct(T value)
{
x=value;
}
T GetValue()
{
return (x*x)-(2*x);
}
private:
T x;
};
void main()
{
Funct< int > cI(25);
Funct< double > cD(3.12);
cout << "cI " << cI.GetValue() << endl;
cout << "cD " << cD.GetValue() << endl;
}

Ну как ??? Впечатляет ??? Обратите внимание на Funct< int > cI(25); именно здесь задается тип класса. Это немного непревычно.

Компоненты STL

В STL большое количество шаблонов, как классов так и функций. Мы можем их использовать с ООП или без него. Вообщем как хотим. Но в STL есть 3 основные компоненты.

Итераторы
Контейнеры
Алгоритмы

Итератор - это аналог указателя, с помощью них мы можем получать доступ к различных элементам данных. Можно использовать и пару итераторов для задания диапазона. Как и указатель для получения данных из итераторов их необходимо разыменовать с помошью операции *. Всего есть пять классов итераторов.

Входные
Выходные
Однонаправленные
Двунаправленные
Произвольного доступа

Контейнеры - это структуры данных такие как списки, очереди и так далее. Доступ к данным находящимся внутри контейнера осуществляется с помощью итераторов :-) Есть следующие контейнеры. Могу пропустить, так что извините, если что.

vector - линейный массив
list - двухсвязанный список
deque - очередь с двухсторонгим доступом
set - ассоциативный массив уникальных ключей
multiset - ассоциативный массив с возможность дублирования ключей
map - ассоциативный массив с уникальными ключами и значениями
multimap - ассоциативный массив с возможность дублирования ключей и значений
stack - структура данных типа стек
queue - структура данных типа очередь

Алгоритмы - это шаблоны функций, с помощью которых производятся операции по работе с данными. Например сортировки или поиска.

Знакомимся с вектором

Вектор (vector) напоминает нам массив, только он способен расти до произвольного размера, поддерживает информацию о размере. Как и массив к вектору можно обратить воспользовавшись операцией индексирования []. Вот характеристики:

Доступ к данных с одинаковой скоростью
Вставка приводит к перемещению элементов
При расширении данные копируються в другой блок

Как видите вектор оптимален для получения информации, но при большом количестве вставок лучше воспользоваться другими контейнерами, например, списками. Проблема в том, что физически вектор распологается в непрерывной памяти. На C это реализовывали функциями malloc.

Для работы с вектором необходимо подключить заголовочный файл:

#include "vector"

Объявить рабочую область:

using namespace std;

После этого вектор необходимо объявить, это можно сделать двумя способами.

vector< int > vArray1;
vector< int > vArray2(30);

В первом случае указывается пустой вектор, а во втором начальный размер.

Можно получать информацию о параметрах вектора:

size() - сколько данных храниться
capacity() - сколько может храниться до изменения размера
max_size() - максимальный размер обычно равен наиболее большому доступному блоку памяти

Смотрим пример:

 // TestVector.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
#include "vector"
#include "iostream.h"
using namespace std;
void main()
{
vector vArray1;
vector vArray2(30);
cout << "Size Vector " << vArray2.size() << endl;
cout << "Capacity Vector " << vArray2.capacity() << endl;
cout << "Max_Size Vector " << vArray2.max_size() << endl;
for (int x=1;x<5;x++)
vArray2.push_back(10); 
cout << "Size Vector " << vArray2.size() << endl;
cout << "Capacity Vector " << vArray2.capacity() << endl;
cout << "Max_Size Vector " << vArray2.max_size() << endl;
}

А вот результат:

Size Vector 30
Capacity Vector 30
Max_Size Vector 1073741823
Size Vector 34
Capacity Vector 60
Max_Size Vector 1073741823
Press any key to continue

Как видите Size показывает сколько сейчас лежит в векторе чисел. В то время как capacity возвращает инициализированный размер, то есть тот размер, до которого можно добавлять данные без инициализации. Вас не удивило, что размер доступной памяти не изменился ??? Это размер доступного блока, а не всей памяти поэтому он и не изменился.

Дальше о векторе

Я уже говоил о инициализации вектора. В дополнение можно сказать, что вектор можно инициализировать с заранее установленными значениями. Вот пример демонстрирующий и доступ к данным вектора через [].

vector vVec(5,10);
for (int x=0;x < 5;x++)
cout << vVec[x] << endl;

У вектора есть много полезных функций. Например, заполнить часть вектора необходимыми данными. В данном примере первые три элемента заполняются цифрой два:

vVec.assign(3,2); 
for (x=0;x < 5;x++)
cout << vVec[x] << endl;

Можно получить первый и последний элемент вектора, для этого есть функции front() и back().

vVec.assign(5,1);
vVec[0]=0;
vVec[4]=4;
cout << vVec.front() << " " << vVec.back() << endl;

Вставку элемента с перемещением можно сделать функцией insert. Вставка производится в первую позицию с перемещением элементов вниз.

for (x=0;x < 5;x++)
cout << vVec[x] << " "; 
cout << endl;
vVec.insert(vVec.begin(),25);
for (x=0;x < 6;x++)
cout << vVec[x] << " "; 
cout << endl;

Можно поместить число в конец вектора воспользовавшись функцией push_back():

vVec.push_back(99);
for (x=0;x < 7;x++)
cout << vVec[x] << " "; 
cout << endl;

Можно удалить последний элемент с сокращением размера:

vVec.pop_back();
for (x=0;x < vVec.size();x++)
cout << vVec[x] << " "; 
cout << endl;

Для удаления используеться функция erase():

vVec.erase(vVec.begin()+2,vVec.begin()+4 ); 
for (x=0;x < vVec.size();x++)
cout << vVec[x] << " "; 
cout << endl;

Изменяет размер вектора функция resize():

vVec.resize(3);
for (x=0;x < vVec.size();x++)
cout << vVec[x] << " "; 
cout << endl;

Применение алгоритмов к вектору

Одним из алгоритмов является сортировка, вот мы и посмотрим как она работает с вектором. Для сортировки можно применить стандартный алгоритм sort. Для его использования необходимо подключить файл заголовков алгоритмов.

#include "algorithm"

После чего можно сортировать, как весь вектор, так и отдельные его части, что очень приятно.

vector< int > v1(10);
vector< int > v2(10);
for (int x=0;x < v1.capacity() ;x++) v1[x]=10-x;
for (x=0;x < v1.capacity() ;x++) v2[x]=10-x;
for (x=0;x < v1.size();x++) cout << v1[x] << " ";
cout << endl;
for (x=0;x < v2.size();x++) cout << v2[x] << " ";
cout << endl;
cout << "___________ SORT _____________" << endl;
sort(v1.begin(),v1.end());
for (x=0;x < v1.size();x++) cout << v1[x] << " ";
cout << endl;
sort(v2.begin()+1,v2.end()-1);
for (x=0;x < v2.size();x++) cout << v2[x] << " ";
cout << endl;

Я не буду подробно описывать, как работает данная сортировка это относится больше к алгоритмам, но здесь показано, что можно векторы сортировать и с ними работают стандартные алгоритмы.

Наш класс в векторе

На данный момент мы использовали в векторе стандартные классы MFC, а как быть для того, чтобы в вектор можно было пеместить произвольный класс ? Для этого нужно соблюдать ряд условий. Минимальные условия.

Конструктор по умолчанию
Конструктор копий
Деструктор

Давайте реализуем и попробуем.

 // СlassVec.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
#include "vector"
#include "iostream.h"
using namespace std;
class CMyClass
{
public:
CMyClass();  // конструктор по умолчанию 
CMyClass(const CMyClass &my);  // конструктор копий 
CMyClass(int xx,int yy);
~CMyClass();  // деструктор 
int x; 
int y;
};
CMyClass::CMyClass()
{
x=0;
y=0;
}
CMyClass::CMyClass(const CMyClass &my)
{
x=my.x;
y=my.y; 
}
CMyClass::CMyClass(int xx,int yy)
{
x=xx;
y=yy; 
}
CMyClass::~CMyClass()
{
}
void main()
{
vector< CMyClass > v; 
v.push_back(CMyClass(1,1));
v.push_back(CMyClass(2,2));
v.push_back(CMyClass(3,3));
for (int x=0;x < v.size();x++)
cout << v[x].x << " " << v[x].y << endl;
};

Естественно, это только самые базовые возможности. Для полного функционирования потребуется перегрузить достаточное количество операций. Довольно много. Как определить необходимость перегрузки данной операции ? Компилятор сам скажет :-)) в виде error :-). Мы знаем, что вектор может работать с архивом, а наш класс пока не умеет, и сортировка вряд ли будет нормальная пока не определены правила, как определить кто старше или больше !!!

Списки

Для использования списков необходимо подключить заголовочный файл и выбрать область.

#include "list"using namespace std;

Теперь список можно объявлять.

list< int > intList;
list< int > intListTest(3);
list< int > intListInit(3,1);

Сначала я объявляю просто пустой список способный хранить числа, дальше я указываю, что в списке 3 элемента и в последнем случае я еще и нициализирую этот список числом 1.

Количество элементов определяем функцией size():

cout << intListInit.size() << endl;

Можно проверить список на пустоту.

if (intList.empty()) cout << " int List empty " << endl;

Для вставки можно использовать три метода Insert(), push_back(), push_front().

 // testList.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
#include "iostream"
#include "list"
using namespace std;
list< int > intList;
list< int > intListTest(3);
list< int > intListInit(3,1);
void ViewintListInit();
void main()
{
cout << intListInit.size() << endl;
if (intList.empty()) cout << " int List empty " << endl; 
ViewintListInit();
intListInit.push_back(100);
intListInit.push_front(0);
intListInit.insert(intListInit.begin(),55); 
ViewintListInit();
}
void ViewintListInit()
{
copy(intListInit.begin(),intListInit.end(),
ostream_iterator< int >(cout," "));
cout << endl;
}

Из списка можно удалять элементы равные определенному значению.

intListInit.remove(1);
ViewintListInit();

Я немного сумбурно расказываю о списках, и вот по какой причине. Очень многие возможности векторов списков и так далее реализуются через итераторы. А вот про них я и не рассказал. Например, чтобы удалить произвольный элемент списка нужен итератор. Наверно в следующем шаге я остановлюсь на понятии итератор и всё станет проще.

Понимание итератора

Вы должны воспринимать итератор на данный момент, как указатель C++. В общем случае это одно и тоже. Давайте посмотрим как применить алгоритм find к массиву C. Массив это и есть набор указателей вроде как.

 // TestIter.cpp : Defines the entry point for the console application.
// #include "stdafx.h"
#include "iostream.h"
#include "algorithm"
using namespace std;
#define ARRAY_SIZE 10
int Arr[ARRAY_SIZE];
void main()
{
for (int x=0;x < ARRAY_SIZE;x++) Arr[x]=x;
int* rezult=find(Arr,Arr+ARRAY_SIZE,3);
if (rezult==Arr+ARRAY_SIZE)
cout << "Not Found 3 " << endl;
else cout << "Yes 3" << endl;
}

Вот смотрите, мы с вами передали в функцию find два указателя. Указатель начала массива и указатель конца массива. Это и есть как их называют - итераторы. При нахождении вам вернется итератор значения, чтобы проверить, что ничего нет мы проверяем с итератором за концом массива.

Вы уже видели, как используются подобные функции типа begin() и end() для получения начала и конца итераторов. Главный вопрос почему не пользоваться указателями ??? Не получится. Представим массив из структур.

struct A
{
int x;
int y;
char buffer[100];
};В С[100];

Так вот для того, чтобы работать с указателями вы должны делать примерно так.

A* D;
D=D+sizeof(A);

Только так вы можете идти от одной структуры к другой. И теперь самое главное. ЭТО МОЖНО ТОЛЬКО ЕСЛИ СТРУКТУРЫ РАСПОЛОЖЕНЫ ЛИНЕЙНО, то есть одна за другой. Тут же мы получим ограничение на то, что блок памяти должен быть непрерывный. Это очень не удобно и ограничивает размер при наличии памяти. Выход только один ЗАВЕСТИ ОТДЕЛЬНЫЙ МАССИВ С ИТЕРАТОРАМИ(указателями). В нем будут линейно храниться указатели на элементы. Ну и что скажете Вы ? Все равно нужен линейный блок памяти. Нужет только структуры могут быть по размеру очень большими. Даже в моем примере на место данной структуры можно поместить массу указателей. И теперь размер ограничивается непрерывной памятью для указателей. Это намного больше, кроме того сами структуры могут быть рассортированны по всей памяти.

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

Некоторые преимущества класса set

Прежде всего - здравствуйте. Ну, если вы все-таки читаете этот шаг, значит либо вы - Каев Артем, либо Артем счел мой скромный мысленный напряг достойным того, чтобы повесить его в своем разделе, что, конечно же, весьма и весьма приятно.

Итак, класс set. Данный шаг, конечно же, не ставит своей целью охватить все возможности класса. Просто мне хотелось немного поговорить о тех его свойствах, которые кажутся мне интересными и довольно-таки часто оказывались мне полезны.

Но сначала. Возможно, я немного повторю Артема если скажу: set или, говоря языком математики, множество, представляет собой объект, контролирующий произвольной длины последовательность уникальных элементов какого-либо типа. В общем, классический подход ко множеству такой: set используется для хранения неповторяющихся (уникальных) ключей, либо для проверки, есть ли элемент в наборе данных.

Ну, от подобных традиций иногда следует отступать, то есть, конечно же, тогда, когда это может оказаться полезным. Находить новые пути и все такое прочее. Сразу скажу: все элементы, помещенные во множество, оказываются рассортированы в порядке возрастания. Это может оказаться полезным, или же наоборот, но в любом случае необходимо это учитывать.

Я впервые столкнулся со множеством при написании программы, демонстрирующей свойства интерполяционных поленомов. Пользователь должен был вводить точки, а я (то есть програма) - строить графики.

Но вот в чем возникла загвоздочка: в любой функции по опреденению не может быть повторяющихся абсцисс (то есть иксов с разными игреками). Что делать? Писать проверочку ручками (да и сортировать вдобавок!) - брала тоска. Выход я нашел такой (привожу пример, конечно же, сильно упрощенный):

1. Создайте проект Win32 Console Application (пустой). Назовем, например, set_test.

2. В нем создайте два файла: заголовок (set_test.h) и cpp-шник (соответственно, set_test.cpp). Хотя можете, конечно, хранить все в одном: проект маленький.

3. В заголовке (set_test.h) напишите:

#include <set>  // это подключаем класс множеств 
#include <iostream.h>  // консольный ввод/вывод - он нам понадобится 
#include <windows.h> / / для MessageBox - лень задавать вопросы через
// консоль - вы меня поймете 
using namespace std;  // подключаем STL-ное пространство имен - как иначе?  // Это класс точки. Не мудрствуя лукаво, я назвал его stl_point.
// Всякие конструкторы копий мне не нужны - вот и не пишу :) 
class stl_point
{
public:
double x, y;  // собственно, абсцисса и ордината нашей точки
// ну и конструктор, поприветствуем: 
stl_point(double tx=0, double ty=0)
{
x = tx;
y = ty;
}
};
 // Теперь самое интересное. Перегружаем оператор "меньше": 
bool operator<(stl_point first, stl_point second)
{
return first.x < second.x;
}

Что сие значит? Во-первых, почему именно оператор "меньше". Эта прелесть (set) осуществляет все свои сравнения (по крайней мере, при попытке добавить элемент) именно через оператор "меньше". Как узнать, какой оператор перегружать? А вы попробуйте откомпилить проект (когда мы его закончим) без его перегрузки. Выскочит соответствующий error... :) .

Во-вторых, почему именно такая перегрузка. Ну, мне же нужно повторяющиеся иксы откинуть. И вдобавок по их значениям рассортировать. Вот я и заставляю беднягу-компа сравнивать вместо двух классов два икса... поделом... :)

Но закончим с проектом. Пишем cpp-шник:

#include "set_test.h" // подключаем, что уже выстрадалиset <stl_point> set_exact; // наш список точек
int main(void)
{
int x, y;
while(1)
{
  // запрашиваем иксы-игреки 
cout << "Abscissa: ";
cin >> x;
cout << "Ordinate: ";
cin >> y;
  // Теперь пытаемся добавить то, что навводил бедолага-пользователь,
// добавить в set. Выводим отчет о результате.
// Впрочем, на этом остановлюсь подробней. 
if(!set_exact.insert(stl_point(x, y)).second)
cout << "not inserted" << endl << endl;
else
cout << "success" << endl << endl;
}
return 0;
}

Итак, что означает фраза

if(!set_exact.insert(stl_point(x, y)).second)
cout << "not inserted" << endl << endl;
else
cout << "success" << endl << endl;

Во-первых, вызвывается конструктор stl_point(x, y) - в созданный экземпляр класса сразу же кидаются икс с игреком (см. конструктор). Далее. Возвращаемое значение сразу же кидается в set_exact и не запоминается больше нигде:

set_exact.insert(stl_point(x, y))

Метод insert объекта set возвращает простенький объект типа pair:

template
struct pair 
{
typedef T first_type;
typedef U second_type
T first;
U second;
pair();
pair(const T& x, const U& y);
template
pair(const pair& pr);
};

Как видите, pair чем-то подобен моей точке: все, что содержит - это два элемента любого (возможно, одинакового) типа - под загадочными именами first и second. :) Наш же insert в случае удачи возвращает pair(it, true), иначе - pair(it, false). Ну, что такое загадочное it - никогда не интересовался. Наверное, на воткнутый элемент итератор. А вот второй элемент, second, - правда ведь на определенную мысль наталкивает?

Итак, смотрим что там, у second'а внутри. Если элемент воткнулся - радуемся. Нет - гм... Ну я печалиться не буду :)) Компилим проект. Запускаем. Попробуйте ввести элементы с одинаковыми иксами. И наоборот - с одинаковыми игреками. Да и вообще - потестьте :))

Теперь усложняем проект. Смотрите, чем поменялся main:

#include "set_test.h"  // подключаем, что уже выстрадали set set_exact;  // наш список точек 
int main(void)
{
int x, y;
while(1)
{
  // запрашиваем иксы-игреки - здесь пока то же самое 
cout << "Abscissa: ";
cin >> x;
cout << "Ordinate: ";
cin >> y;
  // А с этого места начинается новенькое - опишу ниже
// Итак, проверяем, чегой-то там вставилось или не вставилось 
if(!set_exact.insert(stl_point(x, y)).second)
{
  // Ну, пользователь - существо нежное. Если уж он повторно
// ту же абсциссу ввел, нужно узнать, поменять он хочет значение,
// или же просто пальчик у него почесался 
if(MessageBox(NULL,
"Введенному значению абсциссы уже "
"сопоставлено значение ординаты.\nХотите заменить его "
"новым значением?",
"Неувязочка вышла!",
MB_ICONWARNING / MB_YESNO / MB_DEFBUTTON2) == IDYES)
{
  // Ну, раз уж решили менять значение, для начала, не мудрствуя
// лукаво, удалим старое. Метод erase удаляет из множества
// элемент с каким-то определенным значением. Раз уж в нашем
// множестве ключевую (во всех смыслах) роль играет икс, то на
// игрек я в этом случае чихать хотел. Вы видели конструктор -
// он по дефолту вместо игрека ноль подставляет. Ну и пусть
// себе - элемент все равно будет нужный удален :) 
set_exact.erase(stl_point(x));
  // Напоследок еще раз проверим вставился ли наш элемент
// Увидите, вставился 
if(set_exact.insert(stl_point(x, y)).second)
cout << "success" << endl << endl;
else
cout << "not inserted" << endl << endl;
}
else cout << "not inserted" << endl << endl;
}
else cout << "success" << endl << endl;
  // Теперь пройдем все множество с помощью старичка-итератора
// Смысл в том, что после каждого ввода данных ныне будет
// распечатываться все множество
// О том, что есть итератор, смотри в предыдущем шаге :) 
set::iterator i;
for(i=set_exact.begin(); i!=set_exact.end(); i++)
cout << "x = " << (*i).x << ", y = " << (*i).y << endl;
cout << endl;
}
return 0;
}

Ссылки по теме