Информация об изменениях

Сообщение [bike] Многомерный динамический массив от 15.10.2020 15:15

Изменено 15.10.2020 15:23 Bill Baklushi

Старый текст
Новый текст
Разница

[bike] Многомерный динамический массив

Приветствую.

Вчера прошла не очень замеченной крайне калорийная тема
https://rsdn.org/forum/prj/7852771.all

Юный гений пытается продавать крайне кривой велосипед поработе с динамическими массивами.

Задался вопросом, а как такое сделать на нормальных плюсах...
Двумерный вектор я изобретал еще в студенческие, досовские времена: первый operator [] возвращает указатель на строку элементов, второй (не переопределенный) — ссылку на сам элемент.

Вектор векторов тоже решение, но сомнительное по эффективности.

Помню, когда-то изобретал массив с фиксированным числом []. Последний оператор [] возвращает ссылку на элемент, непоследний возвращает шаблонизированный целым значением объект-индекс.

Здесь несколько изменил идею. Все индексы одного и того же типа. operator [] добавляет значение во внутренний контейнер объекта-индекса.
Преобразование индекса в тип-элемент приводит к вычислению плоского индекса в контейнере и выборке соответствующего элемента.

Массив содежит два вектора: описание размерностей dimensions_ и данные data_.

Шаблонизировать тип элементов не стал, это легко допилить.

Применение универсальных ссылок && не сделал — немного плаваю в теме. То же и с constexpr.

Конструктивная критика ~~, смешочки и тухлые помидоры~~ приветствуется.

UPD1: На реализацию ушло около 3 часов, в основном на приведение к функциональному стилю и отладку.

Код:

#include <iostream>

#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

#include <stdexcept>
#include <initializer_list>
    

namespace baklushi
{

typedef double BASE_TYPE;

class multidim_dynarray;

class multiindex
{
public:  

  multiindex operator[] (int i)
  {
    multiindex new_idx(*this);
    new_idx.index_.push_back(i);
    return new_idx;
  }

  operator BASE_TYPE &();
  BASE_TYPE operator = (BASE_TYPE val);
  
private:
  std::vector<size_t> index_;
  multidim_dynarray &container_;  

  multiindex(const multiindex &src):
    container_(src.container_),
    index_(src.index_)
  {
  } 

  multiindex(multidim_dynarray &arr):
    container_(arr)
  {
  }

  friend class multidim_dynarray;
};


class multidim_dynarray
{
public:  
  multiindex operator [](int i)
  {
    return multiindex(*this)[i];  
  }

  multidim_dynarray(std::initializer_list<size_t> dim);
  multidim_dynarray(std::initializer_list<size_t> dim,
    std::initializer_list<BASE_TYPE> data);

  void redim(std::initializer_list<size_t> lst);
  std::vector<size_t> dimensions(){ return dimensions_; }
private:
  std::vector<size_t> dimensions_;
  std::vector<BASE_TYPE> data_;

  friend class multiindex;
};


multidim_dynarray::multidim_dynarray(std::initializer_list<size_t> lst):
  dimensions_(lst)
{
  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);
}

multidim_dynarray::multidim_dynarray(
  std::initializer_list<size_t> dim,
  std::initializer_list<BASE_TYPE> data):
dimensions_(dim)
{
  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);

  std::copy(
    std::begin(data),
    std::min(std::end(data), std::begin(data)+total_el),
    data_.begin());
}

void multidim_dynarray::redim(std::initializer_list<size_t> dim)
{
  dimensions_.assign(dim);

  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);
}

multiindex::operator BASE_TYPE &()
{
  if(!index_.size() || index_.size() !=
    container_.dimensions_.size())
  {
    throw std::out_of_range("Invalid indirection");
  }

  if(!std::equal(
    index_.begin(),
    index_.end(),
    container_.dimensions_.begin(),
    std::less<size_t>() ))
  {
    throw std::out_of_range("Out of range");
  }
  
  std::vector<int> partial_product(index_.size());
  
  std::partial_sum(
    container_.dimensions_.rbegin(),
    container_.dimensions_.rend()-1,
    partial_product.rbegin()+1,
    std::multiplies<int>());
  partial_product.back() = 1;

  std::transform(
    index_.begin(),
    index_.end(),
    partial_product.begin(),
    partial_product.begin(),
    std::multiplies<size_t>());

  size_t flat_idx = std::accumulate(
    partial_product.begin(),
    partial_product.end(),
    0);

   return container_.data_[flat_idx];
}

