Безопасный индекс массива - C/C++

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

// safe_array.hpp

#ifndef safe_array_hpp
#define safe_array_hpp

#include <cstddef>
#include <stdexcept>

template <std::size_t N>
class safe_array_index {
    std::size_t i_;
public:
    explicit safe_array_index(std::size_t i)
    {
        if (i >= N)
            throw std::out_of_range("initial value is out of range");
        i_ = i;
    }
    safe_array_index& operator=(std::size_t i)
    {
        if (i >= N)
            throw std::out_of_range("assigned value is out of range");
        i_ = i;
        return *this;
    }
    bool increment()
    {
        if (i_ == N - 1)
            return false;
        i_++;
        return true;
    }
    operator std::size_t() { return i_; }
};

template <typename T, std::size_t N>
class safe_array {
    T a_[N];
public:
    T const& operator[](safe_array_index<N> i) const
    {
        return a_[i];
    }
    T& operator[](safe_array_index<N> i)
    {
        return a_[i];
    }
};

#endif

// safe_array_test.cpp

#include "safe_array.hpp"

#include <iomanip>
#include <iostream>

int main()
{
    safe_array<int, 10> a, b, c, d;
    safe_array_index<10> i(0);
    do {
        a[i] = static_cast<int>(i);
        b[i] = a[i] * a[i];
        c[i] = b[i] * a[i];
        d[i] = c[i] * a[i];
    } while (i.increment());
    i = 0;
    do {
        std::cout
            << std::setw(1) << a[i] << ' '
            << std::setw(2) << b[i] << ' '
            << std::setw(3) << c[i] << ' '
            << std::setw(4) << d[i] << '\n';
    } while (i.increment());
}

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

    . . .
    safe_array_index() : i_(0) {}
    void reset() { i_ = 0; }
    . . .

    . . .
    safe_array_index<10> i;
    do {
        a[i] = static_cast<int>(i);
        b[i] = a[i] * a[i];
        c[i] = b[i] * a[i];
        d[i] = c[i] * a[i];
    } while (i.increment());
    i.reset();
    . . .

(Инициализация нулем и присваивание нуля безопасны, поскольку C++ запрещает массивы нулевой длины.)

Хотя проверки во время исполнения программы не производятся, ошибки, связанные с обращением за пределы массива, исключены.

Здравствуйте, igna, Вы писали:

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

Здравствуйте, Vamp, Вы писали:

V>Кроме этого, очевидным недостатоком сейф эррея в предложенной релизации является необходимость синхронизировать тип индекса с размерностью массива — отличный способ ошибиться при внесении изменений.

Компилятор подскажет.

Здравствуйте, Vamp, Вы писали:

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

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

I>Компилятор подскажет.
Да. Подскажет. Только он так подскажет, что вовек не разберешься, что не так, особенно, если обявление индекса и массива (а как правило, так и бывает) разнесены.
Например, вот как реагирует g++:
....
file.C: In function 'int main()':
file.C:55: error: no match for 'operator[]' in 'a[i]'
file.C:38: note: candidates are: const T& safe_array<T, N>::operator[](safe_array_index<N>) const [with T = int, unsigned int N = 15u]
...
И таких сообщений там в этой короткой программе 14 штук.

Здравствуйте, igna, Вы писали:

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

Обычно это называется итератор.
И если смотреть на него именно как на итератор, то вполне логично, что он проверяется при модификации, но не проверяется при разыменовании.
Так же, если имеем дело с одним массивом, то очевидной альтернативой является кэширование разыменованного значения.

Здравствуйте, remark, Вы писали:

R>Обычно это называется итератор.

Тот пример — да, но ведь можно и такое написать:

#include "safe_array.hpp"

int main()
{
    safe_array<safe_array<int, 5>, 10> a;
    safe_array<safe_array<int, 10>, 8> b;
    safe_array<safe_array<int, 5>, 8> ab;

    // ...

    safe_array_index<5> i;
    do {
        safe_array_index<8> j;
        do {
            int s = 0;
            safe_array_index<10> k;
            do {
                s += a[k][i] * b[j][k];
            } while (k.increment());
            ab[j][i] = s;
        } while (j.increment());
    } while (i.increment());
}

Здравствуйте, igna.

