Vectorへのオブジェクト格納-2

[戻る]
Baby Chicken [HomePage] 2009/11/03(火) 04:49:48
先日は多くのご回答ありがとうございました。今度はVC++2008 on Vistaで以下のプログ
ラムを作り試しました。
#include <iostream>
#include <vector>
using namespace std;

class A {
    int a;
    static int id;
public:
    A() {
        a = ++id;
        cout << "A(" << a << ") is generated.\n";
    }
    A(const A& obj) {
        this->a = obj.a;
        cout << "A(" << a << ") is copied\n";
    }
    virtual ~A() {
        cout << "A(" << a << ") is deleted.\n";
    }
};
int A::id = 0;

int main() {
    vector<A> groupA;
    for (int i=0; i<4; ++i) {
        groupA.push_back(A());
        cout << "**** Loop " << i+1 << " *****\n";
    }
    char ch;
    cin >> ch;
}

そうすると意外にことに
A(1) is generated.
A(1) is copied
A(1) is deleted.
**** Loop 1 *****
A(2) is generated.
A(1) is copied
A(2) is copied
A(1) is deleted.
A(2) is deleted.
**** Loop 2 *****
A(3) is generated.
A(1) is copied
A(2) is copied
A(3) is copied
A(1) is deleted.
A(2) is deleted.
A(3) is deleted.
**** Loop 3 *****
A(4) is generated.
A(1) is copied
A(2) is copied
A(3) is copied
A(4) is copied
A(1) is deleted.
A(2) is deleted.
A(3) is deleted.
A(4) is deleted.
**** Loop 4 *****
A(1) is deleted.
A(2) is deleted.
A(3) is deleted.
A(4) is deleted.
という出力でした。そこで質問です

[I] 出力から判断すると、多分Vectorの中で格納領域拡大が行われ、その際にcopyが作
られると考えましたが、その考えで良いのでしょうか?
{II} それにしても、何故Loop 3とLoop 4の間でA(1)からA(4)までのコピーが作成される
のでしょうか?
ちなみに、Ubuntu 9.10で走らせたgcc 4.4.1ではこれまた違う出力
A(1) is generated.
A(1) is copied.
A(1) is deleted.
***** Loop 1********
A(2) is generated.
A(2) is copied.
A(1) is copied.
A(1) is deleted.
A(2) is deleted.
***** Loop 2********
A(3) is generated.
A(3) is copied.
A(1) is copied.
A(2) is copied.
A(1) is deleted.
A(2) is deleted.
A(3) is deleted.
***** Loop 3********
A(4) is generated.
A(4) is copied.
A(4) is deleted.
***** Loop 4********
A(1) is deleted.
A(2) is deleted.
A(3) is deleted.
A(4) is deleted.
が得られました。
どうにも面白い現象と思われましたのでご報告兼ねて質問させて頂きました。ちなみに、
vector<A> groupA(100);とかするとまたとんでもない結果出力となりました。宜しくご指
導お願いします。

tetrapod 2009/11/03(火) 07:06:06
どちらも 「それが vector の仕様」としか言いようが無い

vector は、中で持っている要素のためのメモリ領域が連続していることが仕様。
だから *要素用領域* を拡張しなければならない状況になったら、
・別のアドレスに新しい領域を取る
・古い領域から新しい領域にコピーコンストラクタでプレースメントコピーする
・古い領域に対してデストラクタが呼ばれる
ということだ

vector::reserve と vector::size の違いがわかるかな?
vector<A> groupA; の直後に
groupA.reserve(100); とかしておけばどう挙動するか、理解できるかな?
groupA.reserve(100); と vector<A> groupA(100); の違い、わかっているかな?

ついでに vector と list の違いまで理解できれば完璧。

Baby Chicken [HomePage] 2009/11/03(火) 07:23:59
早速のご回答ありがとうございます。reserveとかsizeについてこれまで深く考えていませ
んでした。試みてみます。
ただ、書籍で読んだこれまでの解説では、vectorは予め大きめの領域を確保していると思っ
ていましたので、class Aをたかだか2つや3つで「新たに連続領域」を確保しにいくのが理
解できないのですが・・・

tetrapod 2009/11/03(火) 07:49:26
vector<T> a; だけだと0個の領域しか取らない (これは規格書が定めている) ので
最初の push_back で必ず確保が行われる。
現在の reserve がいくつであっても push_back を繰り返していけばそのうち
領域拡張が必要になるわけだが、その拡張の際に具体的に何個分を reserve するかは
規格書で何も決めていない話なので実装依存。

自動拡張では 1 → 2 → 4 → 8 → 16 → って倍々ゲームな実装が多いみたいだよ
高々数個しか入れない vector に多量の reserve があってもメモリの無駄だし・・・
大量にデータを保持したい場合にはプログラマ側があらかじめ要素数を見積もって
reserve しておくほうがいい (大量データが暗黙自動拡張されると性能低下する)

前回書き忘れたけど
A::A() { a と this を表示 }
A::A(const A& that) { that.a と this と &that を表示 }
A::~A() { a と this を表示 }
とすると理解しやすいかも

Baby Chicken [HomePage] 2009/11/03(火) 15:55:06
[[解決]]
tetrapod様

c++の規格にまで言及されてのご親切な説明ありがとうございます。またcopy constructor
などでの表示についてもヒントを与えて下さり感謝します。
領域確保については分かったのですが、どうしてコピーが必要以上に(例えば4回目に
push_backすると、A(1)からA(4)までコピーされる・・・)というのがピンとこないのです
が・・・
物分かり悪くてすみません

Ban 2009/11/03(火) 17:02:51
> 領域確保については分かったのですが、どうしてコピーが必要以上に
> (例えば4回目にpush_backすると、A(1)からA(4)までコピーされる・・・)
> というのがピンとこないのですが・・・

> vector は、中で持っている要素のためのメモリ領域が連続していることが仕様。
   -- snip --
> ということだ

上にもあるように、vectorの場合、内部のメモリ領域は「全て連続してなければ
ならない」わけです。
しかし、今の領域が足りなくなったとき、もし古いデータを新しい領域に
移動させなければ、当然古いデータと新しいデータは別の場所に格納されてしまい、
連続しません。ゆえに、古いデータは移動されることになります。
(C言語由来のreallocを想起してもらうと分かりやすい人もいるかと思いますが)

# 隣家が空き家だろうがなんだろうが、家族が増えて部屋が足りなくなった時には、
# 一家そろって全員引っ越す(常に一つ屋根の下で暮らす)のがvectorの仕様。
# (これが例えばdequeだと、隣の家を借りて住む事もある
#  <どちらも一長一短がありますし、故にこそ複数のコンテナがあるわけです)

Baby Chicken [HomePage] 2009/11/04(水) 00:51:33
[[解決]]
Ban様

ありがとうございます。

tetrapod 2009/11/04(水) 10:28:09
なんとなく納得がいっていないような雰囲気・・・

Q. 新しい要素を push_back しているだけのに
一見無関係に見える 1 や 2 がデストラクト・コンストラクトされているのはなぜか?
A. みんなで一斉にお引越ししているから
なわけだが・・・もしかして

「ただのメモリ領域」と「オブジェクト」の違いがわかっていない?
malloc と new の違いは理解できている?その辺の認識がきっちりしていないと
capacity と size の違いがわからないはず。
reserve と resize の違いがわからないはず。
まずはその辺から、かな・・・

Baby Chicken [HomePage] 2009/11/05(木) 17:40:18
tetrapod様

