みけCATのにっき（仮）
つれづれなるまゝに、日くらし、PCにむかひて、心に移りゆくよしなし事を、そこはかとなく書きつくれば、あやしうこそものぐるほしけれ。
（本当か！？）
出典

17番目だよ?!コピー祭り!!

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:
みけCAT に連絡する

17番目だよ?!コピー祭り!!

投稿記事 by みけCAT » 11年前

C++のstd::vectorに入れたオブジェクトがどのようなタイミングでコピーされているかを調べてみました。

CODE: 

#include 
#include 

class AsumiKana {
	private:
		int Nyaruko;
		int copyId;
	public:
		AsumiKana(int TatibanaMiya) {
			Nyaruko=TatibanaMiya;
			copyId=0;
			printf("AsumiKana %d-%d constructed.\n",Nyaruko,copyId);
		}
		AsumiKana(const AsumiKana& Ann) {
			Nyaruko=Ann.Nyaruko;
			copyId=Ann.copyId+1;
			printf("AsumiKana %d-%d copyed.\n",Nyaruko,copyId);
		}
		~AsumiKana() {
			printf("AsumiKana %d-%d destructed.\n",Nyaruko,copyId);
		}
		AsumiKana& operator=(const AsumiKana& Yuno) {
			Nyaruko=Yuno.Nyaruko;
			copyId=Yuno.copyId+1;
			printf("AsumiKana %d-%d substituted.\n",Nyaruko,copyId);
		}
		void introduce() const {
			printf("I am AsumiKana %d-%d.\n",Nyaruko,copyId);
		}
};

