Een juiste manier om een ​​matrix in C++

Ik wil een aangrenzende matrix maken voor een grafiek. Aangezien ik het lees, is niet veilig om arrays van het formulier matrix[x][y]te gebruiken omdat ze niet controleren op bereik, besloot ik de vector sjabloonklasse van de STL te gebruiken. Alles wat ik nodig heb om in de matrix op te slaan, zijn Booleaanse waarden. Dus mijn vraag is, als het gebruik van std::vector<std::vector<bool>* >*produceert te veel overhead of als er een eenvoudiger manier is voor een matrix en hoe ik goed kan initialiseren.

EDIT: Heel erg bedankt voor de snelle antwoorden. Ik heb me net gerealiseerd dat ik natuurlijk geen aanwijzingen nodig heb. De grootte van de matrix wordt in het begin rechtstreeks geïnitialiseerd en zal niet veranderen tot het einde van het programma. Het is voor een schoolproject, dus het zou goed zijn als ik “Nice” -code schrijf, hoewel technisch prestaties niet al te belangrijk is. Het gebruik van de STL is prima. Iets als boost gebruiken, wordt waarschijnlijk niet op prijs gesteld.

Antwoord 1, Autoriteit 100%

Merk op dat u ook boost. Ublas voor Matrix-creatie en manipulatie en ook boost .graph om grafieken op een aantal manieren weer te geven en te manipuleren, evenals het gebruik van algoritmen op hen, enz.

Bewerken : Hoe dan ook, een bereik-controleversie van een vector voor uw doeleinden doen is niet moeilijk:

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

Merk op dat je ook de const-versie van de operators en/of iterators en het vreemde gebruik van uitzonderingen zou moeten toevoegen, maar je snapt het idee.

Antwoord 2, autoriteit 55%

Beste manier:

Maak je eigen matrixklasse, op die manier heb je controle over elk laatste aspect ervan, inclusief bereikcontrole.

bijv. Als je de “[x][y]”-notatie leuk vindt, doe dit dan:

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. Als je zo programmeert, is C++ net zo veilig als al die andere “veilige” talen.

Antwoord 3, autoriteit 45%

De standaardvector voert standaard GEEN bereikcontrole uit.

d.w.z. De operator[] voert geen bereikcontrole uit.

De methode at() is vergelijkbaar met [] maar voert een bereikcontrole uit.
Het zal een uitzondering op buiten bereik gooien.

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

Andere opmerkingen:
Waarom een vector<Pointers> ?
U kunt vrij gemakkelijk een vector<Object> hebben. U hoeft zich nu geen zorgen meer te maken over geheugenbeheer (d.w.z. lekken).

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

Opmerking: vector<bool> is overbelast en niet erg efficiënt (d.w.z. deze structuur is geoptimaliseerd voor grootte en niet voor snelheid) (het is iets dat nu wordt erkend als waarschijnlijk een fout door de normcommissie).

Als je de grootte van de matrix weet tijdens het compileren, kun je std::bitset gebruiken?

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

of als het runtime-gedefinieerd is, gebruik boost::dynamic_bitset

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

Met al het bovenstaande kunt u het volgende doen:

m[6][3] = true;

Antwoord 4, autoriteit 23%

Als u ‘C’-arrayprestaties wilt, maar met extra veiligheid en STL-achtige semantiek (iterators, begin()& end()enz.), gebruikt u boost::array.

Eigenlijk is het een template-wrapper voor ‘C’-arrays met enkele NDEBUG-disable-able bereikcontrole-beweringen (en ook enkele std::range_erroruitzondering-throwing accessors ).

Ik gebruik dingen als

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

in plaats van

float m[4][4];

altijd en het werkt geweldig (met de juiste typedefs om de breedsprakigheid in ieder geval laag te houden).

UPDATE:Na enige discussie in de opmerkingen hier over de relatieve prestaties van boost::arrayversus boost::multi_array, heb ik d wijzen erop dat deze code, gecompileerd met g++ -O3 -DNDEBUGop Debian/Lenny amd64 op een Q9450 met 1333MHz DDR3 RAM 3,3 seconden nodig heeft voor boost::multi_arrayvs 0,6 s voor 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;
}

Antwoord 5, autoriteit 18%

Wat ik zou doen is mijn eigen klasse maken voor het omgaan met matrices (waarschijnlijk als een array[x*y] omdat ik meer gewend ben aan C (en ik zou mijn eigen grenzen controleren), maar je zou vectoren of een andere substructuur in die klasse).

Zorg ervoor dat je spullen eerst functioneel zijn en maak je dan zorgen over hoe snel het werkt. Als je de klasse goed ontwerpt, kun je je array[x*y]-implementatie eruit halen en deze vervangen door vectoren of bitmaskers of wat je maar wilt, zonder de rest van de code te veranderen.

Ik weet het niet helemaal zeker, maar ik denk dat daar klassen voor zijn bedoeld, de mogelijkheid om de implementatie goed uit het zicht te abstraheren en alleen de interface te bieden 🙂

Antwoord 6, autoriteit 14%

Naast alle antwoorden die tot nu toe zijn gepost, kunt u er goed aan doen om de C++ FAQ Lite. Vragen 13.10 – 13.12en 16.16 – 16.19behandelen verschillende onderwerpen met betrekking tot het zelf rollen matrix klasse. U ziet een aantal verschillende manieren om de gegevens op te slaan en suggesties over hoe u de subscriptoperators het beste kunt schrijven.

Als je grafiek voldoende schaars is, heb je misschien helemaal geen matrix nodig. Je zou std::multimapkunnen gebruiken om elk hoekpunt toe te wijzen aan de punten die het verbindt.

Antwoord 7, autoriteit 14%

mijn favoriete manier om een grafiek op te slaan is vector<set<int>>; n elementen in vector (knooppunten 0..n-1), >=0 elementen in elke set (randen). Vergeet niet een omgekeerde kopie van elke bidirectionele rand toe te voegen.

Antwoord 8, autoriteit 5%

Overweeg ook hoe groot is uw grafiek / matrix, doet prestatievergelijk veel? Is de grafiek statisch, of kan het in de loop van de tijd groeien, b.v. Door nieuwe randen toe te voegen?

Antwoord 9, Autoriteit 5%

Waarschijnlijk niet relevant omdat dit een oude vraag is, maar u kunt de armadillo gebruiken Bibliotheek, die veel lineaire algebra georiënteerde gegevenstypen en -functies biedt.

Hieronder is een voorbeeld voor uw specifieke probleem:

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

Antwoord 10, Autoriteit 5%

MINST U std::vectormaakt het bereik ook niet aan.