Штука нужная, только её не применишь в случае, если размер массива неизвестен при компиляции.

Здравствуйте, igna, Вы писали:


int main()
{
    safe_array<int, 10> a;
    safe_array_index< a > i(0);
    // так бы я понял что автоматизируется проверка границ, а оп другому ошибка переносится в другое место и становится не так очевидна. 
}

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

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

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

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Mazay, Вы писали:

M>Штука нужная, только её не применишь в случае, если размер массива неизвестен при компиляции.

Тоже можно, если шаблонным параметром сделать не число типа size_t, а класс, у которого есть статический член типа size_t. Причем определение такого класса можно автоматизировать, тогда шаблонным параметром будет просто "пустой" теговый тип:

// safe_array.hpp

#ifndef safe_array_hpp
#define safe_array_hpp

#include <cstddef>
#include <stdexcept>

template <typename T>
struct safe_array_length {
    static std::size_t value;
};

template <typename T> std::size_t safe_array_length<T>::value;

template <typename N>
class safe_array_index {
    std::size_t i_;
public:
    safe_array_index() : i_(0) {}
    explicit safe_array_index(std::size_t i)
    {
        if (i >= safe_array_length<N>::value)
            throw std::out_of_range("initial value is out of range");
        i_ = i;
    }
    safe_array_index& operator=(std::size_t i)
    {
        if (i >= safe_array_length<N>::value)
            throw std::out_of_range("assigned value is out of range");
        i_ = i;
        return *this;
    }
    void reset() { i_ = 0; }
    bool increment()
    {
        if (i_ == safe_array_length<N>::value - 1)
            return false;
        i_++;
        return true;
    }
    operator std::size_t() { return i_; }
};

template <typename T, typename N>
class safe_array {
    T* a_;
public:
    safe_array() : a_(new T[safe_array_length<N>::value]) {}
    ~safe_array() { delete[] a_; }
    T const& operator[](safe_array_index<N> i) const { return a_[i]; }
    T& operator[](safe_array_index<N> i) { return a_[i]; }
private:
    safe_array(safe_array const&);
    safe_array& operator=(safe_array const&);
};

#endif

// safe_array_test.cpp

#include "safe_array.hpp"

#include <iomanip>
#include <iostream>

struct L {};

int main()
{
    safe_array_length<L>::value = 10;
    safe_array<int, L> a, b, c, d;
    safe_array_index<L> i;
    do {
        a[i] = static_cast<int>(i);
        b[i] = a[i] * a[i];
        c[i] = b[i] * a[i];
        d[i] = c[i] * a[i];
    } while (i.increment());
    i.reset();
    do {
        std::cout
            << std::setw(1) << a[i] << ' '
            << std::setw(2) << b[i] << ' '
            << std::setw(3) << c[i] << ' '
            << std::setw(4) << d[i] << '\n';
    } while (i.increment());
}

Аналог примера с перемножением матриц, но с возможностью задавать размер во время исполнения:

// matrix_multiplication.cpp

#include "safe_array.hpp"

#include <cstddef>

struct N {};
struct M {};
struct L {};

int main()
{
    safe_array_length<N>::value = 5;
    safe_array_length<M>::value = 10;
    safe_array_length<L>::value = 8;

    safe_array<safe_array<int, N>, M> a;
    safe_array<safe_array<int, M>, L> b;
    safe_array<safe_array<int, N>, L> ab;

    // ...

    safe_array_index<N> i;
    do {
        safe_array_index<L> j;
        do {
            int s = 0;
            safe_array_index<M> k;
            do {
                s += a[k][i] * b[j][k];
            } while (k.increment());
            ab[j][i] = s;
        } while (j.increment());
    } while (i.increment());
}

Здравствуйте, Vamp, Вы писали:

V>file.C: In function 'int main()':
V>file.C:55: error: no match for 'operator[]' in 'a[i]'
V>file.C:38: note: candidates are: const T& safe_array<T, N>::operator[](safe_array_index<N>) const [with T = int, unsigned int N = 15u]

А по-моему типичное для C++ сообщение об ошибке. И относительно понятное к тому же, например сразу видно, что ты изменил длину на 15.

V>И таких сообщений там в этой короткой программе 14 штук.

