C/C++ 配列のインデックスとして使うべき型について

Question

質問

C言語、C++言語において配列のインデックスとして使うべき型は、size_t ですか？ptrdiff_t ですか？
すべてのインデックスが、ptrdiff_t 型で格納できる保証はありますか。

具体例

size_t

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

int main(void) {
  unsigned char str[1000000];
  const size_t size = sizeof(str) / sizeof(*str);

  for (size_t i = 0; i < size; ++i) {
    str[i] = i;
  }
  for (size_t i = size - 1; i != SIZE_MAX; --i) { // 補足: i < size を好む人もいる
    printf("%hhu ", str[i]); // 蛇足: 既定の実引数拡張があるから %u でいいの？
  }
}

ptrdiff_t

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

int main(void) {
  unsigned char str[1000000];
  const size_t size = sizeof(str) / sizeof(*str);

  for (ptrdiff_t i = 0; i < size; ++i) {
    str[i] = i;
  }
  for (ptrdiff_t i = (ptrdiff_t)size - 1; i >= 0; --i) {
    printf("%hhu ", str[i]);
  }
}

個人的な考え

結論 ptrdiff_t になるような気がしますが、そうなったとしても、

typedef ptrdiff_t index_t;

とでもして、index_t を使うべきかなと思っています。

Answer 1

size_t はオブジェクトのバイト数を表現するに足りる大きさを持つことになっています。 もちろん配列もオブジェクトであり、配列の大きさが配列のバイト数より大きいということはありませんから size_t がインデックスとして不足するということはありません。

一方で、 ptrdiff_t は一般的には size_t と同じ幅を持つものの、符号付きである分だけ表現可能な最大値は小さくなりますので表現不可能な場合が出てきてしまいます。 また、ポインタ同士の減算の結果を ptrdiff_t で表せなかった場合の結果は未定義であるということも明記されているので、そういう項目がある以上はそうなりうるということなんでしょう。

だた、常識的に言ってメモリ空間の半分以上をひとつのオブジェクトが占めるような状況はかなり特殊です。 インデックスは整数型であれば文法的には許容されるので使おうとしている配列の大きさを表せるだけの大きさがあれば十分です。 自分がやろうとしている状況に合わせて適切に見積もってください。

どういう状況で使われるのか想定しにくい汎用的なライブラリであればインデックスに使う型は size_t が間違いない方法ではあります。

Comments

[tails]

二つのポインタの減算の結果が ptrdiff_t で表現可能でない場合、その動作は未定義とする、という仕様が非常に残念ですね。
まあ仕方ないとも思いますが。
諦めて、size_t にします…

Answer 2

C言語、C++言語において配列のインデックスとして使うべき型は、size_t ですか？ptrdiff_t ですか？

この状況では、理論的にはsize_tです。ptrdiff_tは符号付きなので、「32ビット空間の4GiBメモリをすべてcharで確保した」というような極端な想定をすれば、後半が指せなくなってしまいます。

Comments

[tails]

ptrdiff_t の仕様が残念ですね…

Answer 3

intを使いますね。32bit環境では4GB付近までメモリを使いませんし。64bit環境ではsizeof(int) = 4なので巨大なデータを扱うときは要注意かもしれませんね。プログラムを見て思ったのですが、インデックスにこだわらずポインタをデクリメントしてみること、Cのmemset, memcpyなどを使うとCPUの拡張命令などを使って高速に演算できるのでそういったことにも気を使うといいのかと思いました。

#include <stddef.h>
#include <stdint.h>
#include <stdio.h>

int main(void) {
  unsigned char str[1000000];
  const size_t size = sizeof(str) / sizeof(*str);

  for (int i = 0; i < size; i++) {
    str[i] = i;
  }
  for (unsigned char *p = str + (size - 1); p >= str; --p) {
    printf("%hhu ", *p);
  }
}

Comments

[tails]

今回はインデックスとして適切なものはどちらか、という質問なので、可読性を下げる高速なプログラムを書きたいわけではありません。
また、示されたコードは未定義の動作を含みますので、ご注意ください。（p = str - 1 を指すことになるのと、size == 0 の時に問題がある）

ただ、インデックス操作よりもポインタ操作のほうがやはり高速なのでしょうか？
最適化によってインデックス操作はポインタ操作に置き換わるような気もしますが、その辺りと最適化との関連はどうなんだろう、と思います。
状況によるとは思いますが、あまりに可読性・移植性を犠牲にしてまで高速化に注力したくないです。

[tails]

あとは、インデックスとして int を使うことの是非ですが、ポインタに対して演算する際に、結局のところ、整数型はメモリ空間のアドレスサイズに拡張されるので、int がメモリ空間のアドレスサイズに対して小さければ、int を範囲内で制限させる分だけコストがかかるような気がしていましたが、単純なコードではアセンブリレベルで違いがみられませんでした。
なので、速度面からみれば特に問題なさそうではありますが、移植性の観点から見れば仕様上、int型は-32767から32767の範囲を保持できることしか保証がないため、これより大きいサイズをとる可能性があれば、int は問題があるかもしれません。

[anndonut]

p = str - 1が正当かということについては、私も知りたいです。intについて言えば、組み込みでは大きな配列を扱わない、Windowsなどでは32bitなので問題ない、という認識です。配列のインデックスとしてsize_tを使うのが正当だとみなさん認識してはいるのでしょうが、for (size_t ...というのは少しばかり衒学的な印象を受けるので特段理由がない限りはintでよいのではないかと考えます。forのi++を++iと書くといかがなものかとまさかりを投げる人もいないことはないと思いますし…

[tails]

JIS X 3010, 6.5.6 にあるように、
> （略）式Pが配列オブジェクトのi番目の要素を指している場合、式(P)+N及び(P)-N（Nは値nをもつと仮定する。）は、それらが存在するのであれば、それぞれ配列オブジェクトの i+n 番目及び i-n 番目の要素を指す。さらに、式Pが配列オブジェクトの最後の要素を指す場合、式(P)+1はその配列オブジェクトの最後の要素を一つ越えたところを指し、式Qが配列オブジェクトの最後の要素を一つ越えたところを指す場合、式(Q)-1はその配列オブジェクトの最後の要素を指す。ポインタオペランド及びその結果の両方が同じ配列オブジェクトの要素、又は配列オブジェクトの最後の要素を一つ越えたところを指している場合、演算によって、オーバーフローを生じてはならない。**それ以外の場合、動作は未定義とする。**

とあるように、str - 1 という演算は、C99において未定義の動作だと読み取っています。
他に、p = str + 999999; ++p; は問題ないですが、p = str + 1000000; はNGみたいです。

郷に入ったら郷に従うことにします（笑）
ただ、本当に理論上全く問題が起きないのは、size_t だというのは分かりました。