int main(int argc,char* argv[]) {
	std::vector KosigayaKomari;
	int N=5;
	if(argc>=2)sscanf(argv[1],"%d",&N); else scanf("%d",&N);
	for(int i=0;i<N;i++) {
		KosigayaKomari.push_back(AsumiKana(i+1));
	}
	for(int i=0;i<KosigayaKomari.size();i++) {
		KosigayaKomari[i].introduce();
	}
	return 0;
}
N=17での実行結果(http://ideone.com/t2j53h)

CODE: 

AsumiKana 1-0 constructed.
AsumiKana 1-1 copyed.
AsumiKana 1-0 destructed.
AsumiKana 2-0 constructed.
AsumiKana 2-1 copyed.
AsumiKana 1-2 copyed.
AsumiKana 1-1 destructed.
AsumiKana 2-0 destructed.
AsumiKana 3-0 constructed.
AsumiKana 3-1 copyed.
AsumiKana 1-3 copyed.
AsumiKana 2-2 copyed.
AsumiKana 1-2 destructed.
AsumiKana 2-1 destructed.
AsumiKana 3-0 destructed.
AsumiKana 4-0 constructed.
AsumiKana 4-1 copyed.
AsumiKana 4-0 destructed.
AsumiKana 5-0 constructed.
AsumiKana 5-1 copyed.
AsumiKana 1-4 copyed.
AsumiKana 2-3 copyed.
AsumiKana 3-2 copyed.
AsumiKana 4-2 copyed.
AsumiKana 1-3 destructed.
AsumiKana 2-2 destructed.
AsumiKana 3-1 destructed.
AsumiKana 4-1 destructed.
AsumiKana 5-0 destructed.
AsumiKana 6-0 constructed.
AsumiKana 6-1 copyed.
AsumiKana 6-0 destructed.
AsumiKana 7-0 constructed.
AsumiKana 7-1 copyed.
AsumiKana 7-0 destructed.
AsumiKana 8-0 constructed.
AsumiKana 8-1 copyed.
AsumiKana 8-0 destructed.
AsumiKana 9-0 constructed.
AsumiKana 9-1 copyed.
AsumiKana 1-5 copyed.
AsumiKana 2-4 copyed.
AsumiKana 3-3 copyed.
AsumiKana 4-3 copyed.
AsumiKana 5-2 copyed.
AsumiKana 6-2 copyed.
AsumiKana 7-2 copyed.
AsumiKana 8-2 copyed.
AsumiKana 1-4 destructed.
AsumiKana 2-3 destructed.
AsumiKana 3-2 destructed.
AsumiKana 4-2 destructed.
AsumiKana 5-1 destructed.
AsumiKana 6-1 destructed.
AsumiKana 7-1 destructed.
AsumiKana 8-1 destructed.
AsumiKana 9-0 destructed.
AsumiKana 10-0 constructed.
AsumiKana 10-1 copyed.
AsumiKana 10-0 destructed.
AsumiKana 11-0 constructed.
AsumiKana 11-1 copyed.
AsumiKana 11-0 destructed.
AsumiKana 12-0 constructed.
AsumiKana 12-1 copyed.
AsumiKana 12-0 destructed.
AsumiKana 13-0 constructed.
AsumiKana 13-1 copyed.
AsumiKana 13-0 destructed.
AsumiKana 14-0 constructed.
AsumiKana 14-1 copyed.
AsumiKana 14-0 destructed.
AsumiKana 15-0 constructed.
AsumiKana 15-1 copyed.
AsumiKana 15-0 destructed.
AsumiKana 16-0 constructed.
AsumiKana 16-1 copyed.
AsumiKana 16-0 destructed.
AsumiKana 17-0 constructed.
AsumiKana 17-1 copyed.
AsumiKana 1-6 copyed.
AsumiKana 2-5 copyed.
AsumiKana 3-4 copyed.
AsumiKana 4-4 copyed.
AsumiKana 5-3 copyed.
AsumiKana 6-3 copyed.
AsumiKana 7-3 copyed.
AsumiKana 8-3 copyed.
AsumiKana 9-2 copyed.
AsumiKana 10-2 copyed.
AsumiKana 11-2 copyed.
AsumiKana 12-2 copyed.
AsumiKana 13-2 copyed.
AsumiKana 14-2 copyed.
AsumiKana 15-2 copyed.
AsumiKana 16-2 copyed.
AsumiKana 1-5 destructed.
AsumiKana 2-4 destructed.
AsumiKana 3-3 destructed.
AsumiKana 4-3 destructed.
AsumiKana 5-2 destructed.
AsumiKana 6-2 destructed.
AsumiKana 7-2 destructed.
AsumiKana 8-2 destructed.
AsumiKana 9-1 destructed.
AsumiKana 10-1 destructed.
AsumiKana 11-1 destructed.
AsumiKana 12-1 destructed.
AsumiKana 13-1 destructed.
AsumiKana 14-1 destructed.
AsumiKana 15-1 destructed.
AsumiKana 16-1 destructed.
AsumiKana 17-0 destructed.
I am AsumiKana 1-6.
I am AsumiKana 2-5.
I am AsumiKana 3-4.
I am AsumiKana 4-4.
I am AsumiKana 5-3.
I am AsumiKana 6-3.
I am AsumiKana 7-3.
I am AsumiKana 8-3.
I am AsumiKana 9-2.
I am AsumiKana 10-2.
I am AsumiKana 11-2.
I am AsumiKana 12-2.
I am AsumiKana 13-2.
I am AsumiKana 14-2.
I am AsumiKana 15-2.
I am AsumiKana 16-2.
I am AsumiKana 17-1.
AsumiKana 1-6 destructed.
AsumiKana 2-5 destructed.
AsumiKana 3-4 destructed.
AsumiKana 4-4 destructed.
AsumiKana 5-3 destructed.
AsumiKana 6-3 destructed.
AsumiKana 7-3 destructed.
AsumiKana 8-3 destructed.
AsumiKana 9-2 destructed.
AsumiKana 10-2 destructed.
AsumiKana 11-2 destructed.
AsumiKana 12-2 destructed.
AsumiKana 13-2 destructed.
AsumiKana 14-2 destructed.
AsumiKana 15-2 destructed.
AsumiKana 16-2 destructed.
AsumiKana 17-1 destructed.
各行の最初の数字がオブジェクトのIDを、2番目の数字が何番目のコピーかを表しています。

このデータから、
  • push_backの引数に渡したオブジェクトは1回ずつ生成され、すぐに破棄される。
    (引数のオブジェクトがそのままstd::vectorに入るわけではない)
  • std::vector(のgcc 4.8.1の実装)では、2^n(nは非負整数、^は累乗演算子)個の要素をpush_backするたびに、
    今入っているオブジェクト全てをコピーする。その結果、最初にpush_backされたオブジェクトは何度もコピーされる。
  • コンストラクタおよびデストラクタの計算量がO(1)の場合、この実装でN個の要素を挿入するときの計算量はO(N log N)
ということが考察できます。

ご利用は計画的に！

普段からC言語を使用していれば、計算量的には通るはずなのに、
STLコンテナやstd::cinを利用したためにTime Limit Exceededとなって落ちるという事故を防げます！
ページトップ
コメントはまだありません。