質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
GCC

GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

4回答

3320閲覧

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

ttkkggww

総合スコア5

GCC

GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2019/11/29 07:52

編集2019/11/29 07:56

前提・実現したいこと

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

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

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

該当のソースコード

c++

1#include <iostream> 2using namespace std; 3 4 5 6namespace ttkkggww 7{ 8 template <typename TYPE> 9 class vector 10 { 11 private: 12 //配列の先頭のポインタ 13 TYPE *array; 14 //確保しているメモリサイズ 15 int capacity; 16 //使っている配列の大きさ 17 int use_capacity; 18 //use_capacityがcapacityに到達したら二倍にメモリを拡張 19 //要素数が増える時に使う 20 void mayextend(); 21 22 public: 23 TYPE operator [](int index) const; 24 TYPE& operator [](int index); 25 TYPE front ()const; 26 TYPE& front(); 27 TYPE back()const; 28 TYPE& back(); 29 30 bool is_valid() const; 31 //末尾に値を追加するO(1) 32 void push_back(TYPE val); 33 //末尾の値を削除するO(1) 34 void pop_back(); 35 //指定した場所の値を追加する。O(size()) 36 void insert(TYPE val,int index); 37 //指定した場所の値を削除する。O(size()) 38 void erase(int index); 39 //配列の長さを返すO(1) 40 int size(); 41 //最初のポインタを返す。O(1) 42 TYPE* pbegin(); 43 //最後の値が入っている次のポインタを返す。O(1) 44 TYPE* pend(); 45 //コンストラクタ 46 vector(); 47 //コンストラクタO(logsize) 48 vector(int insize); 49 //デストラクタO(1)? 50 ~vector(); 51 }; 52 53 template <typename TYPE> 54 inline bool vector<TYPE>::is_valid()const 55 { 56 return array != nullptr; 57 } 58 59 template <typename TYPE> 60 void vector<TYPE>::mayextend() 61 { 62 if(capacity==use_capacity) 63 { 64 TYPE *copy = new TYPE[use_capacity-1]; 65 for(int i=0;i<use_capacity-1;i++) 66 { 67 copy[i]=array[i]; 68 } 69 capacity=capacity<<1; 70 delete[] array; 71 array = new TYPE[capacity]; 72 for(int i=0;i<use_capacity-1;++i) 73 { 74 array[i]=copy[i]; 75 } 76 delete[] copy; 77 } 78 } 79 80 template <typename TYPE> 81 TYPE vector<TYPE>::operator [](int index) const 82 { 83 return array[index]; 84 } 85 86 template <typename TYPE> 87 TYPE& vector<TYPE>::operator [](int index) 88 { 89 return array[index]; 90 } 91 92 template <typename TYPE> 93 TYPE vector<TYPE>::front()const 94 { 95 return array[0]; 96 } 97 98 template <typename TYPE> 99 TYPE& vector<TYPE>::front() 100 { 101 return array[0]; 102 } 103 104 template <typename TYPE> 105 TYPE vector<TYPE>::back()const 106 { 107 return array[use_capacity-1]; 108 } 109 110 template <typename TYPE> 111 TYPE& vector<TYPE>::back() 112 { 113 return array[use_capacity-1]; 114 } 115 116 template <typename TYPE> 117 void vector<TYPE>::push_back(TYPE val) 118 { 119 use_capacity++; 120 mayextend(); 121 array[use_capacity-1]=val; 122 } 123 124 template <typename TYPE> 125 void vector<TYPE>::pop_back() 126 { 127 use_capacity--; 128 } 129 130 template <typename TYPE> 131 void vector<TYPE>::insert(TYPE val,int index) 132 { 133 use_capacity++; 134 mayextend(); 135 //一つ後ろにずらす 136 for(int i=use_capacity-1;i>index;--i) 137 { 138 array[i]=array[i-1]; 139 } 140 array[index]=val; 141 } 142 143 template <typename TYPE> 144 void vector<TYPE>::erase(int index) 145 { 146 use_capacity--; 147 for(int i=index;i<use_capacity;++i) 148 { 149 array[i]=array[i+1]; 150 } 151 } 152 153 template <typename TYPE> 154 int vector<TYPE>::size() 155 { 156 return use_capacity; 157 } 158 159 template <typename TYPE> 160 TYPE* vector<TYPE>::pbegin() 161 { 162 return array; 163 } 164 165 template <typename TYPE> 166 TYPE* vector<TYPE>::pend() 167 { 168 return array+use_capacity+1; 169 } 170 171 template <typename TYPE> 172 vector<TYPE>::vector() 173 { 174 capacity=1; 175 use_capacity=0; 176 array = new TYPE[capacity]; 177 178 } 179 180 template <typename TYPE> 181 vector<TYPE>::vector(int insize) 182 { 183 capacity=1; 184 use_capacity=insize; 185 while(capacity<insize) 186 { 187 capacity=capacity<<1; 188 } 189 array = new TYPE[capacity]; 190 for(int i = 0;i < insize;++i) 191 array[i]=0; 192 } 193 194 template <typename TYPE> 195 vector<TYPE>::~vector() 196 { 197 if(is_valid()==true) 198 { 199 delete[] array; 200 array=nullptr; 201 } 202 } 203} 204 205int main() 206{ 207 int n;cin>>n; 208 ttkkggww::vector<ttkkggww::vector<int>> a(n); 209 return 0; 210}

試したこと

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

補足情報

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

maisumakun

2019/11/29 07:57

> 競プロ用のライブラリのvectorを自作しようとしています。 とありますが、標準の<vector>に対して、どのような改良の必要があって自作する感じでしょうか。
ttkkggww

2019/11/29 08:26

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

回答4

0

こんにちは。

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

ttkkggww::vector<ttkkggww::vector<int>>のコンストラクタを想定して下さい。
array[i]=0;のarray[i]はttkkggww::vector<int>型です。
これも整数を1つだけ受け取るコンストラクタがありますので、それが呼ばれます。
つまり、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++プログラマには荷が重すぎると思います。規格書を隅々まで理解している人たちなら書けると思いますが、その難易度の高さといったら...

投稿2019/11/29 09:50

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ttkkggww

2019/11/29 17:20

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

0

ベストアンサー

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

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の処理をやめるのも手~~)。

投稿2019/11/29 08:35

編集2019/12/02 05:05
takabosoft

総合スコア8356

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ttkkggww

2019/11/29 09:37

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

2019/11/29 09:37

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

2019/11/30 03:46

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

2019/12/02 00:36 編集

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

2019/12/02 04:37

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

2019/12/02 05:07

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

0

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

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

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

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

投稿2019/11/29 08:33

maisumakun

総合スコア145121

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ttkkggww

2019/11/29 09:09

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

0

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

cpp

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

を入れて、実装に

cpp

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

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

投稿2019/11/29 09:14

編集2019/11/30 04:02
mattn

総合スコア5030

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ttkkggww

2019/11/29 17:14

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

2019/11/29 23:13

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

2019/11/30 03:41

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

2019/11/30 04:03

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問