vi_24E
@vi_24E

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

(C++)ポインタに関するエラー

Q&A

解決したいこと

永続配列の実装をしていたところ、ポインタに関するエラーが出ました。エラーの出所は判明したのですが、原因がわかりません。対処の仕方を教えていただけると幸いです。

発生している問題・エラー

Segmentation fault (core dumped)

該当するソースコード

#include<bits/stdc++.h>
using namespace std;

template <typename T>
struct per_array{
    int depth;
    struct node;
    vector<node*> v;

    struct node{
        bool isleaf;
        node* child[20] = {};
        T val;

        void grow(int depth){
            if (depth == 0){
                isleaf = 1;
                return;
            }

            isleaf = 0;
            for (int i = 0; i < 20; i++){
                node* ptr = (node*)malloc(sizeof(node));
                child[i] = ptr;
            }

            for (int i = 0; i < 20; i++){
                child[i]->grow(depth - 1);
            }
            return;
        }

        node* set(int index, T a){
            if (isleaf) {
                val = a;
                return this;
            }

            return child[index % 20]->set(index / 20, a);
        }

        T get(int index){
            if (index == 0 && isleaf) {
                return val;
            }

            return child[index % 20]->get(index / 20);
        }

        node* copy(node* original, int index, T a){
            if (index == 0 || original->isleaf){
                val = a;
                isleaf = 1;
                return this;
            }

            isleaf = 0;
            for (int i = 0; i < 20; i++){
                if (index % 20 == i) {
                    child[i] = copy(original->child[i], index / 20, a);//おそらくエラー元
                }
                else child[i] = original->child[i];
            }
            return this;
        }
    };

    per_array(vector<T> const a){
        //aで初期化
        depth = 0;
        int t = 1;
        while (t < (int)a.size()){
            t *= 20;
            depth++;
        }

        node n;
        v.emplace_back(&n);
        n.grow(depth);
        for (int i = 0; i < (int)a.size(); i++){
            v[0]->set(i, a[i]);
        }
    }

    void correct(int n, T m){
        //最新verのm番目を破壊的に変更
        (*v.rbegin())->set(n, m);
        return;
    }

    int update(int n, T m){
        //最新verのn番目を保存的に変更(返り値は永続配列中の番号)
        node* ptr;
        ptr = ptr->copy(*v.rbegin(), n, m);
        v.emplace_back(ptr);
        return (int)(v.size() - 1);
    }

    void correct(int index, int n, T m){
        //index番目のverのn番目を破壊的に変更
        v[index]->set(n, m);
        return;
    }

    int back(int index){
        //verをindexに巻き戻す
        v.emplace_back(v[index]);
        return (int)(v.size() - 1);
    }

    T at(int n, int m){
        //n番目のverのm番目を返す
        return v[n]->get(m);
    }
};

int main(){
    vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    per_array<int> pa(a);
    cout << pa.depth << endl << endl;

    cout << pa.at(0, 0) << endl; //3
    cout << pa.at(0, 2) << endl; //4
    cout << pa.at(0, 4) << endl; //5
    cout << pa.at(0, 6) << endl; //2
    cout << pa.at(0, 8) << endl; //3
    cout << endl;

    pa.update(8, 10);//エラー発生
    cout << pa.at(0, 8) << endl; //3
    cout << pa.at(1, 8) << endl; //10
}

自分で試したこと

コメントアウトによるエラー元の探索
vector.push_backをvector.emplace_backに変更(成果なし)
assertマクロでnullptr関連のエラーではないかの調査(おそらくnullptrが原因でない)

C++のポインタ関連の操作に慣れていないので、対処の方法があまり取れませんでした。汚いコードではありますが、見ていただけると幸いです。

0

4Answer

93-94行目で

node* ptr;
ptr = ptr->copy(*v.rbegin(), n, m);

としていて、ptr を初期化しないまま使っているのが原因かと思います。

93行目を

node* ptr = (node*)malloc(sizeof(node));

と変更するとエラーで落ちることがなくなるかと思います。

また、123行目付近で落ちるのは、77行目で定義された node n; がスコープを抜けたときに寿命を迎え、それにしたがって v[0] が無意味な領域を指すことになるためだと思います。

これも同様に77-79行目を

node* n = (node*)malloc(sizeof(node));
v.emplace_back(n);
n -> grow(depth);

のように変更するとうまく動くと思います。

(些細なところですが、a[8]5 なので、126,130行目のコメントで 3 と書かれているところは 5 のミスではないかと思います。)

2Like

Comments

  1. @vi_24E

    Questioner

    ありがとうございます。

    変数は宣言するだけで勝手に領域を確保するのかと勘違いしていますが、初期化が必要なのですね。

    おっしゃっていることは理解できるのですが、77行目のnodeが寿命を迎えるのを止めることができずにいます。構造体にnodeを保管しておくvectorを用意することもしてみましたが、どうもうまくいかないようです。具体的な方法をご教示願えませんでしょうか?
  2. 77行目から79行目を

    ```cpp
    node* n = (node*)malloc(sizeof(node));
    v.emplace_back(n);
    v[0] -> grow(depth);
    ```

    のように、`n` の形を `node*` にしてあげるのが一番かんたんかな?と思います
  3. @vi_24E

    Questioner

    ありがとうございます。

    これもすでに試してはみたのですが、どうやらそうするとコンストラクタが動かなくなり、
    Segmentation fault (core dumped)
    のエラーが出てしまいます。

