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

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

ただいまの
回答率

89.13%

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

解決済

回答 4

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 986

ttkkggww

score 5

前提・実現したいこと

競プロ用のライブラリの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

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • maisumakun

    2019/11/29 16:57

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

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

    キャンセル

  • ttkkggww

    2019/11/29 17:26

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

    キャンセル

回答 4

checkベストアンサー

+3

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

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/12/02 09:27 編集

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

    キャンセル

  • 2019/12/02 13:37

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

    キャンセル

  • 2019/12/02 14:07

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

    キャンセル

+3

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

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

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/29 18:09

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

    キャンセル

+3

こんにちは。

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/30 02:20

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

    キャンセル

+1

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

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

を入れて、実装に

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


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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/11/30 02:14

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

    キャンセル

  • 2019/11/30 08:13

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

    キャンセル

  • 2019/11/30 12:41

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

    キャンセル

  • 2019/11/30 13:03

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

    キャンセル

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

  • ただいまの回答率 89.13%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる