Одной из проблем изучения языка C++, на мой взгляд, является то, что он предназначен для структурирования значительных объёмов текста программы. В силу этого любой пример, который может быть размещён на страницах печатного издания оказывается надуманным, так как показываются "рамки картины" без реального содержания.
Здесь Вашему вниманию предлагается пример программы, в которой демонстрируется несколько приёмов программирования. При относительно небольшом объёме эта программа построена с применением технологии умных указателей, абстрактных классов и STL контейнеров. Кроме того, задача "боевая", количество "натяжек" в её формулировке сведено к минимуму.
При написании программы проведения кубического сплайна через заданный набор точек возникла подзадача нахождения отрезка, которому принадлежит данная точка. При условии что отрезки лежат без свободных мест между ними.
"По месту" задача была решена методом дихотомии. Ниже приведён фрагмент, реализующий данный алгоритм.
Но не давало покоя следующее: мне пришлось руками реализовывать низкоуровневый алгоритм, уже имеющийся в стандартной библиотеке. Встал вопрос: насколько велика цена, которую нужно заплатить, для того чтобы воспользоваться алгоритмом, прописанным в стандартной библиотеке.
Известно, что в контейнере set стандартной библиотеки элементы хранятся отсортированными, что делает несколько более дорогим добавление нового элемента, но удешевляет проверку наличия элемента. Причём для упорядочения и проверки на равенство используется оператор "меньше". Отсюда вытекает план действий: нужно оформить отрезок и точку так, чтобы они выглядели одинаково с точки зрения контейнера set, ввести операцию сравнения (точка меньше отрезка, если она меньше его концов). После чего достаточно хранить в set набор отрезков и по заданной точке искать равный элемент. Если он будет найден, именно ему принадлежит точка.
Данная задача решается проще, если считать точку отрезком нулевой длины (сам не додумался, спасибо Михаилу Зубову). Так что программа написана из предположения необходимости хранить точку и отрезок в разных классах.
double
CPolyStorage::Val(double x)const
{
if(!dat.size()) throw(string("No Elements"));
size_t a=0,b=dat.size()-1,c=(a+b)/2;
if(!(dat[a]<x))
return dat[a].Val(x);
if(dat[b]<x)
return dat[b].Val(x);
while(a!=c&&b!=c)
{
if(dat[c]<x)
a=c;
else
b=c;
c=(a+b)/2;
}
if(!(dat[a]<x))
return dat[a].Val(x);
return dat[b].Val(x);
}
#include <iostream>
#include <set>
using namespace std;
class CPoint;
class CPoly;
//Интерфейс хранимых объектов. Их можно сравнивать, делать копию и выводить в поток.
//Так как в умном указателе хранится обычный указатель на интерфейс,
//для осуществления сравнения необходимо восстановить реальный тип объекта.
//Это делается с помощью техники двойной диспетчеризации.
class CStorableInterface
{
public:
virtual bool operator<(const CStorableInterface&)const=0;//Можем писать < между объектами, первый шаг.
virtual bool operator>(const CPoly&)const=0;//Второй шаг.
virtual bool operator>(const CPoint&)const=0;//Второй шаг.
virtual CStorableInterface *Clone(void)const=0;//Не зная настоящего типа объекта можем создать его копию.
virtual ostream& operator>>(ostream&)const=0;//Можем вывести объект в поток.
};
//Отрезок. Изначально имелся в виду полином на отрезке, поэтому называется так.
class CPoly:public CStorableInterface
{
double a,b;//Левый и правый концы отрезка.
public:
CPoly(double xa=0,double xb=0):a(xa),b(xb){}//Отрезок по двум концам.
virtual bool operator<(const CStorableInterface &r)const{return r>*this;}//Первый шаг диспетчеризации. Знаем левый аргумент, кидаем его направо.
virtual bool operator>(const CPoint&r)const;//Второй шаг, собственно сравниваем.
virtual bool operator<(const CPoint&r)const;
virtual bool operator>(const CPoly&r)const;
virtual ostream& operator>>(ostream& os)const{return os<<"("<<a<<","<<b<<")"<<endl;}
virtual CPoly* Clone(void)const{return new CPoly(*this);}
};
//Точка.
class CPoint:public CStorableInterface
{
double val;
public:
CPoint(double xval=0):val(xval){}
double getVal(void)const{return val;}
bool operator<(const CStorableInterface& r)const{return r>*this;}//То же, что и в отрезке.
bool operator>(const CPoly& r)const{return r<*this;}
bool operator>(const CPoint& r)const{return val>r.val;}
virtual CPoint *Clone(void)const{return new CPoint(*this);}
virtual ostream& operator>>(ostream& os)const{return os<<val<<endl;}
};
//Определить можем только здесь, так как необходимо вызывать функцию из класса точки.
bool CPoly::operator>(const CPoly&r)const{return a>r.a&&b>r.a;}
bool CPoly::operator>(const CPoint&r)const{return r.getVal()<a&&r.getVal()<b;}
bool CPoly::operator<(const CPoint&r)const{return a<r.getVal()&&b<r.getVal();}
//Умный указатель, который можно хранить в std контейнере.
class CStorable
{
CStorableInterface &dat;//Ссылка символизирует то, что время жизни указателя и его содержимого совпадают.
//В противном случае стоял бы указатель.
public:
CStorable(CStorableInterface *pDat):dat(*pDat){}//Родился, сразу связываем.
CStorable(const CStorable& r):dat(*r.dat.Clone()){}//Клонирование.
virtual ~CStorable(){delete &dat;}//Конец жизненного пути.
virtual bool operator<(const CStorable&r)const{return dat<r.dat;}//Сравнение. Перекидываем "горячую картошку" хранимым объектам.
virtual ostream& operator>>(ostream& os)const{return dat>>os;}//Вывод в поток.
};
ostream& operator<<(ostream& os,const CStorable &cs){return cs>>os;}//Удобный вывод в поток.
//Множество хранимых объектов
typedef set<CStorable> SS;
typedef SS::iterator SSI;
typedef SS::const_iterator SSCI;
//Тестирующая программа
int main()
{
//Создаём набор отрезков
SS sam;
sam.insert(CStorable(new CPoly(1,2)));
sam.insert(CStorable(new CPoly(2,2.5)));
sam.insert(CStorable(new CPoly(2.5,3)));
sam.insert(CStorable(new CPoly(3,6)));
SSCI b,e,pe;//Начало, конец, позиция перед концом
b=sam.begin(),pe=e=sam.end();
--pe;
double d;
while(cin>>d)//Если и пока успешно считали... Ctrl+Z - конец файла, ввода, программы.
{
CStorable pp(new CPoint(d));//Упаковка точки в сеъдобную для множества оболочку.
SSCI it=sam.find(pp);//Ищем
if(it==e) //не находим
{
cout<<d<<" not found"<<endl;
if((*pe)<pp) cout<<d<<" lay in right of "<<(*pe)<<endl;
if(!((*b)<pp)) cout<<d<<" lay in left of "<<(*b)<<endl;
}
else
cout<<d<<" lay in "<<(*it)<<endl;//Находим
}
}