ありがとうございます。見透かされました。malloc vs new, capacity vs sizeなど分かっ
ているつもりです(でも分かっていないのかも・・・)。
僕が驚いたのは、実はたとえば
vector <A> groupA(100);
とすると、
groupA.push_back((A());
としただけで、copyが100個も作られてしまった、という点です。こんなことは想像してい
ませんでした。
こんなこと本には書いていませんでしたので、正直驚きました。速度とかメモリーとかがク
リティカルな状況ではかなり効いてくるのでは? と思いました。
今後も宜しくご指導お願いします。

tetrapod 2009/11/05(木) 19:15:44
# やっぱり仕様を理解しないで使っているようにしか見えないわけだが

vector<T> v(NNN); とすると要素が NNN 個作られる。
この場合 v.size() == v.capacity() == NNN になってしまうので、
さらに1個 push_back すると再配置が発生してしまうわけだ。

> copyが100個も作られてしまった
何か微妙に誤解していないだろうか?
お引越ししたので要素が1つづつコピーされ、合計100個の要素のコピーが作られ
(当然ながら引越し中は旧宅と新宅の両方のメモリ領域が必要)
引越し完了後は旧宅にあった要素100個はすべてデストラクトされ
その後、旧宅は取り壊され更地になる=空きメモリになるわけだけど
vector 自体の copy が100個作られたわけではないぞ。

> こんなこと本には書いていませんでしたので
書いてないのかな・・・少なくとも言語規格書には書いてある。

> 速度とかメモリーとかがクリティカルな状況ではかなり効いてくるのでは?
vector は、最初から再配置が発生することを許容して使うもの。
もしくは、再配置が起こらないように工夫して使うもの。

vector<T> v; // 要素数0個でとりあえず作成
v.reserve(NNN); // NNN 個以下で使う限り再配置は発生しない
v.push_back(...);

再配置による性能低下よりも、要素の連続性が優先される場合であるとか
要素数をあらかじめ見積もれる状況で適切な容量を reserve してから使うもんだ。
途中への要素追加とか、途中の要素の削除がある場合には vector は不向き。

list は逆。
原理的に再配置が発生しない代わりに要素はメモリ上で不連続になっている。
追加・挿入・削除が多い状況では list のほうが vector より適切。
ただし同じ個数の要素を保持するには vector より list のほうがメモリを食う。

コンテナってのは状況に応じて使い分ける代物なんだ(既出)

Baby Chicken [HomePage] 2009/11/05(木) 20:11:07
tetrapod様

「vector<T> v(NNN); とすると要素が NNN 個作られる。この場合 v.size() == 
v.capacity() == NNN になってしまうので、さらに1個 push_back すると再配置が発生
してしまうわけだ。」なのですね
ただ、ある有名なC++の解説ホームページで以下の記述がありましたので、誤解していま
した。
**********************************************
vectorはstdという名前空間に含まれています。vectorをインスタンス化するとき、要素
数を指定する 必要はありません。必要に応じて(ただし、正しく使用している場合)動
的に要素数が追加されます。動的に追 加されるということは、vectorクラスの内部でメ
モリ確保を行っているので、場合によっては処理速度の問題が 起こるかも知れません。
それが問題になる場合、コンストラクタにint型の引数を与えれば、それに従ってあ らか
じめ要素を確保してくれます。

vector<int> array(10);  // 初期状態で10個分のメモリ空間を持つint型の動的配列
**********************************************
この記述に従えば、(n)で確保した後 push_backすればその最初から確保され、引っ越し
は起こらないと思いました。

すみません何度も

επιστημη [E-Mail] [HomePage] 2009/11/06(金) 10:35:22
> ある有名なC++の解説ホームページ

どこですかそれ。
かなりウソっぽい。

vector<int> array(10); 
こいつは最初っから10個の要素が挿入された状態でarrayを作ります。

領域だけを確保したいなら
vector<int> array;
array.reserve(10);
であるはず。

YuO [E-Mail] 2009/11/06(金) 11:22:01
引用文から探すと,恐らく
http://www.geocities.jp/ky_webid/cpp/library/002.html
だと思うのですが……。
# 引用するときには出典を書くのが「公正な慣行」だと思っていたのですが……。

ただ,上記ページにはちゃんと
> この場合、要素はデフォルトコンストラクタで初期化されます。
と書いてあるんですけどね。
さらに,直後には
> の場合、代わりの手段として reserve() を使います。
というreserveの説明まであります。

επιστημη [E-Mail] [HomePage] 2009/11/06(金) 11:29:01
↑あ、それなら正しいすね。

vector<int> array(10); なら size():10, capacity():10以上

vector<int> array;
array.reserve(10); なら size():0, capacity():10以上

となるます。

tetrapod 2009/11/06(金) 11:39:26
冒頭の文書でぐぐってみた
http://www.geocities.jp/ky_webid/cpp/library/002.html
だとすると、提示文書の直後に「代わりの手段として reserve() しろ」とある。

・・・っていうかこのページわかりにくい・・・
reserve が要素を確保すると書いてある。これは不正確/誤りだね。

reserve が確保するのは「要素として使うためのメモリ領域」
resize/個数指定 constructor は「 reserve + 要素をコンストラクトする」

コンストラクト済み要素と、まだ要素になっていないメモリ領域はまったく別物。
提示ページはこの両者の区別を正しく行っていない/故意に省略しているね。

古いスレッドには追加発言できません。