|
typedef unsigned int nat; #ifdef ARRAY_TEST void outOfRange ( const char * name, nat size, nat index ); #endif #define CCArrRef const CArrRefШаблон классов CArrRef представляет собой ссылку на константный массив: template <class T> class CArrRef
{
void operator= ( CCArrRef & );
protected:
union { const T * con; T * var; } _data;
nat _size;
public:
CArrRef () : _size(0) { _data.con = 0; }
CArrRef ( const T * d, nat n ) : _size(n) { _data.con = d; }
CArrRef ( CCArrRef<T> & a ) : _data(a._data), _size(a._size) {}
// Указатель на i-ый элемент:
const T * operator() ( nat i = 0 ) const { return _size > i ? _data.con + i : 0; }
#ifdef ARRAY_TEST
void error ( nat n, nat i ) const { outOfRange ( "CArrRef", n, i ); }
CArrRef ( CCArrRef<T> & a, nat i, nat n ) : _size(n) { _data.con = a(i); if ( a._size < i + n ) error ( a._size, i + n ); }
// Ссылка на i-ый элемент:
const T & operator[] ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.con[i]; }
// Ссылка на i-ый элемент от конца:
const T & las ( nat i = 0 ) const { if ( _size <= i ) error ( _size, i ); return _data.con[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
const T & cprev ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.con[i>0 ? i-1:_size-1]; }
const T & cprev ( nat i, nat k ) const { if ( _size <= i ) error ( _size, i ); return _data.con[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
const T & cnext ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.con[i+1<_size?i+1:0]; }
const T & cnext ( nat i, nat k ) const { if ( _size <= i ) error ( _size, i ); return _data.con[(i+k)%_size]; }
#else
CArrRef ( CCArrRef<T> & a, nat i, nat n ) : _size(n) { _data.con = a(i); }
// Ссылка на i-ый элемент:
const T & operator[] ( nat i ) const { return _data.con[i]; }
// Ссылка на i-ый элемент от конца:
const T & las ( nat i = 0 ) const { return _data.con[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
const T & cprev ( nat i ) const { return _data.con[i>0 ? i-1:_size-1]; }
const T & cprev ( nat i, nat k ) const { return _data.con[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
const T & cnext ( nat i ) const { return _data.con[i+1<_size?i+1:0]; }
const T & cnext ( nat i, nat k ) const { return _data.con[(i+k)%_size]; }
#endif
// Количество элементов
nat size () const { return _size; }
};
Шаблон классов MutCArrRef представляет собой изменяемую ссылку на константный массив:
template <class T> class MutCArrRef : public CArrRef<T>
{
void operator= ( const MutCArrRef & );
public:
void reset ( CCArrRef<T> & a )
{
_data.con = a();
_size = a.size();
}
};
Шаблон классов ArrRef представляет собой ссылку на неконстантный массив:
template <class T> class ArrRef : public CArrRef<T>
{
public:
ArrRef () {}
ArrRef ( T * d, nat n ) : CArrRef<T>( d, n ) {}
CCArrRef<T> & operator * () const { return *this; }
// Указатель на i-ый элемент:
T * operator() ( nat i = 0 ) { return _size > i ? _data.var + i : 0; }
const T * operator() ( nat i = 0 ) const { return _size > i ? _data.var + i : 0; }
#ifdef ARRAY_TEST
void error ( nat n, nat i ) const { outOfRange ( "ArrRef", n, i ); }
ArrRef ( ArrRef<T> a, nat i, nat n ) : CArrRef<T>( a(i), n ) { if ( a._size < i + n ) error ( a._size, i + n ); }
// Ссылка на i-ый элемент:
T & operator[] ( nat i ) { if ( _size <= i ) error ( _size, i ); return _data.var[i]; }
// Ссылка на i-ый элемент от конца:
T & las ( nat i = 0 ) { if ( _size <= i ) error ( _size, i ); return _data.var[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
T & cprev ( nat i ) { if ( _size <= i ) error ( _size, i ); return _data.var[i>0 ? i-1:_size-1]; }
T & cprev ( nat i, nat k ) { if ( _size <= i ) error ( _size, i ); return _data.var[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
T & cnext ( nat i ) { if ( _size <= i ) error ( _size, i ); return _data.var[i+1<_size?i+1:0]; }
T & cnext ( nat i, nat k ) { if ( _size <= i ) error ( _size, i ); return _data.var[(i+k)%_size]; }
// Ссылка на i-ый элемент:
const T & operator[] ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.var[i]; }
// Ссылка на i-ый элемент от конца:
const T & las ( nat i = 0 ) const { if ( _size <= i ) error ( _size, i ); return _data.var[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
const T & cprev ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.var[i>0 ? i-1:_size-1]; }
const T & cprev ( nat i, nat k ) const { if ( _size <= i ) error ( _size, i ); return _data.var[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
const T & cnext ( nat i ) const { if ( _size <= i ) error ( _size, i ); return _data.var[i+1<_size?i+1:0]; }
const T & cnext ( nat i, nat k ) const { if ( _size <= i ) error ( _size, i ); return _data.var[(i+k)%_size]; }
#else
ArrRef ( ArrRef<T> a, nat i, nat n ) : CArrRef<T>( a(i), n ) {}
// Ссылка на i-ый элемент:
T & operator[] ( nat i ) { return _data.var[i]; }
// Ссылка на i-ый элемент от конца:
T & las ( nat i = 0 ) { return _data.var[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
T & cprev ( nat i ) { return _data.var[i>0 ? i-1:_size-1]; }
T & cprev ( nat i, nat k ) { return _data.var[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
T & cnext ( nat i ) { return _data.var[i+1<_size?i+1:0]; }
T & cnext ( nat i, nat k ) { return _data.var[(i+k)%_size]; }
// Ссылка на i-ый элемент:
const T & operator[] ( nat i ) const { return _data.var[i]; }
// Ссылка на i-ый элемент от конца:
const T & las ( nat i = 0 ) const { return _data.var[_size-1-i]; }
// Ссылка на предыдущий элемент в цикле:
const T & cprev ( nat i ) const { return _data.var[i>0 ? i-1:_size-1]; }
const T & cprev ( nat i, nat k ) const { return _data.var[(i+_size-k)%_size]; }
// Ссылка на следущий элемент в цикле:
const T & cnext ( nat i ) const { return _data.var[i+1<_size?i+1:0]; }
const T & cnext ( nat i, nat k ) const { return _data.var[(i+k)%_size]; }
#endif
// Операторы присваивания
ArrRef & operator= ( CCArrRef<T> & p )
{
const nat n = _min ( _size, p.size() );
for ( nat i = 0; i < n; ++i ) _data.var[i] = p[i];
return *this;
}
ArrRef & operator= ( const ArrRef & a )
{
return *this = *a;
}
// Изменение порядка следования элементов на обратный
ArrRef & reverse ()
{
if ( _size < 2 ) return *this;
const nat n = _size - 1;
const nat m = _size / 2;
for ( nat i = 0; i < m; ++i ) _swap ( _data.var[i], _data.var[n-i] );
return *this;
}
// Заполнение всех элементов заданным значением
ArrRef & fill ( const T & t )
{
for ( nat i = 0; i < _size; ++i ) _data.var[i] = t;
return *this;
}
// Выполнение оператора <= для всех элементов массива
template <class S> ArrRef & operator << ( S & s )
{
for ( nat i = 0; i < _size; ++i ) _data.var[i] <= s;
return *this;
}
};
Шаблон классов FixArrRef представляет собой ссылку на массив постоянной длины:
template <class T, nat n> class FixArrRef : public ArrRef<T>
{
protected:
FixArrRef ( T * d ) : ArrRef<T>( d, n ) {}
public:
explicit FixArrRef ( ArrRef<T> a, nat i = 0 ) : ArrRef<T> ( a, i, n ) {}
FixArrRef & operator= ( const FixArrRef & a )
{
for ( nat i = 0; i < n; ++i ) _data.var[i] = a[i];
return *this;
}
FixArrRef & operator+= ( const FixArrRef & a )
{
for ( nat i = 0; i < n; ++i ) _data.var[i] += a[i];
return *this;
}
FixArrRef & operator-= ( const FixArrRef & a )
{
for ( nat i = 0; i < n; ++i ) _data.var[i] -= a[i];
return *this;
}
friend inline void _swap ( FixArrRef & a1, FixArrRef & a2 )
{
for ( nat i = 0; i < n; ++i ) _swap ( a1[i], a2[i] );
}
};
Шаблон классов FixArray представляет собой массив постоянной длины:
template <class T, nat n> class FixArray : public FixArrRef<T>
{
T stor[n];
FixArray ( const FixArray & );
public:
FixArray () : FixArrRef<<T, n> ( stor ) {}
FixArray & operator= ( const FixArray & a )
{
for ( nat i = 0; i < n; ++i ) stor[i] = a.stor[i];
return *this;
}
FixArray & operator+= ( const FixArray & a )
{
for ( nat i = 0; i < n; ++i ) stor[i] += a[i];
return *this;
}
FixArray & operator-= ( const FixArray & a )
{
for ( nat i = 0; i < n; ++i ) stor[i] -= a[i];
return *this;
}
FixArray & operator*= ( const T & t )
{
for ( nat i = 0; i < n; ++i ) stor[i] *= t;
return *this;
}
// Заполнение всех элементов заданным значением
FixArray & fill ( const T & t )
{
ArrRef<T>::fill ( t );
return *this;
}
};
Шаблон классов DynArrRef предназначен для создания ссылок на массивы с изменяемым размером.
Размер массива меняется при помощи виртуальной функции resize:
template <class T> class DynArrRef : public ArrRef<T>
{
protected:
DynArrRef ( T * d, nat n ) : ArrRef<T>( d, n ) {}
public:
virtual DynArrRef & resize ( nat n = 0 ) = 0;
DynArrRef & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
if ( _size != r.size() ) resize ( r.size() );
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
DynArrRef & operator= ( const DynArrRef & a )
{
return *this = *a;
}
};
Шаблон классов DynArray предназначен для создания динамических массивов, т.е. они могут менять свой размер
во время выполнения программы. В его конструкторе можно указать к-во элементов.
Функция-член resize меняет размер массива на указанный, при этом значения элементов теряются, даже в случае,
когда новый размер равен предыдущему.
Дружественная функция _swap меняет содержимое двух массивов.
template <class T> class DynArray : public DynArrRef<T>
{
DynArray ( const DynArray & );
public:
explicit DynArray ( nat n = 0 ) : DynArrRef<T> ( n > 0 ? new T[n] : 0, n ) {}
explicit DynArray ( CCArrRef<T> & r ) : DynArrRef<T> ( new T[r.size()], r.size() )
{
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
}
~DynArray () { delete[] _data.var; }
DynArray & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
if ( _size != r.size() ) resize ( r.size() );
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
DynArray & operator= ( const DynArray & a )
{
return *this = *a;
}
virtual DynArrRef<T> & resize ( nat n = 0 )
{
delete[] _data.var;
_data.var = 0; // на случай исключения в new
if ( ( _size = n ) > 0 ) _data.var = new T[n];
return *this;
}
DynArray & swap ( DynArray & a )
{
_swap ( _size, a._size );
_swap ( _data, a._data );
return *this;
}
friend inline void _swap ( DynArray & a1, DynArray & a2 )
{
a1.swap ( a2 );
}
};
Шаблон CmbArray является комбинированным массивом, т.е. в зависимости от размера его элементы
могут находится в стеке или в "куче". Параметр шаблона N определяет размер встроенного массива.
Заметим, что в предыдущем шаблоне DynArray функция-член resize всегда вызывает для старых элементов массива деструктор,
а для новых элементов - конструктор. Для шаблона CmbArray это происходит не всегда. Например, если размеры
массива меняются в пределах N, то значения элементов не меняются.
template <class T, nat N> class CmbArray : public DynArrRef<T>
{
T stor[N];
CmbArray ( const CmbArray & );
public:
explicit CmbArray ( nat n = 0 ) : DynArrRef<T> ( n > N ? new T[n] : stor, n ) {}
explicit CmbArray ( CCArrRef<T> & r ) : DynArrRef<T> ( r.size() > N ? new T[r.size()] : stor, r.size() )
{
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
}
~CmbArray () { if ( _data.var != stor ) delete[] _data.var; }
CmbArray & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
resize ( r.size() );
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
CmbArray & operator= ( const CmbArray & a )
{
return *this = *a;
}
CmbArray & operator -= ( const CmbArray & a )
{
const nat n = _min ( _size, a._size );
for ( nat i = 0; i < n; ++i ) _data.var[i] -= a[i];
return *this;
}
virtual DynArrRef<T> & resize ( nat n = 0 )
{
if ( _size == n ) return *this;
if ( _data.var != stor )
{
delete[] _data.var;
_data.var = stor;
}
if ( ( _size = n ) > N ) _data.var = new T[_size];
return *this;
}
};
Шаблон классов SuiteRef предназначен для создания ссылок на последовательные наборы однотипных элементов.
Функция-член add добавляет в конец массива указанный элемент. Функция-член inc ( increase ) без параметра увеличивает размер набора на 1 и возвращает ссылку на добавленный элемент. Функция-член inc ( increase ) с параметром увеличивает размер набора на величину параметра. Функция-член dec ( decrease ) уменьшает размер набора на n ( по умолчанию на 1 ). Функция-член del удаляет указанный элемент. Если он не последний в наборе, то его место занимает последний элемент. Функция-член delAndShift удаляет указанный элемент, а стоящие после него элементы сдвигает на одну позицию. Функция-член addAftLas добавляет множество элементов в конец набора. template <class T> class SuiteRef : public DynArrRef<T>
{
SuiteRef ( const SuiteRef & );
void _del ( nat i )
{
if ( i < --_size ) _data.var[i] = _data.var[_size];
}
virtual void resizeAndCopy ( nat n ) = 0;
protected:
nat real_size;
SuiteRef ( T * d, nat n ) : DynArrRef<T>( d, n ) {}
public:
SuiteRef & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
resize ( r.size() );
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
SuiteRef & operator= ( const SuiteRef & a )
{
return *this = *a;
}
virtual DynArrRef<T> & resize ( nat n = 0 )
{
if ( n > real_size ) resizeAndCopy ( n );
else _size = n;
return *this;
}
SuiteRef & add ( const T & t )
{
inc() = t;
return *this;
}
SuiteRef & addIfHasNot ( const T & t )
{
for ( nat i = 0; i < _size; ++i ) if ( _data.var[i] == t ) return *this;
inc() = t;
return *this;
}
T & inc ()
{
if ( _size == real_size ) resizeAndCopy ( _size + 1 );
else ++_size;
return _data.var[_size-1];
}
SuiteRef & inc ( nat n )
{
if ( _size + n > real_size ) resizeAndCopy ( _size + n );
else _size += n;
return *this;
}
SuiteRef & dec ( nat n = 1 )
{
_size = _size > n ? _size - n : 0;
return *this;
}
SuiteRef & del ( nat i )
{
if ( i < _size ) _del ( i );
#ifdef ARRAY_TEST
else outOfRange ( "SuiteRef::del", _size, i );
#endif ARRAY_TEST
return *this;
}
SuiteRef & delAndShift ( nat i )
{
if ( i < _size )
{
--_size;
#if _MSC_VER > 1200 // MS VC 6.0
for ( ; i < _size; ++i ) copyFunc ( _data.var[i], _data.var[i+1] );
#else
for ( ; i < _size; ++i ) _data.var[i] = _data.var[i+1];
#endif
}
#ifdef ARRAY_TEST
else outOfRange ( "SuiteRef::delAndShift", _size, i );
#endif ARRAY_TEST
return *this;
}
SuiteRef & addAftLas ( CCArrRef<T> & a )
{
const nat s = _size;
inc ( a.size() );
for ( nat i = s; i < _size; ++i ) _data.var[i] = a[i-s];
return *this;
}
};
Шаблон классов Suite предназначен для создания последовательных наборов однотипных элементов.
Дружественная функция _swap меняет содержимое двух наборов. template <class T> class Suite : SuiteRef<T>
{
Suite ( const Suite & );
virtual void resizeAndCopy ( nat n )
{
real_size = _max ( real_size + n, 8u );
T * tmp = new T[real_size];
#if _MSC_VER > 1200 // MS VC 6.0
for ( nat i = 0; i < _size; ++i ) copyFunc ( tmp[i], _data.var[i] );
#else
for ( nat i = 0; i < _size; ++i ) tmp[i] = _data.var[i];
#endif
delete[] _data.var;
_data.var = tmp;
_size = n;
}
public:
Suite () : SuiteRef<T>(0, real_size=0) {}
explicit Suite ( nat n, nat m = 0 ) : SuiteRef<T>((real_size=_max(n,m)) > 0 ? new T[real_size] : 0, m) {}
~Suite () { delete[] _data.var; }
Suite & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
_size = r.size();
if ( real_size < _size )
{
real_size = _size;
delete[] _data.var;
_data.var = 0; // на случай исключения в new
_data.var = new T[_size];
}
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
Suite & operator= ( const Suite & a )
{
return *this = *a;
}
Suite & swap ( Suite & a )
{
_swap ( real_size, a.real_size );
_swap ( _size, a._size );
_swap ( _data, a._data );
return *this;
}
friend inline void _swap ( Suite & a1, Suite & a2 )
{
a1.swap ( a2 );
}
};
#if _MSC_VER > 1200 // MS VC 6.0
template <class T> inline void copyFunc ( T & a, T & b ) { a = b; }
template <class T> inline void copyFunc ( Suite <T> & a, Suite <T> & b ) { _swap ( a, b ); }
template <class T> inline void copyFunc ( DynArray<T> & a, DynArray<T> & b ) { _swap ( a, b ); }
#endif
Шаблон классов CmbSuite также предназначен для создания последовательных наборов однотипных элементов,
но в отличии от шаблона Suite он является комбинированным аналогично CmbArray:
template <class T, nat N> class CmbSuite : public SuiteRef<T>
{
T stor[N];
CmbSuite ( const CmbSuite & );
virtual void resizeAndCopy ( nat n )
{
real_size = _max ( real_size + n, 8u );
T * tmp = new T[real_size];
#if _MSC_VER > 1200 // MS VC 6.0
for ( nat i = 0; i < _size; ++i ) copyFunc ( tmp[i], _data.var[i] );
#else
for ( nat i = 0; i < _size; ++i ) tmp[i] = _data.var[i];
#endif
if ( _data.var != stor ) delete[] _data.var;
_data.var = tmp;
_size = n;
}
public:
CmbSuite () : SuiteRef<T>(stor, 0) { real_size = N; }
explicit CmbSuite ( nat n, nat m = 0 ) :
SuiteRef<T> ( ( real_size = _max(n,m) ) > N ? new T[real_size] : ( real_size = N, stor ), m ) {}
~CmbSuite () { if ( _data.var != stor ) delete[] _data.var; }
CmbSuite & operator= ( CCArrRef<T> & r )
{
if ( _data.var == r() ) return *this;
_size = r.size();
if ( real_size < _size )
{
real_size = _size;
if ( _data.var != stor )
{
delete[] _data.var;
_data.var = stor; // на случай исключения в new
}
_data.var = new T[_size];
}
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
CmbSuite & operator= ( const CmbSuite & a )
{
return *this = *a;
}
};
Шаблон классов LtdSuiteRef предназначен для создания ссылок на набор элементов ограниченного размера.
template <class T> class LtdSuiteRef : public SuiteRef<T>
{
virtual void resizeAndCopy ( nat n )
{
#ifdef ARRAY_TEST
if ( n > real_size ) outOfRange ( "LtdSuiteRef::resizeAndCopy", real_size, n );
#endif
_size = real_size;
}
public:
LtdSuiteRef ( ArrRef<T> a, nat i, nat n ) : SuiteRef<T>( a(i), 0 )
{
real_size = n;
#ifdef ARRAY_TEST
if ( a.size() < i + n ) outOfRange ( "LtdSuiteRef", a.size(), i + n );
#endif
}
LtdSuiteRef & operator= ( CCArrRef<T> & r )
{
_size = r.size();
#ifdef ARRAY_TEST
if ( _size > real_size ) outOfRange ( "LtdSuiteRef::operator=", real_size, _size );
#endif
if ( _size > real_size ) _size = real_size;
for ( nat i = 0; i < _size; ++i ) _data.var[i] = r[i];
return *this;
}
LtdSuiteRef & operator= ( const LtdSuiteRef & a )
{
return *this = *a;
}
};
В результате получаем следующую иерархию классов:
CArrRef -> MutCArrRef
|
|
ArrRef -> FixArrRef -> FixArray
|
|
DynArrRef -> DynArray, CmbArray
|
|
SuiteRef -> Suite, CmbSuite
|
|
LtdSuiteRef
Семь из них являются интерфейсными ( или ссылками на массив ) и пять - контейнерными классами.
Такое большое к-во классов вызвано стремлением, по возможности, избегать применение операторов new и delete.
Исходники находятся в файле ShevArray.h. Смотрите также раздел Операции с массивами. Наверх |