下面的代码实现了一个后缀数组算法。
#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
如何作为返回类型值,有人能给我一些建议吗?
最佳答案
可变长度数组
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;
}
关于c++ - vector 如何成为返回类型值以及关于我的代码的另一个问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53237129/