私の手元の環境 (g++ (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0) ですと、下記で落ちますね..

cout << pa.at(0, 6) << endl; //2
1Like

Comments

  1. @vi_24E

    Questioner

    ありがとうございます。

    このコードが不安定なのか、手元の環境だとコンパイルエラーが、AtCoderのコードテストだとエラーなし(pa.at(0, 8)で出力される値が違うことを除けば)、paizaのコードテストだと上記のエラーが出るようになってしまいました。

    未定義動作がどこかに含まれているのでしょうか?コンパイルエラーのエラーメッセージも見たことがないものだったので、追記いたします。

    /usr/local/bin/g++ -fdiagnostics-color=always -g /このファイルへのパス -o /このファイルへのパス
    /bin/sh: -c: line 0: syntax error near unexpected token `('
    /bin/sh: -c: line 0: `/usr/local/bin/g++ -fdiagnostics-color=always -g /このファイルへのパス -o /このファイルへのパス'
  2. (コードが崩れるので別コメントにします)

コードが難しくて理解できておらず、誤った情報でしたら申し訳ありませんが、
気になった点をご連絡します.

 

下記の child の領域は確保できていますか?

    struct node{
        bool isleaf;
!       node* child[20] = {};

というのも、私の環境ではデバッグログを出力を追加すると、
下記 get(int index) の 2回目の呼び出しのときに、
🛑 の箇所で this->child を見ると、0x8 となっており、
落ちてしまいました.

        T get(int index){
🛑          if (index == 0 && isleaf) {
                return val;
            }

            return child[index % 20]->get(index / 20);
        }

一方、1回目の呼び出しでは、次のように 0x7fffffffd2e8 といったように
メモリ領域が獲得できているようです.

また、値も次のようになっています.

(gdb) p this->child
$8 = {0x1, 0x55555576cf10, 0x7ffff72c8fc1 <_IO_do_write+177>, 0x0, 0x7ffff7628760 <_IO_2_1_stdout_>, 0xa, 0xa,
  0xb, 0x0, 0x0, 0x7ffff72c9473 <_IO_file_overflow+259>, 0x55555575a020 <std::cout@@GLIBCXX_3.4>,
  0x7fffffffd360, 0xa, 0x7ffff795865b <std::ostream::put(char)+91>, 0x1,
  0x55555575a020 <std::cout@@GLIBCXX_3.4>, 0x0, 0x7ffff7628760 <_IO_2_1_stdout_>, 0x0}
0Like

Comments

  1. どうやら、0x7ffff〜 という番地は、スタック領域のようです.
  2. void grow(int depth) での、 malloc() によって獲得しているメモリ領域 0x556a〜 という番地でした.
  3. @vi_24E

    Questioner

    ご丁寧にありがとうございます。

    読みにくいコードで申し訳ございません。コードの中身としては20分木を用いた永続配列を実装している感じです。おそらく再帰的な構造体で作っている木でバグが発生しています。

    お恥ずかしながら、これがポインタを積極的に使った初めてのコードでして、領域確保についてほとんど知識がないのですが、node[20]とするだけでは領域は確保されないのでしょうか?

    配列の領域確保についてイマイチ理解しておらず、以下のようなコードに修正したのですが、それでも同じようになってしまうようです。

    node** child = new node*[20];

    不完全型のポインタについて領域確保する時は何か特別な形式が必要なのでしょうか?
  4. > 読みにくいコードで申し訳ございません。

    競技用プログラミングでしょうか.
    いえ、私がこういう高度なアルゴリズムを知らないので、コードが読めていないだけです.

    > おそらく再帰的な構造体で作っている木でバグが発生しています。

    はい. 私も再帰呼び出しが影響していると推測しています.

    具体的には T get(int index) における下記処理ですね.
    return child[index % 20]->get(index / 20);

    上記、「return child[index % 20]->get(index / 20);」を呼び出した直後に、
    「this」のアドレスを見ると 0x0 となっており、領域が獲得できていなかったです.


  5. すみません. 検討してみたのですが、次の (a) の実装方法が分からないです.


    **(a)** (今回の struct node の中で、さらに struct node 用の領域を獲得するといった) 自分自身のメモリ領域を獲得する実装をしたことがないです


    なお、すでにご覧になられたかも知れませんが、
    下記記事で vi_24E様と似たような実装をされているようでした.

    https://qiita.com/hotman78/items/9c643feae1de087e6fc5


    ただ、上記記事でも、上述の (a) にはなっていないようです.

    お力になれず申し訳ないです.
  6. @vi_24E

    Questioner

    ありがとうございます。

    この記事で知ったデータ構造なのですが、ポインタ実装の練習も兼ねて、車輪の再発明をしている次第です。

    もう少し試行錯誤を繰り返して見ます。
  7. いえ、競技プログラミングの世界の高度さ、難易度の高さに驚かされました。
    レベルが高くてとても足を踏み入れられないですが、同競技を興味を持って見させてもらいます。

教えていただくと確かに ptr は未初期化ですね。
何よりも複雑な構造でヒープ領域を使えることに驚きました。
ーーー
追記

確かに77行目はローカル変数ですが、、解放が理解できないのでデバッガで見てみます!

0Like

Your answer might help someone💌