c++ - vector 如何成为返回类型值以及关于我的代码的另一个问题

Question

下面的代码实现了一个后缀数组算法。

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

/**---  Reference：http://www.geeksforgeeks.org/suffix-array-set-1-introduction/ ---*/

/**
 * @brief store the information of suffix
 */
struct suffix
{
    int index;
    string suff;
};

/**
 * @brief get suffix_array
 * @param text
 * @param n the length of text
 *
 * ps:
 *  b a n a n a
 *  5 3 1 0 4 2
 *
 *  0 banana                          5 a
 *  1 anana     Sort the Suffixes     3 ana
 *  2 nana      ---------------->     1 anana
 *  3 ana        alphabetically       0 banana
 *  4 na                              4 na
 *  5 a                               2 nana
 *
 * suffix array for "banana" is {5, 3, 1, 0, 4, 2}
 *
 * Rank array: the rank array rank[i] represents the rank of the suffix 
 *             beginning at the ith position. That is, if suffix_array[i]=j,
 *             then rank[j] = i
 *
 */
vector<int> buildSuffixArray(string& text, int n)
{
    //store suffixes and their indices
    struct suffix suffixes[n];
    vector<int> suffix_array;
    for (int i = 0; i < n; ++ i)
    {
        suffixes[i].index = i;
        suffixes[i].suff = text.c_str() + i;
    }

    sort(suffixes, suffixes + n, [](struct suffix a, struct suffix b) {
        return strcmp(a.suff.c_str(), b.suff.c_str()) < 0 ? 1 : 0;
    });

    for (int i = 0; i < n; ++ i)
        suffix_array[i] = suffixes[i].index;

    return suffix_array;
}

vector<int> rankArray(vector<int>& suffix_array)
{
    vector<int> rank_array(suffix_array.size());

    for (int i = 0; i < suffix_array.size(); i++)
        rank_array[suffix_array[i]] = i;

    return rank_array;
}

当我将这段代码复制到 Visual Studio 中时，它提醒我表达式必须包含一个常量值，并且 n-->(struct suffix suffixes[n])不能在这个地方使用。以下是我的编译器报告的中文错误信息。

表达式必须含有常量值，参数n不可用作常量值

不明白为什么，用gcc编译也不会出错。

而且我不知道vector如何作为返回类型值，有人能给我一些建议吗？

Answer 1

可变长度数组

I can compile it by gcc with no mistake.

一个数组suffix suffixes[n]被创建在堆栈上，具有自动存储持续时间。那么这个 n 通常必须在 C++ 的编译时确定。但是一些 C++ 编译器支持 VLA(可变长度数组)，它是 C99 的补充，允许在堆栈上声明 C 风格的数组，长度不定。VC++ 不支持 C99 和 VLA，但是 GNU compiler supports VLA as an extension even in C90 and C++ .这就是为什么你可以通过 gcc 编译上面的代码而没有错误的原因。过去有各种相关的帖子。

• Why can i declare an array with a predestined size on gcc but not on visual studio c++?
• Why does a C/C++ compiler need know the size of an array at compile time?
• Why aren't variable-length arrays part of the C++ standard?
• Variable Length Array (VLA) in C++ compilers

如果您在 gcc 编译命令中添加 -pedantic (-pedantic-errors) 选项，我们可以得到大多数 gcc 扩展的警告(错误)。在这种情况下，使用此选项我们应该得到以下警告(错误)消息:

ISO C++ forbids variable length array 'suffixes'

---

buildSuffixArray的实现

And I do not know how vector can be the return type value

即使在 GNU 编译器中，您的 buildSuffixArray 也会出现段错误，因为 suffix_array 未分配。以下最低限度固定的版本可以很好地与 GNU 编译器一起工作:

std::vector<int> buildSuffixArray(const std::string& text, int n)
{
    suffix suffixes[n];
    for (int i = 0; i < n; ++ i)
    {        
        suffixes[i].index = i;
        suffixes[i].suff = text.c_str() + i;
    }

    std::sort(suffixes, suffixes + n, [](struct suffix a, struct suffix b) {
        return std::strcmp(a.suff.c_str(), b.suff.c_str()) < 0 ? 1 : 0;
    });

    std::vector<int> suffix_array(n);
    for (int i = 0; i < n; ++ i){
        suffix_array[i] = suffixes[i].index;
    }

    return suffix_array;
}

但是VC++不支持VLA，上面修复后的版本用VC++还是会出现编译错误。以下代码是避免 VLA(冗余参数 n 和 lambda 表达式)的示例。这将适用于 gcc 和 VC++。 DEMO is here.

std::vector<int> buildSuffixArray(const std::string& text)
{
    std::vector<suffix> suffixes(text.length());
    for (std::size_t i = 0; i < suffixes.size(); ++i)
    {        
        suffixes[i].index = i;
        suffixes[i].suff = text.c_str() + i;
    }

    std::sort(suffixes.begin(), suffixes.end(), [](const suffix& a, const suffix& b) {
        return (std::strcmp(a.suff.c_str(), b.suff.c_str()) < 0);
    });

    std::vector<int> suffix_array(text.length());
    for (std::size_t i = 0; i < suffix_array.size(); ++i){
        suffix_array[i] = suffixes[i].index;
    }

    return suffix_array;
}