assertion failure with c++11 lambda

general
,
1

i wrote a program for generating suffix array; but unfortunately some how i’m getting assert failure in my code;
i really don’t know why this assertion is failing;

#include <bits/stdc++.h>
#ifdef __mr__
    #include "prettyprint.hpp"
#endif
#define i32inf                      (0x7fffffff)
#define i32_inf                     (-0x7fffffff-1)
#define i64inf                      (0x7fffffffffffffff)
#define i64_inf                     (-0x7fffffffffffffff-1)
#define ui32inf                     (0xffffffffu)
#define ui64inf                     (0xffffffffffffffffu)
#define bitcounti32                 __builtin_popcount
#define bitcounti64                 __builtin_popcountll
using namespace std;
int testcases;

vector<int32_t> getSuffixArray(string& str) {
    vector<int32_t> ranks(str.size());
    vector<int32_t> newranks(str.size());
    for (int x = 0; x < str.size(); ++x)
        newranks[x] = x;
    sort(newranks.begin(), newranks.end(), [&](int32_t i, int32_t j) -> bool {
        assert(i < str.size());
        assert(j < str.size());
        return str[i] <= str[j];
    });
    for (int x = 0; x < str.size(); ++x)
        ranks[newranks[x]] = x;
    for (int x = 1; x <= str.size(); x <<= 1) {
        for (int y = 0; y < str.size(); ++y)
            newranks[y] = y;
        sort(newranks.begin(), newranks.end(), [&](int32_t i, int32_t j) -> bool {
            unsigned long long ki = 1ull*(ranks[i] + 1) << 32, kj = 1ull*(ranks[j] + 1) << 32;
            if (i + x < str.size())
                ki |= ranks[i + x] + 1;
            if (j + x < str.size())
                kj |= ranks[j + x] + 1;
            return ki <= kj;
        });
        // cout << newranks << endl;
        for (int x = 0; x < str.size(); ++x)
            ranks[newranks[x]] = x;
    }
    return move(newranks);
}

int main() {
    string str;
    vector<int32_t> prtemp;
    cin >> str;
    prtemp = getSuffixArray(str);
    cout << prtemp << endl;
    return 0;
}

Input:
sandkjasndkjasndkajnsdkjasndkjasndkjasndkasndkjasnkdjanskdj

please help me!

IDEONE: http://ideone.com/sx2qfq

2

You have one character too much in your lambda comparator :wink: !

    sort(newranks.begin(), newranks.end(), [&](int32_t i, int32_t j) -> bool {
        assert(i < str.size());
        assert(j < str.size());
        return str[i] <= str[j];
    });

std::sort expects a strict weak ordering and has undefined behavior if this condition is not fulfilled.

The solution is to remove the extra “=” in the comparison.

    sort(newranks.begin(), newranks.end(), [&](int32_t i, int32_t j) -> bool {
        assert(i < str.size());
        assert(j < str.size());
        return str[i] < str[j];
    });

See http://ideone.com/UOSyWB

By the way, you should tell explicitly which variables you want to capture in your lambda for performance reasons.

1 Like
3

thank you very much; and i usually avoid too much verbosity in code until it works so, didn’t captured the str