Операции с массивами


В этом разделе представлены некоторые операции с массивами, которые описаны здесь.

Вначале рассмотрим операции, которые не меняют массивы. Массивы можно сравнивать:

template <class T> inline
bool operator == ( CArrRef<T> a, CArrRef<T> b )
{
    if ( a.size() != b.size() ) return false;
    for ( nat i = 0; i < a.size(); ++i ) 
        if ( a[i] != b[i] ) return false;
    return true;
}

template <class T> inline 
bool operator == ( const ArrRef<T> & a, const ArrRef<T> & b )
{
    return *a == *b;
}

template <class T> inline
bool operator != ( CArrRef<T> a, CArrRef<T> b )
{
    if ( a.size() != b.size() ) return true;
    for ( nat i = 0; i < a.size(); ++i ) 
        if ( a[i] != b[i] ) return true;
    return false;
}
Применять некоторую операцию поочерёдно к заданному значению:
template <class T1, class T2> inline 
T1 & operator += ( T1 & t, CArrRef<T2> a )
{
    for ( nat i = 0; i < a.size(); ++i ) t += a[i];
    return t;
}

template <class T1, class T2> inline 
T1 & operator << ( T1 & t, CArrRef<T2> a )
{
    for ( nat i = 0; i < a.size(); ++i ) t << a[i];
    return t;
}
Можно подсчитать к-во элементов равных заданному:
template <class A, class B> inline 
nat count ( const A & a, const B & b, nat from = 0 )
{
    nat n = 0;
    for ( nat i = from; i < a.size(); ++i ) if ( a[i] == b ) ++n;
    return n;
}
Можно найти индекс первого с начала элемента равного заданному ( в случае, если такой не будет найден возвращается к-во элементов массива ):
template <class A, class B> inline 
nat firEqu ( const A & a, const B & b, nat from = 0 )
{
    for ( nat i = from; i < a.size(); ++i ) if ( a[i] == b ) return i;
    return a.size();
}
Или индекс первого с конца:
template <class A, class B> inline 
nat lasEqu ( const A & a, const B & b )
{
    for ( nat i = a.size(); i > 0; --i ) if ( a[i-1] == b ) return i-1;
    return a.size();
}
Можно определить - есть ли в массиве элемент равный данному:
template <class A, class B> inline 
bool hasEqu ( const A & a, const B & b )
{
    for ( nat i = 0; i < a.size(); ++i ) if ( a[i] == b ) return true;
    return false;
}
Шаблон функций firMin находит индекс первого с начала минимального элемента:
template <class T> inline 
nat firMin ( const T & a )
{
    nat m = 0;
    for ( nat i = 1; i < a.size(); ++i ) if ( a[i] < a[m] ) m = i;
    return m;
}
Шаблон функций firMax находит индекс первого с начала максимального элемента:
template <class T> inline 
nat firMax ( const T & a )
{
    nat m = 0;
    for ( nat i = 1; i < a.size(); ++i ) if ( a[i] > a[m] ) m = i;
    return m;
}
Шаблон функций findMinMax находит минимальное и максимальное значения элементов:
template <class T1, class T2> inline 
bool findMinMax ( const T1 & a, T2 & min, T2 & max )
{
    if ( ! a.size() ) return false;
    max = min = a[0];
    for ( nat i = 1; i < a.size(); ++i )
    {
        const T2 & t = a[i];
        if ( min > t ) min = t; else
        if ( max < t ) max = t;
    }
    return true;
}
Шаблон функций amean находит арифметическое среднее по всему массиву:
template <class T> inline 
Def<T> amean ( CArrRef<T> a )
{
    if ( ! a.size() ) return Def<T>();
    T res ( a[0] );
    for ( nat i = 1; i < a.size(); ++i ) res += a[i];
    return res / a.size();
}

template <class T> inline 
Def<T> amean ( const ArrRef<T> & a )
{
    return amean ( *a );
}
Если элементы массива упорядочены по возрастанию, то при помощи функций firEqu123 и lasEqu123 можно найти первый или последний элемент равный заданному:
template <class A, class B> inline 
nat firEqu123 ( const A & a, const B & b )
{
    if ( ! a.size() ) return 0;
    int prior = -1, last = a.size() - 1;
    while ( prior + 1 < last )
    {
        const int i = ( prior + last ) / 2;
        if ( a[i] < b ) prior = i; else last = i;
    }
    return a[last] == b ? last : a.size();
}

template <class A, class B> inline 
nat lasEqu123 ( const A & a, const B & b )
{
    if ( a.size() == 0 ) return 0;
    nat from = 0, before = a.size();
    while ( from + 1 < before )
    {
        const nat i = ( from + before ) / 2;
        if ( a[i] > b ) before = i; else from = i;
    }
    return a[from] == b ? from : a.size();
}
Теперь рассмотрим операции, которые меняют массивы.

Операторы <<= и >>= осуществляют циклический сдвиг элементов на заданное количество шагов в начало и в конец массива соответственно:
template <class T> inline 
ArrRef<T> & operator <<= ( ArrRef<T> & a, nat k )
{
    const nat n = a.size();
    if ( n < 2 || ! ( k %= n ) ) return a;
    const nat m = n - k;
    if ( m < k ) return a >>= m;
    nat i;
    CmbArray<T, 64> b ( k );
    for ( i = 0; i < k; ++i ) b[i] = a[i];
    for ( i = 0; i < m; ++i ) a[i] = a[i+k];
    for ( i = 0; i < k; ++i ) a[i+m] = b[i];
    return a;
}

template <class T> inline 
ArrRef<T> & operator >>= ( ArrRef<T> & a, nat k )
{
    const nat n = a.size();
    if ( n < 2 || ! ( k %= n ) ) return a;
    const nat m = n - k;
    if ( m < k ) return a <<= m;
    nat i;
    CmbArray<T, 64> b ( k );
    for ( i = 0; i < k; ++i ) b[i] = a[i+m];
    for ( i = m; --i > 0; ) a[i+k] = a[i]; a[k] = a[0];
    for ( i = 0; i < k; ++i ) a[i] = b[i];
    return a;
}
Следующие функции-операторы делают арифметичекие операции с элементами массива поочерёдно начиная с первого:
template <class T1, class T2> inline 
ArrRef<T1> & operator += (  ArrRef<T1> & a, const T2 & b )
{
    for ( nat i = 0; i < a.size(); ++i ) a[i] += b;
    return a;
}

template <class T1, class T2> inline 
ArrRef<T1> & operator -= (  ArrRef<T1> & a, const T2 & b )
{
    for ( nat i = 0; i < a.size(); ++i ) a[i] -= b;
    return a;
}

template <class T1, class T2> inline 
ArrRef<T1> & operator *= (  ArrRef<T1> & a, const T2 & b )
{
    for ( nat i = 0; i < a.size(); ++i ) a[i] *= b;
    return a;
}

template <class T1, class T2> inline 
ArrRef<T1> & operator /= (  ArrRef<T1> & a, const T2 & b )
{
    for ( nat i = 0; i < a.size(); ++i ) a[i] /= b;
    return a;
}
Функция sum складывает почленно элементы массивов b и c, и записывает их в массив a:
template <class A, class B, class C> inline 
A & sum ( A & a, const B & b, const C & c )
{
    const nat n = _min ( a.size(), b.size(), c.size() );
    for ( nat i = 0; i < n; ++i ) a[i] = b[i] + c[i];
    return a;
}
Описание шаблона классов Def находится здесь.
Исходники находятся в файле ShevArray.h.

Наверх