Верно. Так ведь и operator[] используется 14 раз.

M>    safe_array_index< a > i(0);

Индекс привязанный к определенному массиву это уже не совсем индекс, а скорее итератор. Речь не о том, что итераторы хуже, они другие. В некоторых задачах нужно один и тот же индекс использовать для доступа к нескольким массивам. Например многие вычислительные задачи такие, а использование в них нескольких итераторов вместо одного индекса провоцирует ошибки, очень легко итераторы могут оказаться рассогласованными.

Дополнительный плюс: если перепутать индексы, компилятор выдаст сообщение об ошибке:

                s += a[k][i] * b[k][j]; // error

Здравствуйте, igna, Вы писали:

I>

M>>    safe_array_index< a > i(0);
I>

I>Индекс привязанный к определенному массиву это уже не совсем индекс, а скорее итератор. Речь не о том, что итераторы хуже, они другие. В некоторых задачах нужно один и тот же индекс использовать для доступа к нескольким массивам. Например многие вычислительные задачи такие, а использование в них нескольких итераторов вместо одного индекса провоцирует ошибки, очень легко итераторы могут оказаться рассогласованными.

Ну опять же повторюсь , бывае такое редко. Если рядом лежат несколько масивово одной длины , можеть объеденить их элемент в один класс ?

Кстати у вас индекс выполняет 2 роли одновременно и задает диапазон значений в цикле и индексирует , а если нам надо проитерировать только часть массива ?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, minorlogic, Вы писали:

M>Ну опять же повторюсь , бывае такое редко.

Так предлагаемое решение для этих редких случаев и есть.

Здравствуйте, minorlogic, Вы писали:

M>Здравствуйте, igna, Вы писали:

I>>

M>>>    safe_array_index< a > i(0);
I>>

I>>Индекс привязанный к определенному массиву это уже не совсем индекс, а скорее итератор. Речь не о том, что итераторы хуже, они другие. В некоторых задачах нужно один и тот же индекс использовать для доступа к нескольким массивам. Например многие вычислительные задачи такие, а использование в них нескольких итераторов вместо одного индекса провоцирует ошибки, очень легко итераторы могут оказаться рассогласованными.

M>Ну опять же повторюсь , бывае такое редко. Если рядом лежат несколько масивово одной длины , можеть объеденить их элемент в один класс ?

Не всегда это возможно. Это может быть буфер, формат которого нельзя менять по требованию какого-либо API. Это могут быть данные приехавшие в таком виде откуда-либо ещё. Объединение не всегда разумно с т.з. производительности: Hot/Cold Data Splitting

Здравствуйте, igna, Вы писали:

I>

M>>    safe_array_index< a > i(0);
I>

std::vector<Foo> field;
Foo getFooAtPoint(double x)
{
size_t i = ceil(x * MAX + 0.5);
return field[i];
// не думаю что здесь есть смысл в итераторах:
// return *(field.begin() + i);
}

Здравствуйте, igna,

#include <stdio.h>
struct MyIndex
{
};  

template <int N,class C>
 C* operator+(C (&x)[N],  MyIndex)
  {  printf(" проверяем для N=%d ",N);
     return x+N/2;
  } 

int main(int, char **)
{ MyIndex m;
  char c[9];
  c+m;  //  проверяем 
  c[m]; //  c[m] по определению *(c+m)
  return 0;
}

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

Здравствуйте, igna, Вы писали:

I>Конечно в одном из этих случаев выигрыш будет наибольшим, но и при однократном обращении он все же будет за счет совмещения проверки индекса с проверкой условия окончания цикла.

Зато, возможно, оптимизатор не просечёт как этот цикл оптимизировать...

Здравствуйте, igna, Вы писали:

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

#include <stdio.h>
struct MyIndex
{ int i;
  MyIndex(int _i):i(_i){}
  MyIndex& operator=(int _i){i=_i;return *this;}
  operator int&(){return i;}
  template <int N,class C>
    C& operator[](C (&x)[N])
    {  if(i<0||N<=i)
        printf("Ошибка !!!!");
       return x[i];
    }
};

template <int N,class C>
 C* operator+(C (&x)[N],  MyIndex)
  {  printf(" проверяем для N=%d ",N);
     return x+N/2;
  }

