14

Quad-/octree データ構造があります。セルの子インデックス/ptrsを配列に格納しています。配列内の各位置は、親に対する子の位置を表します (例: 2D):

// _____________
// |     |     |
// |  2  |  3  |
// |_____|_____|
// |     |     |
// |  0  |  1  |
// |_____|_____|
// for each cell, 4 children are always stored in row-major order
std::vector<std::array<Integer,4>> children;

Integer子の最大数は、型が表現できる値のサブセットであることを知っています。-1したがって、 forInteger = intやstd::numeric_limits<unsigned>::max()forのような「魔法の」値を使用して、セルに子がないかどうかを識別できますInteger = unsigned。これはstd::optional<Integer>想定できないことです。

私が理解している限りでは、この魔法の値の使用は の存在理由の 1 つですstd::optional。std::vector<std::optional<int>>それでも、 in inner loops の性能が気になります。

そう、

  • のパフォーマンスは のパフォーマンスstd::vector<std::optional<int>>より悪くなりstd::vector<int>ますか? （私はすでに「存在しない」値の比較を行っています）。

  • std::optionalまたは、 raw と同じパフォーマンスを提供するようにの実装を最適化できintますか? そしてどうやって？

関数の戻り値の型とマジック値をデータ構造に混在std::optionalさせるのは、非常に悪い考えのように思えます。私は一貫性を保ち、どちらか一方を (少なくとも同じコンテキスト内で) 使用することを好みます。マジック ナンバーとの比較を実行する関数をオーバーロードすることはできますが、次のようにします。

template<T> bool is_valid(const T& t) { 
  return /* comparison with magic value for t */; 
}

オプションタイプの場合。

4

2 に答える 2

14

std::optional追加のストレージが必要になり、キャッシュに収まる値が少なくなります (この理由は既にわかっているようです)。

内部表現がユーザーから完全に隠されている限り、パブリック API によって公開されたものとは異なる値をデータ構造に内部的に保存することは間違っているとは思いません。

さらに、マジック ナンバーを 1 組のinline変換関数に分離することをお勧めします。

コンパイラは、忘れた場合に型エラーを生成することにより、変換関数を一貫して使用することを覚えておくのに役立ちます。int暗黙的な変換が存在しないようにする (またはユーザー定義の変換を定義する) ために、内部データ構造の に薄い構造体ラッパーを使用することもできます。

class CompressedOptionalUInt
{
    static const unsigned SENTINEL_MISSING = std::numeric_limits<unsigned>::max();
    unsigned value;

public:
    CompressedOptionalUInt(std::optional<unsigned> val) : value(!val? SENTINEL_MISSING: *val) {}
    operator std::optional<unsigned>() const { ... }
};

を使用しますstd::array<CompressedOptionalUInt>。

型ごとにセンチネルを定義する必要があるだけで、それをテンプレートにするのは非常に簡単です。

于 2013-06-26T15:39:13.107 に答える
3

いいえ、それほど効率的ではありません。参照実装からわかるように、追加の値を保存、更新、およびチェックする必要があります。

于 2013-06-26T15:43:10.140 に答える