Правильный способ создания матрицы в С++

Ответ 1

Обратите внимание, что вы также можете использовать boost.ublas для создания и манипуляции с матрицами, а также boost.graph для представления и обработки графиков несколькими способами, а также с использованием алгоритмов на них и т.д.

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

template <typename T>
class BoundsMatrix
{
        std::vector<T> inner_;
        unsigned int dimx_, dimy_;

public:
        BoundsMatrix (unsigned int dimx, unsigned int dimy)
                : dimx_ (dimx), dimy_ (dimy)
        {
                inner_.resize (dimx_*dimy_);
        }

        T& operator()(unsigned int x, unsigned int y)
        {
                if (x >= dimx_ || y>= dimy_)
                        throw 0; // ouch
                return inner_[dimx_*y + x];
        }
};

Обратите внимание, что вам также нужно будет добавить версию const для операторов и/или итераторов и странное использование исключений, но вы получите эту идею.

Ответ 2

Стандартный вектор НЕ делает проверку диапазона по умолчанию.

то есть. Оператор [] не выполняет проверку диапазона.

Метод at() аналогичен [], но выполняет проверку диапазона.
Он выдает исключение из вне диапазона.

std::vector:: at()
std::vector:: operator []()

Другие примечания: Почему вектор < Указатели > ?
Вы можете легко получить вектор <Object> . Теперь нет необходимости беспокоиться об управлении памятью (т.е. Утечки).

std::vector<std::vector<bool> >   m;

Примечание: vector <bool> перегружен и не очень эффективен (т.е. эта структура была оптимизирована для размера, а не скорости) (Это то, что сейчас признано ошибкой комитета по стандартам).

Если вы знаете размер матрицы во время компиляции, вы можете использовать std:: bitset?

std::vector<std::bitset<5> >    m;

или если определено время выполнения, используйте boost:: dynamic_bitset

std::vector<boost::dynamic_bitset>  m;

Все вышесказанное позволит вам:

m[6][3] = true;

Ответ 3

Лучший способ:

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

например. Если вам нравится обозначение "[x] [y]", сделайте следующее:

class my_matrix {
  std::vector<std::vector<bool> >m;
public:
  my_matrix(unsigned int x, unsigned int y) {
    m.resize(x, std::vector<bool>(y,false));
  }
  class matrix_row {
    std::vector<bool>& row;
  public:
    matrix_row(std::vector<bool>& r) : row(r) {
    }
    bool& operator[](unsigned int y) {
      return row.at(y);
    }
  };
  matrix_row& operator[](unsigned int x) {
    return matrix_row(m.at(x));
  }
};
// Example usage
my_matrix mm(100,100);
mm[10][10] = true;

пь. Если вы так программируете, то С++ так же безопасен, как и все другие "безопасные" языки.

Ответ 4

Если вам нужна производительность массива "C", но с добавленной безопасностью и STL-подобной семантикой (итераторы, begin() и end() и т.д.), используйте boost::array.

В основном это шаблонная оболочка для 'C'-массивов с некоторыми NDEBUG -разборчивыми возможностями проверки диапазона (а также некоторые std::range_error исключающие исключения).

Я использую такие вещи, как

boost::array<boost::array<float,4>,4> m;

вместо

float m[4][4];

все время, и он отлично работает (с соответствующими typedefs, чтобы сохранить многословие, во всяком случае).

ОБНОВЛЕНИЕ:. После некоторого обсуждения в комментариях относительной производительности boost::array vs boost::multi_array, я хотел бы указать, что этот код, скомпилированный с g++ -O3 -DNDEBUG в Debian/Lenny amd64 на Q9450 с 1333 МГц DDR3 RAM занимает 3,3 с для boost::multi_array против 0,6 с для boost::array.

#include <iostream>
#include <time.h>
#include "boost/array.hpp"
#include "boost/multi_array.hpp"

using namespace boost;

enum {N=1024};

typedef multi_array<char,3> M;
typedef array<array<array<char,N>,N>,N> C;

// Forward declare to avoid being optimised away
static void clear(M& m);
static void clear(C& c);

int main(int,char**)
{
  const clock_t t0=clock();

  {
    M m(extents[N][N][N]);
    clear(m);
  }

  const clock_t t1=clock();

  {
    std::auto_ptr<C> c(new C);
    clear(*c);
  }

  const clock_t t2=clock();

  std::cout 
    << "multi_array: " << (t1-t0)/static_cast<float>(CLOCKS_PER_SEC) << "s\n"
    << "array      : " << (t2-t1)/static_cast<float>(CLOCKS_PER_SEC) << "s\n";

  return 0;
}

void clear(M& m)
{
  for (M::index i=0;i<N;i++)
    for (M::index j=0;j<N;j++)
      for (M::index k=0;k<N;k++)
    m[i][j][k]=1;
}


void clear(C& c)
{
  for (int i=0;i<N;i++)
    for (int j=0;j<N;j++)
      for (int k=0;k<N;k++)
    c[i][j][k]=1;
}

Ответ 5

Что бы я сделал, это создать свой собственный класс для работы с матрицами (возможно, как массив [x * y], потому что я больше привык к C (и у меня была бы проверка собственных границ), но вы могли бы использовать векторов или любой другой подструктуры в этом классе).

Сначала загрузите свой материал, а затем подумайте о том, как быстро он работает. Если вы правильно создаете класс, вы можете вытащить реализацию вашего массива [x * y] и заменить его векторами или битами или любым другим, что вы хотите, не изменяя остальную часть кода.

Я не совсем уверен, но я считаю, что для чего предназначены классы, способность абстрагироваться от реализации вне поля зрения и предоставлять только интерфейс: -)

Ответ 6

Мой любимый способ хранения графика - vector<set<int>>; n элементов в векторе (узлы 0..n-1), >= 0 элементов в каждом наборе (ребра). Просто не забудьте добавить обратную копию каждого двунаправленного ребра.

Ответ 7

В дополнение ко всем ответам, которые были опубликованы до сих пор, вам может потребоваться проверить С++ FAQ Lite. Вопросы 13.10 - 13.12 и 16.16 - 16.19 охватывают несколько темы, связанные с переводом собственного класса матрицы. Вы увидите несколько различных способов хранения данных и предложений о том, как лучше всего писать индексированные операторы.

Кроме того, если ваш график достаточно разрежен, вам может не понадобиться матрица. Вы можете использовать std::multimap для сопоставления каждой вершины с теми, с которыми она соединяется.

Ответ 8

Считайте также, насколько велика ваша диаграмма/матрица, важна ли производительность? Является ли график статическим или может расти с течением времени, например. добавив новые ребра?

Ответ 9

Обратите внимание, что std::vector не выполняет проверку диапазона.

Ответ 10

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

Ниже приведен пример вашей конкретной проблемы:

// In C++11
Mat<bool> matrix = {  
    { true, true},
    { false, false},
};

// In C++98
Mat<bool> matrix;
matrix << true << true << endr
       << false << false << endr;