Правильный способ создать матрицу в 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

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

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

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

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

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

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

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

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

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

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

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

Все вышеперечисленное позволит вам сделать:

m[6][3] = true;

Answer 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;

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

Answer 4

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

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

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

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

вместо

float m[4][4];

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

---

ОБНОВЛЕНИЕ: После некоторого обсуждения в комментариях относительно производительности boost::array против boost::multi_array я бы отметил, что этот код, скомпилированный с g++ -O3 -DNDEBUG в Debian / Lenny amd64 на Q9450 с 1333 МГц ОЗУ DDR3 занимает 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

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

Answer 6

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

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

Answer 7

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

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

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

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

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

Answer 10

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