BASE_TYPE multiindex::operator = (BASE_TYPE val)
{
  return this->operator BASE_TYPE &() = val;
}

}; //namespace

int main()
{
  baklushi::multidim_dynarray arr({3,4,5},
  {
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 69  //redundant line, will be ignored

  } );

  try
  {
    arr[1][2][1] += 5.0;

    std::cout << arr[1][2][3] << std::endl;
  }
  catch(const std::out_of_range &e)
  {
    std::cerr << "Out of range exception raised: " << e.what() << '\n';
  }
}

[bike] Многомерный динамический массив

Думаю хороший сишник при необходимости переизобретет это в кратчайшие сроки.

Код:

#include <iostream>

#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>

#include <stdexcept>
#include <initializer_list>
    

namespace baklushi
{

typedef double BASE_TYPE;

class multidim_dynarray;

class multiindex
{
public:  

  multiindex operator[] (int i)
  {
    multiindex new_idx(*this);
    new_idx.index_.push_back(i);
    return new_idx;
  }

  operator BASE_TYPE &();
  BASE_TYPE operator = (BASE_TYPE val);
  
private:
  std::vector<size_t> index_;
  multidim_dynarray &container_;  

  multiindex(const multiindex &src):
    container_(src.container_),
    index_(src.index_)
  {
  } 

  multiindex(multidim_dynarray &arr):
    container_(arr)
  {
  }

  friend class multidim_dynarray;
};


class multidim_dynarray
{
public:  
  multiindex operator [](int i)
  {
    return multiindex(*this)[i];  
  }

  multidim_dynarray(std::initializer_list<size_t> dim);
  multidim_dynarray(std::initializer_list<size_t> dim,
    std::initializer_list<BASE_TYPE> data);

  void redim(std::initializer_list<size_t> lst);
  std::vector<size_t> dimensions(){ return dimensions_; }
private:
  std::vector<size_t> dimensions_;
  std::vector<BASE_TYPE> data_;

  friend class multiindex;
};


multidim_dynarray::multidim_dynarray(std::initializer_list<size_t> lst):
  dimensions_(lst)
{
  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);
}

multidim_dynarray::multidim_dynarray(
  std::initializer_list<size_t> dim,
  std::initializer_list<BASE_TYPE> data):
dimensions_(dim)
{
  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);

  std::copy(
    std::begin(data),
    std::min(std::end(data), std::begin(data)+total_el),
    data_.begin());
}

void multidim_dynarray::redim(std::initializer_list<size_t> dim)
{
  dimensions_.assign(dim);

  size_t total_el =
    std::accumulate(
      dimensions_.begin(),
      dimensions_.end(),
      1,
      std::multiplies<size_t>());
  data_.resize(total_el);
}

multiindex::operator BASE_TYPE &()
{
  if(!index_.size() || index_.size() !=
    container_.dimensions_.size())
  {
    throw std::out_of_range("Invalid indirection");
  }

  if(!std::equal(
    index_.begin(),
    index_.end(),
    container_.dimensions_.begin(),
    std::less<size_t>() ))
  {
    throw std::out_of_range("Out of range");
  }
  
  std::vector<int> partial_product(index_.size());
  
  std::partial_sum(
    container_.dimensions_.rbegin(),
    container_.dimensions_.rend()-1,
    partial_product.rbegin()+1,
    std::multiplies<int>());
  partial_product.back() = 1;

  std::transform(
    index_.begin(),
    index_.end(),
    partial_product.begin(),
    partial_product.begin(),
    std::multiplies<size_t>());

  size_t flat_idx = std::accumulate(
    partial_product.begin(),
    partial_product.end(),
    0);

   return container_.data_[flat_idx];
}

BASE_TYPE multiindex::operator = (BASE_TYPE val)
{
  return this->operator BASE_TYPE &() = val;
}

}; //namespace

int main()
{
  baklushi::multidim_dynarray arr({3,4,5},
  {
     0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
    10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
    20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
    30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
    40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
    50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
    60, 61, 62, 63, 64, 65, 66, 67, 68, 69  //redundant line, will be ignored

  } );

  try
  {
    arr[1][2][1] += 5.0;

    std::cout << arr[1][2][3] << std::endl;
  }
  catch(const std::out_of_range &e)
  {
    std::cerr << "Out of range exception raised: " << e.what() << '\n';
  }
}