5034


本家の方でちょっと[議論](https://stackoverflow.com/questions/28070669/storage-mapping-
function-for-multi-array-
in-c/28070811#28070811)になったのですが、英語には弱く知識も不十分ということもあって英語での議論では相手の主張がよく納得ができなかったのでこちらで質問させて頂きたいと思います。

簡単な例を挙げれば、`short array[n][m];`という配列がある時、

[code]

    short *p = &array[0][0];
    for(int i = 0;i < n*m; ++i)
        *p++ = 1;
    
[/code]

は、

[code]

    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            array[i][m] = 1;
    
[/code]

と  
同じ挙動をすることが保証されているか？  
言い換えれば、２次の配列はその最小要素(つまり`short int`)が連続していることが保証されているか？  
ということです。

標準では、「配列はその要素は連続しており隙間はない」とされていますが、  
その方の主張によると、  
「１次元配列は確かにそうであるが、２次元配列は必ずしもそうではない。」  
例えば`short a[2][7];`のような副配列を考える時、  
Ｃでは２次元配列は配列の配列であり、その意味で要素として`short [7];`は隙間なく連続しているが、  
副配列である`short [7];`の最後には調整パディングが付与されているかもしれない。  
そのような場合2次元配列全体としてみると連続していない。  
（つまり先述の例のような場合の動作は保証されない）

確かに副配列の最後にパディングが存在しても標準の言と矛盾しないとは思いますが、  
そもそもそのような（配列でパディングが付与される）ことがあるのかどうかも疑問です。  
（構造体でメンバー間でパディングがある場合があることは承知しています、しかし配列の最後にパディングが付与され`sizeof(short[7])`が`8*sizeof(short)`になるとは思えません。）  
例えば、`short a[4];`も`short b[5];`もアラインメントの問題なくアクセスできます、  
そのような手段がある(つまり最小構成要素である`short`にアクセスできる)中で`short a[14]`(連続している)を解釈上`short
a[2][7];`(不連続である？)と内部の表現が違うというのは納得できません。  
そのようなパディングがそもそも必要無いと思うし、  
もしそのようなパディングが存在するような内部イメージを持つならアドレス演算を複雑にするだけだと思います。(Ｃの理念に反する？)

また、対象としている配列が

[code]

    sizeof(array) == n*m*sizeof(array[0][0])
    
[/code]

が真である場合にはそのようなパディングが存在しない、  
なので、この場合連続であるといってもよく、先述の例の動作は保証される。  
と思ったのですが、  
「それでも動作は保証されない。境界制約のルールに違反する。」  
と言われました。  
私の理解としては、`short *p = &array[0][0];`
のようなことは最小構成要素が同じ`short`であり、連続している場合（つまりメモリのサイズが同じでパディングを有していないと考えられる場合）問題無いと思えます。(逆に最小構成要素が異なる場合、例えば`char
*`を`int *`に変換して`int`でアクセスすることは問題がある。)

私の理解が間違っているとしたら何が間違っているのでしょうか？  
このようなこと（連続か不連続か）をハッキリさせるような文言が標準にありますか？

* * *

長くて要点がはっきりしない部分もあると思うのでまとめを追加します。

Ｑ：多次元配列は不連続か？（不連続の意味合いの説明はもういいと思うので略）  
Ａ：  
標準に記載がない以上、連続かも知れないし、不連続かもしれない。  
不連続かも知れないので不連続だとして扱う必要がある。  
（つまりサンプルコードの動作は保証されないものとしなければならない）

Ｑ：では、連続すると判断ができた場合のサンプルコードの動作は保証されるか？  
Ａ：（私の理解では保証される）

Ｑ：自分のシステム＋コンパイラで連続する（あるいは不連続）と判断するためにどのようなコードを書けばよいか？  
Ａ：（私の理解では`sizeof(array) == n*m*sizeof(array[0][0])`のようなもの）


CC BY-SA 3.0
2015-01-22T00:14:03.350
5022
2015-01-27T13:30:40.383
2017-05-23T12:38:56.083
-1
5044
question
c 言語仕様
２次元配列は不連続か？


私の解釈では以下の通りです。

  1. 2次元配列要素の連続性保証は直接明言されないが、演繹的には連続したメモリ配置であるといえる。
  2. ~~ただし、2次元配列上での1次元配列的な要素走査(`*p++`)は、その動作保証がなされない。~~
  3. 以上より、質問文中のサンプルプログラムは同じ挙動を示す。（そうならないC言語処理系は合理的に存在し得ないという態度）

以降の解釈は[WG14/N1256 ISO/IEC 9899:TC3](http://www.open-
std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)（C99言語仕様）に基づきます。

* * *

>   1. 2次元配列要素の連続性保証は直接明言されないが、演繹的には連続したメモリ配置であるといえる。
>

6.2.5/p20により、1次元配列(`short [7]`)ではその要素(`short`)の連続性が明らかに保証されます。2次元配列(`short
[2][7]`)の要素は1次元配列型(`short [7]`)であり、この1次元配列型の連続性が明らかに保証されます。2次元配列(`short
[2][7]`)の全要素の連続性が保証されるか否かは、その配列要素型`short
[7]`同士の"間"にパディングバイトが存在しえるかという問題に帰着できます。

> 20 Any number of derived types can be constructed from the object, function,
> and incomplete types, as follows:
>
>   * An array type describes **a contiguously allocated nonempty set of
> objects** with a particular member object type, called the element type.
> [...]
>   * [...]
>

6.5.3.4/p2-3には`sizeof`演算子は「オペランド式の型が占めるバイトサイズを返す」「オペランドが配列型の場合は、配列が占める総バイトサイズを返す」とあります。

> 2 The `sizeof` operator yields **the size (in bytes) of its operand** ,
> which may be an expression or the parenthesized name of a type. The size is
> determined from the type of the operand. The result is an integer. If the
> type of the operand is a variable length array type, the operand is
> evaluated; otherwise, the operand is not evaluated and the result is an
> integer constant.
>
> 3 [...] When applied to an operand that has array type, the result is **the
> total number of bytes in the array**. When applied to an operand that has
> structure or union type, the result is the total number of bytes in such an
> object, including internal and trailing padding.

`short
array[2][7];`では、`sizeof(array[0][0])`＝`short`型サイズ（例えば`2`）、`sizeof(array[0])`＝`sizeof(short[7])`つまり`short`型×`2`、`sizeof(array)`＝`sizeof(short[2][7])`つまり`sizeof(short[7])`x`2`＝`short`型×`2`×`7`となる
**べき**
です。先ほど懸念したパディングがどこかに存在すると仮定した場合、この制約を満たすことができなくなるため、パディングバイトはその存在が許されないと考えます。(下図参照）

[code]

    // 要素short型が*連続配置*された配列short[7]
    +---+---+-//-+---+
    | s | s | .. | s |  sizeof(short)*7 == sizeof(short[7])
    +---+---+-//-+---+
    
    // 要素(short[7])型が*連続配置*された配列short[2][7]
    +------+------+
    | s[7] | s[7] |  sizeof(short[7])*2 == sizeof(short[2][7])
    +------+------+
    
[/code]

これらより、配列要素数の計算式が期待通り動作すると保証されています。（6.5.3.4/p6は例示にすぎず、原理主義的立場では仕様(normative)ではありませんが、前掲解釈を増補するものとみなせます。）

> 6 EXAMPLE 2 Another use of the sizeof operator is to compute the number of
> elements in an array:  
>  `sizeof array / sizeof array[0]`

* * *

補足：@snakさんに指摘頂いた、配列実装のメモリレイアウトとして「末尾パディングはあり得ないのか？」という点について、英語版StackOverflowに質問"[Can
an array have trailing
padding?](https://stackoverflow.com/questions/27093290/)"がありました。付いていた回答の主張は、[私の解釈](https://ja.stackoverflow.com/questions/5022/#comment3693_5034)と同じで「そうする理由が存在しない」という点です。また、6.5.9/p6
`==`演算子セマンティクスを根拠として提示されていました。

> 6 Two pointers compare equal if and only if both are null pointers, [...] or
> one is a pointer to one past the end of one array object and the other is a
> pointer to the start of a different array object that happens to immediately
> follow the first array object in the address space. 94)
>
> 脚注94) Two objects may be adjacent in memory because they are adjacent
> elements of a larger array or adjacent members of a structure with no
> padding between them, or because the implementation chose to place them so,
> even though they are unrelated. If prior invalid pointer operations (such as
> accesses outside array bounds) produced undefined behavior, subsequent
> comparisons also produce undefined behavior.

