Właściwy sposób tworzenia macierzy w C++

Question

Chcę utworzyć macierz sąsiedztwa dla wykresu. Ponieważ czytam, nie jest bezpiecznie używać tablic o formacie matrix[x][y], ponieważ nie sprawdzają zasięgu, zdecydowałem się użyć klasy szablonu wektorowego stl. Wszystko, co muszę przechowywać w macierzy, to wartości logiczne. Tak więc moje pytanie brzmi, jeśli użycie std::vector<std::vector<bool>* >* wytwarza zbyt dużo narzutów lub jeśli istnieje bardziej prosty sposób dla macierzy i jak mogę ją poprawnie zainicjować.

EDYCJA: Wielkie dzięki za szybkie odpowiedzi. Właśnie zdałem sobie sprawę, że oczywiście nie potrzebuję żadnych wskazówek. Rozmiar macierzy zostanie zainicjowany na samym początku i nie zmieni się do końca programu. Jest to projekt szkolny, więc dobrze by było, gdybym napisał "ładny" kod, chociaż techniczna wydajność nie jest zbyt ważna. Używanie STL jest w porządku. Używanie czegoś podobnego do boost, prawdopodobnie nie jest doceniane.

Answer 1

Zastanów się również, jak duży jest twój wykres/matrycę, czy wydajność ma duże znaczenie? Czy wykres jest statyczny, czy może się rozrastać w czasie, np. dodając nowe krawędzie?

Answer 2

Należy zauważyć, że również można używać do tworzenia macierzy boost.ublas i manipulacji, a także boost.graph do reprezentowania i manipulować wykresów w kilka sposobów, jak również przy użyciu algorytmów na nich, itd

Edit: W każdym razie, robi wersję zakres sprawdzić w wektorze do swoich celów nie jest trudna rzecz:

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]; 
     } 
}; 

Uwaga że trzeba także dodać const wersję operatorów i/lub iteratory i dziwne wykorzystanie wyjątki, ale masz pomysł.

Answer 3

Pamiętaj, że std::vector nie sprawdza również zasięgu.

Answer 4

Co mogę zrobić, to stworzyć własną klasę do radzenia sobie z macierzami (prawdopodobnie jako tablicę [x * y], ponieważ jestem bardziej przyzwyczajony do C (i będę miał moje własne sprawdzanie granic), ale możesz używać wektorów lub dowolnej innej podstruktury w tej klasie).

Najpierw zacznij działać, a następnie przejmuj się szybkością działania. Jeśli prawidłowo zaprojektujesz klasę, możesz wyciągnąć implementację tablicy [x * y] i zastąpić ją wektorami lub maskami bitowymi lub cokolwiek chcesz, bez zmiany reszty kodu.

nie jestem całkowicie pewien, ale coś to właśnie zajęcia miały na zdolność do abstrakcyjnego realizacji dobrze poza zasięgiem wzroku i zapewniają tylko interfejs :-)

Answer 5

Najlepszy sposób:

Stwórz własną klasę macierzy, w ten sposób kontroluj każdy jej ostatni aspekt, w tym sprawdzanie zasięgu.

np. Jeśli podoba Ci się notacja "[x] [y]", wykonaj następujące czynności:

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; 

nb. Jeśli programujesz w ten sposób, C++ jest tak samo bezpieczny jak wszystkie inne "bezpieczne" języki.

Answer 6

Oprócz wszystkich odpowiedzi, które zostały przesłane do tej pory, warto sprawdzić numer C++ FAQ Lite. Pytania 13.10 - 13.12 i 16.16 - 16.19 obejmują kilka tematów związanych z rozwijaniem własnej klasy macierzy. Zobaczysz kilka różnych sposobów przechowywania danych i sugestie, jak najlepiej napisać operatory indeksów dolnych.

Ponadto, jeśli Twój wykres jest wystarczająco rzadki, możesz w ogóle nie potrzebować macierzy. Możesz użyć std::multimap do odwzorowania każdego wierzchołka na ten, który łączy.

Answer 7

Standardowy wektor NIE sprawdza domyślnie zakresu.

tj. Operator [] nie sprawdza zakresu.

Metoda w punkcie() jest podobna do [], ale wykonuje test zakresu.
Spowoduje to zgłoszenie wyjątku poza zakresem.

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

Inne uwagi: Dlaczego wektorem < Wskaźniki >?
Możesz całkiem łatwo mieć wektor <Obiekt>. Teraz nie musisz się martwić o zarządzanie pamięcią (np. Przecieki).

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

Uwaga: vector <bool> jest przeciążony i nie bardzo wydajne (tj struktura ta została zoptymalizowana pod kątem wielkości nie prędkość) (To jest coś, co jest obecnie uznawana za prawdopodobnie omyłkowo przez Komitet Standardów).

Jeśli znasz rozmiar macierzy podczas kompilacji, możesz użyć std :: bitset?

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

lub jeśli jest zdefiniowany impuls Runtime use :: dynamic_bitset

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

Wszystkie powyższe pozwoli Ci zrobić:

m[6][3] = true; 

Answer 8

Jeśli chcesz wydajności macierzy 'C' , ale z dodatkowym zabezpieczeniem i semantyką podobną do STL (iteratory, begin() & end() itp.), użyj boost::array.

Zasadniczo jest szablonowym opakowaniem dla macierzy C z niektórymi sprawdzającymi zakresów wartościami z zakresu NDEBUG (a także niektórymi akcesoriami do wyrzucania wyjątków std::range_error).

używam takich rzeczy

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

zamiast

float m[4][4]; 

cały czas i działa świetnie (z odpowiednimi typedefs zachować szczegółowość w dół, w każdym razie).

---

UPDATE: obserwuję dyskusję tu względnej wydajności boost::array vs boost::multi_array komentarzach, chciałbym podkreślić, że ten kod, skompilowany z g++ -O3 -DNDEBUG na Debianie/Lenny amd64 na Q9450 z 1333MHz DDR3 RAM ma 3.3s dla boost::multi_array vs 0.6s dla 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 9

Prawdopodobnie nie ma znaczenia, jak jest to stara sprawa, ale można korzystać z biblioteki Armadillo, który zapewnia wiele typów danych liniowych zorientowane algebra i funkcji.

Poniżej znajduje się przykład dla konkretnego problemu:

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

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

Answer 10

mój ulubiony sposób na przechowywanie wykresu vector<set<int>>; n elementów w wektorze (węzły 0..n-1),> = 0 elementów w każdym zestawie (krawędzie). Nie zapomnij o dodaniu odwróconej kopii każdej dwukierunkowej krawędzi.