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

Question

Я хочу создать матрицу смежности для графа. Поскольку я читаю, это не безопасно использовать массивы вида matrix[x][y] поскольку они не проверяют диапазон, я решил использовать векторный шаблон класса stl. Все, что мне нужно хранить в матрице - это логические значения. Так что мой вопрос, если с помощью std::vector<std::vector<bool>* >* создает слишком много накладных расходов или, если есть более простой способ для матрицы и как я могу правильно ее инициализировать.

РЕДАКТИРОВАТЬ: Большое спасибо за быстрые ответы. Я только что понял, что, конечно, мне не нужны указатели. Размер матрицы будет инициализирован в самом начале и не изменится до конца программы. Это для школьного проекта, поэтому было бы хорошо, если бы я написал "хороший" код, хотя технически производительность не так уж важна. Использование STL нормально. Использование чего-то вроде boost, вероятно, не ценится.

Answer 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 std::out_of_range("matrix indices out of range"); // ouch
                return inner_[dimx_*y + x];
        }
};

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

Answer 2

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

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

например. Если вам нравится нотация "[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;

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

Answer 3

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

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

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

станд:: вектор:: в ()
станд:: вектор:: Оператор []()

Другие заметки: почему вектор<указатели>?
Вы можете довольно легко иметь вектор

Answer 4

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

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

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

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

вместо

float m[4][4];

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

---

ОБНОВЛЕНИЕ: После некоторого обсуждения в комментариях здесь относительно относительной эффективности boost::array против 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;
}

Answer 5

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

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

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

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

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

Answer 9

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

Answer 10

Имейте в виду std::vector также не выполняет проверку диапазона.