c++のvectorの実装でエラーがでます。

Question

前提・実現したいこと

競プロ用のライブラリのvectorを自作しようとしています。
vectorライブラリを実装中に以下のエラーメッセージが発生しました。
二次元以上のvectorを使えるようにしたいです。

発生している問題・エラーメッセージ

*** Error in `./a.out': double free or corruption (fasttop): 0x0000000001384c60 ***

該当のソースコード

#include <iostream>
using namespace std;



namespace ttkkggww
{
	template <typename TYPE>
	class vector
	{
		private:
		//配列の先頭のポインタ
		TYPE *array;
		//確保しているメモリサイズ
		int capacity;
		//使っている配列の大きさ
		int use_capacity;
		//use_capacityがcapacityに到達したら二倍にメモリを拡張
		//要素数が増える時に使う
		void mayextend();

		public:	
		TYPE operator [](int index) const;
		TYPE& operator [](int index);
		TYPE front ()const;
		TYPE& front();
		TYPE back()const;
		TYPE& back();

		bool is_valid() const;
		//末尾に値を追加するO(1)
		void push_back(TYPE val);
		//末尾の値を削除するO(1)
	 	void pop_back();
		//指定した場所の値を追加する。O(size())
		void insert(TYPE val,int index);
		//指定した場所の値を削除する。O(size())
		void erase(int index);
		//配列の長さを返すO(1)
		int size();
		//最初のポインタを返す。O(1)
		TYPE* pbegin();
		//最後の値が入っている次のポインタを返す。O(1)
		TYPE* pend();
		//コンストラクタ
		vector();
		//コンストラクタO(logsize)
		vector(int insize);
		//デストラクタO(1)?
		~vector();
	};

	template <typename TYPE>
	inline bool vector<TYPE>::is_valid()const
	{
		return array != nullptr;
	}

	template <typename TYPE>
	void vector<TYPE>::mayextend()
	{
		if(capacity==use_capacity)
		{
			TYPE *copy = new TYPE[use_capacity-1];
			for(int i=0;i<use_capacity-1;i++)
			{
				copy[i]=array[i];
			}
			capacity=capacity<<1;
			delete[] array;
			array = new TYPE[capacity];
			for(int i=0;i<use_capacity-1;++i)
			{
				array[i]=copy[i];
			}
			delete[] copy;
		}
	}

	template <typename TYPE>
	TYPE vector<TYPE>::operator [](int index) const
	{
		return array[index];
	}

	template <typename TYPE>
	TYPE& vector<TYPE>::operator [](int index)
	{
		return array[index];
	}

	template <typename TYPE>
	TYPE vector<TYPE>::front()const
	{
		return array[0];
	}

	template <typename TYPE>
	TYPE& vector<TYPE>::front()
	{
		return array[0];
	}

	template <typename TYPE>
	TYPE vector<TYPE>::back()const
	{
		return array[use_capacity-1];
	}

	template <typename TYPE>
	TYPE& vector<TYPE>::back()
	{
		return array[use_capacity-1];
	}

	template <typename TYPE>
	void vector<TYPE>::push_back(TYPE val)
	{
		use_capacity++;
		mayextend();
		array[use_capacity-1]=val;
	}

	template <typename TYPE>
	void vector<TYPE>::pop_back()
	{
		use_capacity--;
	}

	template <typename TYPE>
	void vector<TYPE>::insert(TYPE val,int index)
	{
		use_capacity++;
		mayextend();
		//一つ後ろにずらす
		for(int i=use_capacity-1;i>index;--i)
		{
			array[i]=array[i-1];
		}
		array[index]=val;
	}

	template <typename TYPE>
	void vector<TYPE>::erase(int index)
	{
		use_capacity--;
		for(int i=index;i<use_capacity;++i)
		{
			array[i]=array[i+1];
		}
	}

	template <typename TYPE>
	int vector<TYPE>::size()
	{
		return use_capacity;
	}

	template <typename TYPE>
	TYPE* vector<TYPE>::pbegin()
	{
		return array;
	}

	template <typename TYPE>
	TYPE* vector<TYPE>::pend()
	{
		return array+use_capacity+1;
	}

	template <typename TYPE>
	vector<TYPE>::vector()
	{
		capacity=1;
		use_capacity=0;
		array = new TYPE[capacity];

	}

	template <typename TYPE>
	vector<TYPE>::vector(int insize)
	{
		capacity=1;
		use_capacity=insize;
		while(capacity<insize)
		{
			capacity=capacity<<1;
		}
		array = new TYPE[capacity];
		for(int i = 0;i < insize;++i)
		array[i]=0;
	}

	template <typename TYPE>
	vector<TYPE>::~vector()
	{
		if(is_valid()==true)
		{
		delete[] array;
		array=nullptr;
		}
	}	
}

int main()
{
	int n;cin>>n;
	ttkkggww::vector<ttkkggww::vector<int>> a(n);
	return 0;
}

試したこと

deleteを同じアドレス?に対して二回連続で呼び出しているのだとおもいます。
ロベールのC++Arrayクラステンプレート
このページを参考にしました。
delete後にnullを代入したりしてみました。

補足情報

エラーメッセージはAtCoderのコードテストからのエラーです。
コードテスト
GCC5.4.1

Comments

[maisumakun]

> 競プロ用のライブラリのvectorを自作しようとしています。

とありますが、標準の<vector>に対して、どのような改良の必要があって自作する感じでしょうか。

[ttkkggww]

できるだけ自分で実装してみたいと思いました。
実用的ではないかもしれませんが、自分で把握できるものを使いたいからです。

Answer 1

こんにちは。

takabosoftさんの回答でFAなのですが、少し補足してみます。

ttkkggww::vector<ttkkggww::vector<int>>のコンストラクタを想定して下さい。
array[i]=0;のarray[i]はttkkggww::vector<int>型です。
これも整数を１つだけ受け取るコンストラクタがありますので、それが呼ばれます。
つまり、array[i]=0;はarray[i]=ttkkggww::vector<int>::vector(0);へ展開されます。

ttkkggww::vector<int>::vector(0);のarrayは、array = new int[capacity];ですが、capacityは1なので、arrayはnew int[1]で獲得した領域へのポインタになっています。

ttkkggww::vector<int>は、コピー代入演算子を定義していませんので、コンパイラが自動的に生成します。自動生成されたコピー代入演算子は、本当に単純コピーするだけですので、右辺で獲得されたarrayは左辺のarray[i].arrayへ単純コピーされます。また右辺のarrayは一時領域なのですぐに開放されます。
従って、array[i].arrayは開放された領域へのポインタとなってしまいます。

array[i]=0;はやめるべきです。コンストラクタが無駄に2回呼ばれますので。
また、コピー代入演算子をdeleteする、もしくは、真面目に定義するべきです。

---

しかし、STLの実装は超高難易度ですから、自力で書くのは私も含めて「普通」のC++プログラマには荷が重すぎると思います。規格書を隅々まで理解している人たちなら書けると思いますが、その難易度の高さといったら．．．

Comments

[ttkkggww]

回答ありがとうございます。STLの実装をしたかったというよりは、四角い車輪の再発名でもよかったので、自分の理解できているものを使いたいという気持ちです。（そもそも使用できてませんが...）
いろいろ勉強になりました。

Answer 2

デバッグで追ってみた感じ、コンストラクタ内の

for(int i = 0;i < insize;++i)
array[i]=0;

上記のコードで
一時的にttkkggww::vector<int>(0)を生成して代入しているようです。

1. 一時的にttkkggww::vector<int>(0)が生成され内部でarrayをnewする
2. コンテナ側へ↑の内容が丸ごとコピーされる
3. 1が破棄される(arrayもdelete[]される)
4. コンテナ側は複製を持っているので3でdelete済みのarrayを保持し続けている
5. コンテナ側で持っているarrayは存在しないポインタなので、deleteやその他のアクセスはすべて正常に動作しない

という感じです。

解決策はおまかせします（~~ =0の処理をやめるのも手~~）。

Comments

[ttkkggww]

回答ありがとうございます。0の処理をやめたらエラーなくなりました。うーん何となく把握しました。クラスの理解があまりできていないようです。コピーコンストラクタ？=演算子のオーバーロード？勉強しておきます...

[mattn]

= 0 をやめるとメモリにゴミが入ったままになりますので対処方法としては良くありません。

[yumetodo]

というかplacement newしましょうという思い。

[takabosoft]

> = 0 をやめるとメモリにゴミが入ったままになりますので対処方法としては良くありません。
それはttkkggwwさんが判断されることです。
競プロ用と言っているぐらいですから、余計な初期化を勝手にされる方が負荷になって嫌だ、と思うかもしれないと思って入れた一言です（すみません、正直あんまり深く考えていません）。

[yumetodo]

>余計な初期化を勝手にされる方が負荷になって嫌だ
そういうときはreserve()を実装するべきだったのではと。

[takabosoft]

解決案としては駄目だったようなので、該当箇所は取り消し線入れておきます。

Answer 3

実用的ではないかもしれませんが、自分で把握できるものを使いたいからです。

競技ということを前提にするならば、既存の標準ライブラリをしっかり把握することのほうがずっと有意義です。

何を競うのかにもよりますが、競技中には「デジタルでのコード持ち込み不可」というようなものもあって、自分で作ったライブラリを使うには入力時間を消費してしまうということも考えられます。

そうでなくても、うまく動かないときに「今書いたコード」と「自作のライブラリ」の両方を疑わなければいけない、というのも大きなハンデになってしまいます。

Comments

[ttkkggww]

回答ありがとうございます。確かにそうですね。既存のライブラリを把握することは大切だとおもいます。標準ライブラリの中身もしっかり把握できるようにしたいです。ですが今の私のレベルではライブラリの中身を把握することは難しいです。それと、競技外でもし別の言語を触るときにも実装できるようになりたいと思ったからです。（vectorコンテナのようなものは殆どの言語に実装されているとおもいますが...）

Answer 4

コピー演算子が無いからだと思います。クラス宣言に

    vector<TYPE>& operator=(const vector<TYPE>& a);

を入れて、実装に

    template <typename TYPE>
    vector<TYPE>& vector<TYPE>::operator=(const vector<TYPE>& a) {
      return *this;
    }

を足せば動くと思います。コピー演算子が何かについてはご自信で調べて下さい。

Comments

[ttkkggww]

ありがとうございます。調べてみます。

[asm]

参考ページでは
コピーコンストラクタの定義・実装
コピー演算子の定義(後編で実装も添付)があったという衝撃

[yumetodo]

ところでそれコピーコンストラクタではなくてコピー代入演算子では？という思いが・・・

[mattn]

いま間違いに気付いて自分でビックリしたとこですw 直しました。