30

グラフの隣接行列を作成したい。matrix[x][y]範囲をチェックしないため、形式の配列を使用するのは安全ではないことを読んだので、stl のベクトル テンプレート クラスを使用することにしました。マトリックスに格納する必要があるのはブール値だけです。だから私の質問は、使用std::vector<std::vector<bool>* >*するとオーバーヘッドが多すぎる場合、またはマトリックスのより簡単な方法と、それを適切に初期化する方法があるかどうかです。

編集:素早い回答をありがとう。もちろん、ポインターは必要ないことに気付きました。行列のサイズは最初に初期化され、プログラムの最後まで変更されません。これは学校のプロジェクト用なので、技術的にはパフォーマンスはそれほど重要ではありませんが、「いい」コードを書けばよいでしょう。STL を使用しても問題ありません。ブーストのようなものを使用することは、おそらく高く評価されていません。

4

10 に答える 10

10

標準ベクトルは、デフォルトでは範囲チェックを行いません。

つまり、operator[] は範囲チェックを行いません。

メソッド at() は [] に似ていますが、範囲チェックを行います。
範囲外で例外をスローします。

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

その他の注意事項: なぜ vector<Pointers> なのか?
vector<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;
于 2009-03-06T12:40:53.480 に答える
5

「C」配列のパフォーマンスが必要であるが、追加の安全性と STL のようなセマンティクス (反復子begin()などend()) が必要な場合は、 を使用しますboost::array

基本的には、いくつかのNDEBUG-disable-able 範囲チェック アサート (およびいくつかのstd::range_error例外スロー アクセサー) を持つ 'C' 配列のテンプレート化されたラッパーです。

私は次のようなものを使用します

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

それ以外の

float m[4][4];

常にうまく機能します(とにかく、冗長性を抑えるための適切なtypedefを使用します)。


更新:ここのコメントでboost::arrayvsの相対的なパフォーマンスに関するいくつかの議論に続いて、1333MHz DDR3 RAM を搭載した Q9450 で Debian/Lenny amd64 でboost::multi_arrayコンパイルされたこのコードは、 では3.3 秒、 では 0.6 秒かかることを指摘します。g++ -O3 -DNDEBUGboost::multi_arrayboost::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;
}
于 2009-03-06T13:51:55.293 に答える
4

私がすることは、行列を処理するための独自のクラスを作成することです (おそらく配列 [x*y] として)。これは、C に慣れているため (そして、独自の境界チェックがあるため)、ベクトルまたは任意のそのクラスの他の部分構造)。

最初に機能を確認してから、実行速度を心配してください。クラスを適切に設計すれば、配列 [x*y] の実装を取り出して、残りのコードを変更することなく、ベクターやビットマスクなど、必要なものに置き換えることができます。

完全にはわかりませんが、それがクラスの目的であり、実装を見えないように抽象化し、インターフェースのみを提供する機能だと思います:-)

于 2009-03-06T11:41:47.413 に答える
1

std::vector範囲チェックもしないことに注意してください。

于 2009-03-06T11:37:47.500 に答える