template <int N,class C>
 C* operator+(MyIndex,  C (&x)[N])
  {  printf(" проверяем для N=%d ",N);
     return x+N/2;
  }

int main(int, char **)
{
 #define PROVERKA
 #ifdef PROVERKA
  MyIndex m=9;
 #else
  int m;
 #endif
  int i=m;
  m=i;

  char c[9];
  c+m;  //  проверяем
  m+c;
  for(m=0;m<11;m++)
   m[c]=m;
  return 0;
}

полная симуляция int, только с проверкой

Здравствуйте, Programador, Вы писали:

P>struct MyIndex
P>{ int i;
P>  MyIndex(int _i):i(_i){}
P>  MyIndex& operator=(int _i){i=_i;return *this;}
P>  operator int&(){return i;}
P>  template <int N,class C>
P>    C& operator[](C (&x)[N])
P>    {  if(i<0||N<=i)
P>        printf("Ошибка !!!!");
P>       return x[i];
P>    }
P>};

Разве здесь нет проверки индекса при доступе к элементу массива?

Здравствуйте, Erop, Вы писали:

E>Зато, возможно, оптимизатор не просечёт как этот цикл оптимизировать...

Ну значит это не тот случай (или не тот компилятор), когда использование safe_array_index имеет смысл.

Здравствуйте, igna, Вы писали:

I>Здравствуйте, Programador, Вы писали:

I>

P>>struct MyIndex
P>>{ int i;
P>>  MyIndex(int _i):i(_i){}
P>>  MyIndex& operator=(int _i){i=_i;return *this;}
P>>  operator int&(){return i;}
P>>  template <int N,class C>
P>>    C& operator[](C (&x)[N])
P>>    {  if(i<0||N<=i)
P>>        printf("Ошибка !!!!");
P>>       return x[i];
P>>    }
P>>};
I>

I>Разве здесь нет проверки индекса при доступе к элементу массива?
здес not implemented

а здесь есть

  char c[9];
  c+m;  //  проверяем
  m+c;
  for(m=0;m<11;m++)
   m[c]=m;
  return 0;
}

и для этого не нужно нигде указывать размер массива, + полная совместимость с int

Здравствуйте, Programador, Вы писали:

I>>Разве здесь нет проверки индекса при доступе к элементу массива?
P>здес not implemented

P>а здесь есть

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

Здравствуйте, minorlogic, Вы писали:

M>Кстати у вас индекс выполняет 2 роли одновременно и задает диапазон значений в цикле и индексирует , а если нам надо проитерировать только часть массива ?

Проитерировать часть массива — это не проблемма. Достаточно инициализировать индекс чем-то осмысленным, вместо reset()'а и передавать в increment() верхнюю границу в качестве формального параметра, лишь бы компилятору хватило мозгов заоптимизировать.
Плохо то, что придётся явно проверять случай, когда ни одной итерации не требуется. Например надо нам пробежаться индексом по интервалу [A, B):

i = A;
do
{
      do_smth(i, array_X[i], array_Y[i], exp(i));
} while (i.increment(B));

или так, как привыкли с обычным size_t:

for(size_t i = A; i < B; ++i)
{
     do_smth(i, array_X[i], array_Y[i], exp(i));
}

Если A == B, то код в первом случае отработает не так как хочется, да и он выглядит не очень.

	От:	igna
	Дата:	02.05.08 13:30
	Оценка:	71 (4)

	От:	Vamp
	Дата:	02.05.08 13:39
	Оценка:

	От:	igna
	Дата:	02.05.08 13:44
	Оценка:

	От:	igna
	Дата:	02.05.08 13:52
	Оценка:

	От:	Vamp
	Дата:	02.05.08 13:53
	Оценка:

От:	remark	http://www.1024cores.net/
Дата:	02.05.08 13:55
Оценка:

	От:	minorlogic
	Дата:	03.05.08 06:36
	Оценка:	1 (1)

	От:	Erop
	Дата:	04.05.08 09:36
	Оценка:

	От:	Programador
	Дата:	04.05.08 10:39
	Оценка:

	От:	Programador
	Дата:	04.05.08 16:52
	Оценка:

	От:	Mazay
	Дата:	05.05.08 07:56
	Оценка: