|
Как вы знаете, в стандартном языке С++ нумерация элементов массива начинается с 0, и использовать отрицательные индексы запрещено. Однако некоторые приложения выиграли бы от применения массива, в котором программисту разрешено задавать разные границы. Рассмотрим плоскость декартовых координат: каждая ось — линия, на которой располагаются и положительные, и отрицательные значения. Удобным способом представления такой линии в программе было бы применение массива, в котором Д°~ пустимы положительные и отрицательные значения индексов. Например* имея отрезок, изменяющийся от —5 до 5, вы могли бы использовать массив, который индексировался бы следующим образом:
Разработанный контейнер типа RangeArray позволяет вам создать такои массив. Более того, вы сможете задавать произвольные верхнюю и нижню»0 границы для индексирования элементов массива.
RangeArray — динамический контейнер, допускающий увеличение массива как в положительном, так и в отрицательном направлениях. В этом отношении он подобен встроенному контейнеру, вектору. Контейнер RangeArray поддерживает все требуемые от последовательного контейнера операции, плюс дополнительную операцию индексирования [] и необязательные функции: at (), push_front (), pop_front () и т. д. Вы можете написать следующий фрагмент кода, иллюстрирующий использование контейнера RangeArray:
// Создается массив с границами от -3 до 4 // и инициализируется с нулевыми значениями. RangeArray<int> ob (-3, 4, 0);
// Присваивает значения от -3 до 4 элементам массива ob. for (int I = -3; I < 5; i++) ob[i] = 1; // ...
COUt « ob[-2] ; //-...
0b[2] = ob[-l] % 2;
Как вы могли догадаться, первая строка конструирует объект типа RangeArray с диапазоном изменения индекса от -3 до 4, каждый элемент объекта инициализирован с нулевым значением. Остальные строки фрагмента кола показывают, что к элементам массива возможен доступ в заданном диапазоне изменения индекса.
Вообще, тип RangeArray позволяет создавать объекты, задавая нижнюю и верхнюю границы массива и значение, применяемое при инициализации каждого его элемента. Другими словами, контейнер RangeArray содержит следующий вариант конструктора: RangeArray (1 owerbound, upperbound, ini tvalue)
После того как массив создан, к нему можно применять операцию индексирования с любым значением индекса из заданного диапазона. Это означает, что разрешены любые значения индекса, включая отрицательные. Поскольку массив типа RangeArray динамический, в него можно вставлять Элементы и удалять их. Эти операции вызывают увеличение или сжатие Массива соответственно. Важно то, что может меняться любая граница массива. Если добавляется элемент с отрицательным значением индекса, то Увеличивается отрицательная часть диапазона. Если же удаляется элемент с положительным значением индекса, то сжимается положительная часть Интервала.
Следует также обратить внимание на то, что реализация контейнера RangeArray намеренно не оптимизирована для повышения производительности. Более того, при разработке программы главным критерием оптимизации была наибольшая ясность и доходчивость кода. Задача приводимого примера — четко продемонстрировать все шаги, необходимые для создания пользовательского контейнера. Для облегчения понимания предлагаемая программа написана достаточно прямолинейно, без хитростей. Работа над ее усовершенствованием может доставить вам удовольствие. Пользовательский контейнер, реализующий массив | с настраиваемым диапазоном
i____________________.____________________________________________________________________________________
// Назовите этот файл га.п. //
#include <iostream> #include <iterator> #include <algorithm> #include <cstdlib> #include <stdexcept>
using namespace std;
// Класс-исключение для RangeArray. class RAExc { string err; public:
RAExc(string e) { err = e;
}
string geterrO { return err; }
11 Контейнер для массива с настраиваемым диапазоном. tetplate<class Т, class Allocator = allocator<T> > class RangeArray { T *arrayptr; // указатель на базовый массив контейнера
unsigned len; // хранит длину контейнера int upperbound; // нижняя граница int lowerbound; // верхняя граница Allocator а; // распределитель памяти public:
// Спецификаторы typedef, необходимые для контейнера.
typedef Т value_type;
typedef Allocator allocator..type;
typedef typename Allocator::reference reference;
typedef typename Allocator::const_reference const_reference;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename Allocator::pointer pointer;
typedef typename Allocator::const_pointer const_pointer;
// Итераторы прямого направления.
typedef T " iterator;
typedef const T * const_iterator;
// Замечание: Этот контейнер не поддерживает итераторы
// обратного направления, но вы можете добавить их, если захотите.
// ***** конструкторы и деструктор *****
// Конструктор, заданный по умолчанию.
RangeArray ()
{
upperbound = lowerbound = 0; len = 0;
arrayptr = a.allocate(0);
}
// Конструирует массив заданного диапазона
//с присваиванием каждому элементу начального значения RangeArray(int low, int high, const T &t);
// Конструирует массив с отсчетом от нуля из num элементов // со значением t. Этот конструктор необходим // для совместимости с библиотекой STL. RangeArray(int num, const T &t=T());
// Конструирует на основе заданного диапазона итераторов. RangeArray(iterator start, iterator stop);
// Копирующий конструктор. RangeArray (const RangeArray &o) ,-
// Деструктор. -RangeArray () ;
// ***** Функции перегрузки операций *****
// Возвращает ссылку на заданный элемент.
Т &operator[](int i)
{
return arrayptr[i - lowerbound];
}
// Возвращает ссылки const на заданный элемент.
const Т fcoperator[](int i) const
{
return arrayptr[i - lowerbound];
}
// Присваивает один контейнер другому. RangeArray &operator=(const RangeArray &o);
// ***** Функции вставки *****
// Вставляет val по адресу p.
iterator insert(iterator p, const T &val);
// Вставляет num копий значения val, начиная с адреса р.
void insert(iterator р, int num, const T &val)
{
for(; num>0; num—) p = insert(p, val) + 1;
}
// Вставляет ряд элементов, заданный start и stop по адресу р.
void insert(iterator р, iterator start, iterator stop)
{
while(start != stop) {
p = insert(p, *start) + 1; start++;
}
}
// ***** Функции очистки *****
// Стирает элемент в р. iterator erase(iterator р);
// Стирает заданный диапазон элементов, iterator erase(iterator start, iterator stop) {
iterator p = end();
for(int i=stop-start; i > 0; i—)
p = erase(start); return p;
}
// ***** функции Push и Pop *****
// Добавляет элемент в конец, void push_back(const T &val) {
insert(end(), val);
}
// Удаляет последний элемент.
void pop_back() {
erase (end 0-1) ;
}
// Добавляет элемент в начало, void push_front(const T &val) {
insert(begin(), val);
}
// Удаляет начальный элемент.
void pop_front()
{
erase(begin());
}
// ***** Функции front() и back() *****
// Возвращает ссылку на первый элемент.
Т &front()
{
return arrayptr[0];
}
// Возвращает ссылку const на первый элемент.
const Т &front() const
{
return arrayptr[0];
}
// Возвращает ссылку на последний элемент.
Т &back()
{
return arrayptr[len-1];
}
// Возвращает ссылку const на последний элемент, const Т &back() const
{
return arrayptr[len-1];
}
// ***** Функции итератора *****
// Возвращает итератор, указывающий на первый элемент.
iterator begin()
{
return &arrayptr[0];
}
// Возвращает итератор, указывающий на последний элемент.
iterator end()
{
return barrayptr[upperbound - lowerbound];
}
// Возвращает итератор const на первый элемент.
const_iterator begin() const
{
return &arrayptr[0];
}
// Возвращает итератор const на последний элемент.
const_iterator end() const
{
return fcarrayptr[upperbound - lowerbound];
}
// ***** Разные функции *****
// Функция at() выполняет проверку выхода за границы. // Возвращает ссылку на заданный элемент. Т &at(int i) {
if(i < lowerbound || i >= upperbound) throw out_of_range("Index Out of Range");
return arrayptr[i - lowerbound];
.}
// Возвращает ссылку const на заданный элемент.
const Т &at(int i) const
{
if(i < lowerbound || i >= upperbound)
throw out_of_range("Index Out of Range");
return arrayptr[i - lowerbound];
}
// Возвращает размер контейнера.
size_type size() const
{
return end() - begin();
}
// Возвращает максимальный размер RangeArray.
size_type max_size()
{
return a.max_size();
}
// Возвращает true, если контейнер пуст.
bool empty()
{
return size() == 0;
}
// Обменивает значения двух контейнеров.
void swap (RangeArray &b)
{
RangeArray<T> tmp;
tmp = *this; *this = b; b = tmp;
}
/ / Удаляет и уничтожает все элементы.
void clear()
{
erase(begin(), end());
}
// ***** He-STL-функции *****
// Возвращает границы, int getlowerbound () {
return lowerbound;
}
int getupperbound () {
return upperbound;
}
};
// ***** Реализации невстроенных функций *****
// Конструирует массив заданного диапазона
//с указанием начального значения каждого элемента.
template <class Т, class А>
RangeArray<T, А>:: RangeArray (int low, int high, const T &t)
{
if (high <= low) throw RAExc ("Invalid Range"); high++;
// Сохраняет границы, upperbound = high; lowerbound = low;
// Выделяет память для контейнера, arrayptr = a.allocate(high - low);
// Сохраняет длину контейнера len = high - low;
// Конструирует элементы. for(size_type i=0; i < size(); i++) a.cons truet(fcarrayptr[ i ], t);
}
// Создает массив с отсчетом от нуля из num элементов //со значением t. Этот конструктор нужен // для совместимости с библиотекой STL. template <class Т, class А>
RangeArray<T, А>::RangeArray(int num, const T &t) {
// Сохраняет границы, upperbound = num; lowerbound = 0;
// Выделяет память для контейнера, arrayptr = а.allocate(num);
// Сохраняет длину контейнера, len = num;
// Формирует элементы. for(size_type i=0; i < size(); i++) a.cons truce(fcarrayptr[ i ], t);
}
// Создает массив с отсчетом от нуля из элементов, заданных // диапазоном итераторов. Этот конструктор нужен для // совместимости с библиотекой STL. template <class Т, class А>
RangeArray<T, А>::RangeArray(iterator start, iterator stop)
// Выделяет требуемую память, arrayptr = a.allocate(stop - start);
{
upperbound = stop - start; lowerbound = 0;
len = stop - start;
// Конструирует элементы, // заданные диапазоном итераторов. for(size_type i=0; i < size(); i++) a.cons truet(fcarrayptr[i], * start++);
}
// Копирующий конструктор, template <class T, class A>
RangeArray<T, A>:: RangeArray (const RangeArray<T, A> &o) {
// Выделяет память для копии, arrayptr = a.allocate(о.size());
upperbound = о.upperbound; lowerbound = о.-lowerbound;
len = o.len;
// Создает копию.
for(size_type i=0; i < size(); i++)
a.cons truet(fcarrayptr[i], о.arrayptr[i]);
}
// Деструктор.
template <class T, class A> RangeArray<T, A>::-RangeArray() {
// Вызывает деструкторы для элементов в контейнере. for(size_type i=0; i < size(); i++) a.destroy(fcarrayptr[i]);
// Освобождает память.
a.deallocate (arrayptr, sizeO);
}
// Присваивает один контейнер другому, template <class Т, class А> RangeArray<T, А> & RangeArray<T, А>::operator=(const RangeArray<T, A> &o) {
// Вызывает деструкторы для элементов в контейнере-приемнике. for(size_type i=0; i < size(); i++) a.destroy(fcarrayptr[i]);
// Освобождает исходную память, a.deallocate(arrayptr, size());
// Выделяет память для нового размера, arrayptr = a.allocate(о.size());
upperbound = o.upperbound; lowerbound = о.lowerbound; len = o.len;
// Создает копию.
for(size_type i=0; i < size(); i++) arrayptr[i] = о.arrayptr[i];
return *this;
}
// Вставляет val в позицию, заданную p.
template <class T, class A>
typename RangeArray<T, A>::iterator
RangeArray<T, A>::insert(iterator p, const T &val)
{
iterator q; size_type i, j;
// Получает необходимую память. T *tmp = a.allocate(size() + 1);
// Копирует существующие элементы в новый массив, t
II если возможно, вставляет новый элемент.
for(i=j=0; i < size(); i++, j++) { if(&arrayptr[i] == p) { tmp[j] = val; q = &tmp[j];
}
tmp[j] = arrayptr[i];
}
// В противном случае новый элемент перемещается в конец. if(p == endO) {
tmptj] = val;
q = &tmp[j];
}
// Корректирует длину len и границы. len++;
if(p < fcarrayptr [abs (lowerbound) ])
lowerbound— ; else
upperbound++;
// Вызывает деструкторы для элементов старого контейнера, for(size_type i=0; i < size()-l; i++) a.des troy(fcarrayptr[i]);
// Очищает память, отведенную для старого контейнера, a.deallocate(arrayptr, size()-l); arrayptr = tmp; return q;
}
// Стирает элемент по адресу p. template <class T, class A> typename RangeArray<T, A>::iterator RangeArray<T, A>::erase(i terator p) {
iterator q = p;
// Уничтожает стертый элемент.
if(p != end()) a.destroy(p);
// Корректирует длину len и границы, len—;
if(p < &arrayptr[abs(lowerbound)])
lowerbound++; else
upperbound—;
// Уплотняет оставшиеся элементы. for( ; p < end(); p++)
*p = *(p+l); return q;
}
// ******** Операции отношения **************
template<class T, class Allocator>
bool operator==(const RangeArray<T. Allocator> &a, const RangeArray<T, Allocator> &b)
{
iЈ(a.size() != b.sizeO) return false; return equal (a.begin(), a.endO, b.beginO);
}
template<class T, class Allocator>
bool operator!=(const RangeArray<T, Allocator> &a, const RangeArray<T, Allocator> &b)
{
if (a. size () != b.sizeO) return true;
return ! equal (a. begin (), a.endO, b.beginO);
}
template<class T, class Allocator>
bool operator<(const RangeArray<T, Allocator> &a.
const RangeArray<T, Allocator> &b) •
{
return lexicographical_compare(а.begin(), а.end(), b.beginO. b.endO);
}
template<class т, class Allocator> bool operator>(const RangeArray<T, Allocator> &a, const RangeArray<T, Allocator> &b)
{
return b < a;
}
template<class T, class Allocator> bool operator<=(const RangeArray<T, Allocator> &a, const RangeArray<T, Allocator> &b)
{
return !(a > b) ;
}
template<class T, class Allocator> bool operator>=(const RangeArray<T, Allocator> &a, const RangeArray<T, Allocator> &b)
{
return ! (a < b) ;
}
Как отмечено в комментариях в начале листинга 8.1, следует весь код поместить в файл с именем ra.h. Он будет использоваться в программах-примерах, приведенных далее.
Код листинга 8.1 содержит два класса. Первый — RAEXC — класс-исключение. Этот тип исключения генерируется, если делается попытка создать объект RangeArray с некорректно заданными границами, например, если нижняя граница больше верхней. Второй — RangeArray — класс контейнера, его мы обсудим подробно в следующих разделах.
|