* * *

2点目については、C99仕様の6.5/p7、いわゆるStrict Aliasing
Ruleにより保証がないと当初考えていました。ただ、改めて確認すると問題無いように思えたので、こちらの主張は取り下げます。


CC BY-SA 3.0
2015-01-22T03:32:05.427
5034
2015-01-22T10:16:09.800
2017-05-23T12:38:56.083
-1
49
5022
answer


**追記：yohjpさんとsnakさんの回答・コメントより、配列の配列も配列なんだから連続だ、ということが腑に落ちましたので下記回答は撤回します。**

コメント等の情報も加味して回答します。  
私の回答としては「不連続かもしれない」です。

前提の配列は以下。

[code]

    short array[2][7];
    
[/code]

※結果は妄想であって、各種コンパイラが用意できるはずもなく、検証はしていないです。

**1. パディング入れるよ、多次元配列も連続領域だよコンパイラ**

[code]

    sizeof(array) == 32
    2*7*sizeof(short) == 28
    
[/code]

**2. パディング入れるよ、多次元配列は連続領域じゃないよコンパイラ**

[code]

    sizeof(array) == 32
    2*7*sizeof(short) == 28
    
[/code]

**3. パディング入れないよ、多次元配列も連続領域だよコンパイラ**

[code]

    sizeof(array) == 28
    2*7*sizeof(short) == 28
    
