c++ - 为什么我从 GNU g++ 和 VC++ 得到不同的结果

Question

我正在尝试用 C++ 解决这个问题:

“给定一个整数序列 S，找到多个递增序列 I，使得 I 中的每两个连续元素出现在 S 中，但出现在 I 的第一个元素的相对两侧。”

这是我开发的代码:

#include<iostream>
#include<set>
#include<vector>

using namespace std;

struct Element {
long long height;
long long acc;
long long con;
};

bool fncomp(Element* lhs, Element* rhs) {
    return lhs->height < rhs->height;
}

int solution(vector<int> &H) {
    // set up
    int N = (int)H.size();
    if (N == 0 || N == 1) return N;
    long long sol = 0;
    // build trees
    bool(*fn_pt)(Element*, Element*) = fncomp;
    set<Element*, bool(*)(Element*, Element*)> rightTree(fn_pt),   leftTree(fn_pt);
    set<Element*, bool(*)(Element*, Element*)>::iterator ri, li;
    for (int i = 0; i < N; i++) {
        Element* e = new Element;
        e->acc = 0;
        e->con = 0;
        e->height = H[i];
        rightTree.insert(e);
    }
    //tree elements set up
    ri = --rightTree.end();
    Element* elem = *ri;
    elem->con = 1;
    elem->acc = 1;
    while (elem->height > H[0]) {
        Element* succ = elem;
        ri--;
        elem = *ri;
        elem->con = 1;
        elem->acc = succ->acc + 1;
    }
    rightTree.erase(ri);
    elem->con = elem->acc;
    leftTree.insert(elem);
    sol += elem->acc;
    // main loop
    Element* pE = new Element;
    for (int j = 1; j < (N - 1); j++) {
        // bad case
        if (H[j] < H[j - 1]) {
            ///////
            Element* nE = new Element;
            nE->height = H[j];
            pE->height = H[j - 1];
            rightTree.erase(nE);
            leftTree.insert(nE);
            ///////
            li = leftTree.lower_bound(pE);
            long ltAcc = (*li)->acc;
            li--;
            ///////
            ri = rightTree.lower_bound(pE);
            long rtAcc = 0;
            if (ri != rightTree.end()) rtAcc = (*ri)->acc;
            ri--;
            ///////
            while (ri != (--rightTree.begin()) && (*ri)->height > H[j]) {
                if (fncomp(*ri, *li)) {
                    (*li)->con = rtAcc + 1;
                    (*li)->acc = rtAcc + 1 + ltAcc;
                    ltAcc = (*li)->acc;
                    --li;
                }
                else {
                    (*ri)->con = ltAcc + 1;
                    (*ri)->acc = ltAcc + 1 + rtAcc;
                    rtAcc = (*ri)->acc;
                    --ri;
                }
            }
            while ((*li)->height > H[j]) {
                (*li)->con = rtAcc + 1;
                (*li)->acc = rtAcc + 1 + ltAcc;
                ltAcc = (*li)->acc;
                --li;
            }
            (*li)->con = rtAcc + 1;
            (*li)->acc = rtAcc + 1 + ltAcc;
            sol += (*li)->acc;
        }
        // good case
        else {
            Element* nE = new Element;
            nE->height = H[j];
            ri = rightTree.upper_bound(nE);
            li = leftTree.upper_bound(nE);
            rightTree.erase(nE);
            if (li == leftTree.end() && ri == rightTree.end()) {
                nE->con = 1;
                nE->acc = 1;
            }
            else if (li != leftTree.end() && ri == rightTree.end()) {
                nE->con = 1;
                nE->acc = 1 + (*li)->acc;
            }
            else if (li == leftTree.end() && ri != rightTree.end()) {
                nE->con = (*ri)->acc + 1;
                nE->acc = nE->con;
            }
            else {
                nE->con = (*ri)->acc + 1;
                nE->acc = nE->con + (*li)->acc;
            }
            leftTree.insert(nE);
            sol += nE->acc;
        }
    }
    // final step
    li = leftTree.upper_bound(*rightTree.begin());
    while (li != leftTree.end()) {
        sol++;
        li++;
    }
    sol++;
    return (int)(sol % 1000000007);
}

int main(int argc, char* argv[]) {
    vector<int> H = { 13, 2, 5 };
    cout << "sol: " << solution(H) << endl;
    system("pause");
}

main函数调用 solution(vector<int> H) .重点是，当参数具有特定值 H = {13, 2, 5} 时VC++编译程序给出的输出值为7 (这是正确的)，但是 GNU g++ 编译程序给出的输出值为 5 (clang 编译的程序也是这样)。

我正在使用这个网站以及其他网站来测试不同的编译器 http://rextester.com/l/cpp_online_compiler_gcc

我试图找出这种奇怪行为的原因，但没有找到任何相关信息。只有一个帖子处理类似的问题: Different results VS C++ and GNU g++这就是我使用 long long 的原因输入代码，问题依旧。

Answer 1

问题是递减序列开始 --rightTree.begin()

我发现 VC++ 和 GNU g++ 在上述操作中的行为方式不同。这是显示差异的代码，改编自 http://www.cplusplus.com/forum/general/84609/ :

#include<iostream>
#include<set>

using namespace std;

struct Element {
long long height;
long long acc;
long long con;
};

bool fncomp(Element* lhs, Element* rhs) {
    return lhs->height < rhs->height;
}

int main(){

    bool(*fn_pt)(Element*, Element*) = fncomp;
    set<Element*, bool(*)(Element*, Element*)> rightTree(fn_pt);
    set<Element*, bool(*)(Element*, Element*)>::iterator ri;

    ri = rightTree.begin();
    --ri;
    ++ri;
    if(ri == rightTree.begin()) cout << "it works!" << endl;
}