2

2 つの符号なし整数が与えられたとします。

size_t A, B;

それらにはいくつかの乱数がロードされており、A は B より大きい、等しい、または小さい可能性があります。A から B にループしたいのですが、比較とインクリメントはどちらが大きいかによって異なります。

for (size_t i = A; i <= B; ++i) //A <= B
for (size_t i = A; i >= B; --i) //A >= B

明白なブルート フォース ソリューションは、これらを if ステートメントに埋め込むことです。

if (A <= B)
{
 for (size_t i = A; i <= B; ++i) ...
}
else
{
 for (size_t i = A; i >= B; --i) ...
}

AからBにループする必要があることに注意してください。したがって、2 つの中間整数を使用して、A と B を正しいスロットに投げてから、同じ比較とインクリメントを行うことはできません。「A の方が大きい」場合は、デクリメントする必要があり、反対の場合はインクリメントする必要があります。

これと同じセットアップを必要とするネストされたループが多数ある可能性があります。つまり、すべての if/else に関数呼び出しがあり、多くの変数を渡す必要があるか、別の if/else と別の if/else などを渡す必要があります。

速度をあまり犠牲にすることなくこれを回避するためのトリッキーなショートカットはありますか? タイトで頻繁に繰り返されるループ内の関数ポインターなどは、私にとって非常に苦痛に聞こえます。クレイジーなテンプレート ソリューションはありますか?

4

4 に答える 4

7

私の間違い、もともと質問を誤解していました。

Aからへの包括的なループを作成するBには、トリッキーな状況があります。Bを 1 つ過ぎてループする必要があるため、ループの前にその値を計算します。ループ内でコンマ演算子を使用しましたforが、わかりやすくするためにいつでも外側に置くことができます。

int direction = (A < B) ? 1 : -1;
for( size_t i = A, iEnd = B+direction; i != iEnd; i += direction ) {
    ...
}

Aと を変更しても構わない場合Bは、代わりにこれを行うことができます (Aループ変数として使用):

for( B+=direction, A != B; A += direction ) {

}

そして、私は遊んでいました...関数ポインターに関してインライン化のルールが何であるか、またはこれがより速いかどうかはわかりませんが、いずれにしても演習です。=)

inline const size_t up( size_t& val ) { return val++; }
inline const size_t down( size_t& val ) { return val--; }

typedef const size_t (*FnIncDec)( size_t& );

inline FnIncDec up_or_down( size_t A, size_t B )
{
    return (A <= B) ? up : down;
}

int main( void )
{
    size_t A = 4, B = 1;
    FnIncDec next = up_or_down( A, B );

    for( next(B); A != B; next(A) ) {
        std::cout << A << endl;
    }

    return 0;
}

これに応えて：

これは、A = 0、B = UINT_MAX (およびその逆) の場合には機能しません。

それは正しいです。問題は、オーバーフローにより との初期値が同じiになることです。iEndこれを処理するには、代わりにdo->whileループを使用します。これにより、最初のテストが削除されます。これは、常にループ本体を少なくとも 1 回実行するため冗長です...最初のテストを削除することにより、最初の終了条件を超えて反復します。

size_t i = A;
size_t iEnd = B+direction;

do {
    // ...
    i += direction;
} while( i != iEnd );
于 2012-12-13T21:40:24.557 に答える
5 
size_t const delta = size_t(A < B? 1 : -1);
size_t i = A;
for( ;; )
{
    // blah

    if( i == B ) { break; }
    i += delta;
}
于 2012-12-13T22:10:25.920 に答える
2

繰り返される値をどうしますか？

これが配列内のインデックスになる場合は、関連するクラスiteratorまたはreverse_iteratorクラスを使用し、これらの周りにアルゴリズムを実装する必要があります。コードはより堅牢になり、保守や進化が容易になります。さらに、標準ライブラリの多くのツールは、これらのインターフェイスを使用して構築されています。

実際には、そうでない場合でも、独自のインデックスを返すイテレータクラスを実装できます。

メタプログラミングの魔法を少し使って、イテレータがとの順序に従ってどのように動作するかを定義することもできAますB。

先に進む前に、これはとの定数値でのみ機能することを考慮してください。AB

template <int A,int B>
struct ordered {
    static const bool value = A > B ? false: true;
};

template <bool B>
int pre_incr(int &v){
    return ++v;
}

template <>
int pre_incr<false>(int &v){
    return --v;
}

template <int A, int B>
class const_int_iterator : public iterator<input_iterator_tag, const int>
{
    int p;
  public:
    typedef const_int_iterator<A,B> self_type;
    const_int_iterator() : p(A) {}
    const_int_iterator(int s) : p(s) {}
    const_int_iterator(const self_type& mit) : p(mit.p) {}
    self_type& operator++() {pre_incr< ordered<A,B>::value >(p);return *this;}
    self_type operator++(int) {self_type tmp(*this); operator++(); return tmp;}
    bool operator==(const self_type& rhs) {return p==rhs.p;}
    bool operator!=(const self_type& rhs) {return p!=rhs.p;}
    const int& operator*() {return p;}
};


template <int A, int B> 
class iterator_factory {    
  public:
    typedef const_int_iterator<A,B> iterator_type;
    static iterator_type begin(){
        return iterator_type();
    }
    static iterator_type end(){
        return iterator_type(B);
    }
};

上記のコードでは、AからBの値にまたがるベアボーンiteratorクラスを定義しました。AとBが昇順であるかどうかを判断し、正しい演算子（++または--）を選択して値を調べる簡単なメタプログラミングテストがあります。

最後に、保持する単純なファクトリクラスbeginとendイテレータメソッドも定義しました。このクラスを使用すると、依存型の値AとBに対して単一の宣言ポイントのみを使用できます（ここでは、AとBを1回だけ使用する必要があります。このコンテナ、およびそこから生成されるイテレータは、これらの同じAとBに依存するため、コードがいくらか単純化されます）。

ここでは、20から11までの値を出力する簡単なテストプログラムを提供します。

#define A 20
#define B 10

typedef iterator_factory<A,B> factory;

int main(){

   auto it = factory::begin();

   for (;it != factory::end();it++)
      cout << "iterator is : " << *it << endl;

}

ただし、標準ライブラリを使用してこれを行うためのより良い方法があるかもしれません。

との使用OとUINT_MAXのためAの問題Bが提起されました。これらの特定の値を使用してテンプレートをオーバーロードすることで、これらのケースを処理できるはずだと思います（読者の演習として残しておきます）。

于 2012-12-13T23:44:29.053 に答える
0 
size_t A, B;

if (A > B) swap(A,B);  // Assuming A <= B, if not, make B to be A

for (size_t i = A; A <= B; ++A) ...
于 2012-12-13T22:09:41.517 に答える