0

多くの場合、機能するセグメント ツリーの C++ コードがありますが、入力が大きいと失敗します。とにかく、バグを追跡して、コードの一部を「同等」と思われるものに変更すると、コードが失敗することなく機能することがわかりました。

いくつかのコンテキスト:

struct state {
    int v, pos;
    state (int v, int pos) : v(v), pos(pos)  {}
};
int split(state s);
state go(state, int, int, int);

struct node{
    int link;
...
};
vector<node> t;

このコードは機能しません:

int get_link (int v) {
    if (t[v].link != -1)  return t[v].link;
    if (t[v].par == -1)  return 0;

    int to = get_link (t[v].par);
    state aux = go (state (to,t[to].len()), t[v].l + (t[v].par==0), t[v].r, t[v].i_str);

    return t[v].link = split (aux);
}

これは機能します：

int get_link (int v) {
    if (t[v].link != -1)  return t[v].link;
    if (t[v].par == -1)  return 0;

    int to = get_link (t[v].par);
    state aux = go (state (to,t[to].len()), t[v].l + (t[v].par==0), t[v].r, t[v].i_str);

    int ret = split (aux);
    t[v].link = ret;
    return ret;
}

これは機能します：

int get_link (int v) {
    if (t[v].link != -1)  return t[v].link;
    if (t[v].par == -1)  return 0;

    int to = get_link (t[v].par);
    state aux = go (state (to,t[to].len()), t[v].l + (t[v].par==0), t[v].r, t[v].i_str);

    int ret = split (aux);
    t[v].link = ret;
    return t[v].link;
}

これは機能しません:

int get_link (int v) {

    node &w = t[v];
    if (w.link != -1)  return w.link;
    if (w.par == -1)  return 0;

    int to = get_link (w.par);
    state aux = go (state (to,t[to].len()), w.l + (w.par==0), w.r, w.i_str);

    int ret = split (aux);
    w.link = ret;
//  assert(t[v].link == ret);

    return ret;
}

さらに、この最後のケースでは、アサートは失敗します。すべての失敗のケースで、 get_line 関数は問題なく何度も実行されるため、奇妙です。

何が間違っているのか、何を誤解しているのか。

有用であれば

$ gcc -v 組み込み仕様の使用。COLLECT_GCC=gcc COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-redhat-linux/4.7.2/lto-wrapper ターゲット: x86_64-redhat-linux 構成: ../configure --prefix=/usr --mandir=/ usr/share/man --infodir=/usr/share/info --with-bugurl= http://bugzilla.redhat.com/bugzilla--enable-bootstrap --enable-shared --enable-threads=posix --enable-checking=release --disable-build-with-cxx --disable-build-poststage1-with-cxx --with-system- zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-gnu-unique-object --enable-linker-build-id --with-linker-hash-style=gnu --enable-languages=c, c++,objc,obj-c++,java,fortran,ada,go,lto --enable-plugin --enable-initfini-array --enable-java-awt=gtk --disable-dssi --with-java-home =/usr/lib/jvm/java-1.5.0-gcj-1.5.0.0/jre --enable-libgcj-multifile --enable-java-maintainer-mode --with-ecj-jar=/usr/share/ java/eclipse-ecj.jar --disable-libjava-multilib --with-ppl --with-cloog --with-tune=generic --with-arch_32=i686 --build=x86_64-redhat-linux スレッド モデル: posix gcc バージョン 4.7.2 20120921 (Red Hat 4.7.2-2) (GCC)

4

1 に答える 1

1

分割関数がtベクトルのサイズを変更している可能性が高いようです。したがって、このような式でt[v].link = split (aux)はvector::operator[]、分割呼び出しの前に が評価され (可能です)、分割関数がベクトルを再割り当てしている場合、存在しなくなったオブジェクトへの参照にアクセスしている可能性があります。

vector::operator[]一時変数を使用する代替コードには、split の呼び出しの後に呼び出しが確実に発生するため、この問題はありません。

于 2013-04-04T09:43:38.433 に答える