时间戳

首页 > 解决方案 > 矢量如何成为返回类型值以及关于我的代码的另一个问题

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

问题描述

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

#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返回类型值如何，有人可以给我一些建议吗？

标签： c++algorithm

解决方案

可变长度数组

我可以通过 gcc 毫无错误地编译它。

数组suffix suffixes[n]在堆栈上创建，具有自动存储持续时间。然后这n通常必须在 C++ 的编译时确定。但是一些 C++ 编译器支持 VLA（可变长度数组），它是 C99 的补充，并允许在堆栈上声明具有非恒定长度的 C 样式数组。VC++ 不支持 C99 和 VLA，但GNU 编译器即使在 C90 和 C++ 中也支持 VLA 作为扩展。这就是为什么您可以通过 gcc 编译上述代码而不会出错的原因。过去有各种相关的帖子。

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

ISO C++ 禁止变长数组“后缀”

实施buildSuffixArray

而且我不知道vector如何成为返回类型值

buildSuffixArray即使在 GNU 编译器中，您也会出现分段错误，因为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++。 演示在这里。

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;
}

推荐阅读