[/code]

**4. パディング入れないよ、多次元配列は連続領域じゃないよコンパイラ**

[code]

    sizeof(array) == 28
    2*7*sizeof(short) == 28
    
[/code]

パディングなしの場合、`sizeof(short[7])`の評価は常に14で、それは`array[0][0]`のアドレスが`0x1000`で`array[1][0]`のアドレスが`0x2000`となっていても変わらないため、連続領域かそうでないかは区別が付かないと思いますがいかがでしょうか。

`sizeof`とパディングについて私が何か根本的に間違ってますか･･･？


CC BY-SA 3.0
2015-01-22T04:54:45.983
5045
2015-01-22T05:33:05.510
2015-01-22T05:33:05.510
7214
7214
5022
answer


あえて仕様を当たらず。

一般に配列`a`、型`type`について、

  1. `&a[N]`は `a + N`と常に同義である。
  2. `a + N` の結果は常に`&a[0] + sizeof(*a) * N`(ポインタ型を考慮しない単純加算)と一致する。
  3. `sizeof(type[M])`は常に`sizeof(type) * M`と一致する。

ことが保証されていれば、連続していると言えると思います。  
(そしてそれぞれ保証されているはず)

つまり

`short array[2][7];`  
があったとき

  1. `&array[1]` = `array + 1`
  2. `array + 1` = `&array[0] + sizeof(*array) * 1` (ポインタ型を考慮しない単純加算)
  3. `sizeof(*array)` = `sizeof(short[7])` = `sizeof(short) * 7`

ゆえに  
`&array[1]` = `&array[0] + sizeof(short) * 7` (ポインタ型を考慮しない単純加算)

この式は領域が連続していることを示していると思うわけです。

すなわち、メモリ内配置は

[code]

    array[0][0]
    array[0][1]
    array[0][2]
    array[0][3]
    array[0][4]
    array[0][5]
    array[0][6]
    array[1][0]
    array[1][1]
    array[1][2]
    array[1][3]
    array[1][4]
    array[1][5]
    array[1][6]
    
[/code]

と連続しており、array[0][6]とarray[1][0]の間にパディングは存在し得ないということです。


CC BY-SA 3.0
2015-01-22T06:58:35.673
5058
2015-01-22T15:35:00.690
2015-01-22T15:35:00.690
4765
4765
5022
answer


タグがCなのでオフトピ気味になりますが、C++だと、配列のサイズが要素のサイズ×要素数とあるので、配列の後ろにパディングが付かないことになりますね。

5.3.3 Sizeof p6 より引用:

> When applied to an array, the result is the total number of bytes in the
> array. This implies that the size of an array of n elements is n times the
> size of an element.

ISO/IEC 14882:2003, 2011, 2014 で、上記の存在を確認しました。


CC BY-SA 3.0
2015-01-26T15:13:59.537
5362
2015-01-26T15:13:59.537
7831
5022
answer


仮に多次元配列を1次元配列として扱えない処理系が存在するなら、それらの処理系ではcallocやmemset等を独自に拡張する必要があります。  
規格がそういった処理系も考慮しているなら、独自拡張しなくても済む仕様になってるはず。


CC BY-SA 3.0
2015-01-27T13:30:40.383
5436
2015-01-27T13:30:40.383
7504
5022
answer