30

C++ 標準ライブラリのアルゴリズムを実装する方法を知りたいときは、常にhttp://en.cppreference.com/w/cpp/algorithmを調べます。これは優れた情報源です。しかし、実装の詳細を理解できない場合があり、特定の方法で何かが行われる理由を説明する必要があります。たとえば、 の実装ではstd::copy_n、最初の割り当てがループの外で行われ、ループが で始まるのは1なぜですか?

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
    if (count > 0) {
        *result++ = *first;
        for (Size i = 1; i < count; ++i) {
            *result++ = *++first;
        }
    }
    return result;
}

さらに: 可能なアルゴリズムの実装が説明されているサイトを知っていますか?

4

4 に答える 4

20

単純な実装と比較してください。

template< class InputIt, class Size, class OutputIt>
OutputIt copy_n(InputIt first, Size count, OutputIt result)
{
  for (Size i = 0; i < count; ++i) {
    *result++ = *first++;
  }
  return result;
}

firstこのバージョンでは、 !がもう 1 つインクリメントされます。

  1. count==0、どちらも0のインクリメントを行いますfirst。

  2. count==1、それらのバージョンはゼロインクリメントを行いfirstます。上記のバージョンは 1 を行います。

  3. count==2、それらのバージョンは の 1 つのインクリメントを行いfirstます。上記のバージョンは 2.

逆参照可能だがインクリメント可能ではないイテレータを処理する可能性があります。少なくとも STL の時代には、区別がありました。現在、入力イテレータにこのプロパティがあるかどうかはわかりません。

これは、素朴な実装を使用した場合に発生すると思われるバグです。また、「実際の読み取り操作は、反復子が逆参照されたときではなく、インクリメントされたときに実行される」と主張するドキュメントがあります。

逆参照可能でインクリメント不可能な入力反復子の存在について、章と節をまだ追跡していません。どうやら、標準はcopy_n入力/出力イテレータを逆参照する回数を詳しく説明していますが、入力イテレータをインクリメントする回数については詳しく説明していません。

単純な実装は、非単純な実装よりも入力反復子を 1 回インクリメントします。++不十分なスペースで読み取るシングルパス入力イテレータがある場合copy_n、入力ストリームの末尾を超えてデータを読み取ろうとして、それ以上の入力を不必要にブロックする可能性があります。

于 2013-07-15T20:42:26.177 に答える
13

それは単なる実装です。GCC 4.4 での実装は異なります (概念的にはより単純です)。

template<typename InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  for (; __n > 0; --__n)
{
  *__result = *__first;
  ++__first;
  ++__result;
}
  return __result;
}

[入力イテレータが入力イテレータの場合にのみ実装を提供したため、イテレータがランダム アクセス イテレータの場合は別の実装があります] その実装には、入力をインクリメントするというバグがあります。イテレータが予想よりも 1 回多い。

GCC 4.8 での実装はもう少し複雑です。

template<typename _InputIterator, typename _Size, typename _OutputIterator>
_OutputIterator
copy_n(_InputIterator __first, _Size __n,
     _OutputIterator __result)
{
  if (__n > 0)
{
  while (true)
    {
      *__result = *__first;
      ++__result;
      if (--__n > 0)
    ++__first;
      else
    break;
    }
}
  return __result;
}
于 2013-07-15T20:53:32.057 に答える
1

初診なので

if (count > 0)

count > 0 であることがわかっているため、そのコードの作成者は、値が 1 になるまで count に対して再度テストする必要はないと感じました。最後に。

Size count = 1;
for (Size i = 1; i < count; ++i) {
    std::cout << i << std::endl;
}

何も印刷しません。

したがって、コードは条件付き分岐を排除し、Size が 1 の場合、「最初に」インクリメント/調整する必要がなくなるため、プレインクリメントになります。

于 2013-07-15T20:42:51.750 に答える