strncmp(), Segmentation fault
以下のコードのstrncmp()を呼び出すところでSegmentation faultになります。
なぜでしょうか？
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
bool cmp(const char* a, const char* b) {
return strncmp(a, b, 1) <= 0;
}
int main() {
char* s = "aaaaaaaaaaaaaaaaa";
vector<const char*> v;
for (int i = 0; i < (int)strlen(s); i++)
v.push_back(s + i);
sort(v.begin(), v.end(), cmp);
}
// g++, cygwin
sortの二項述語はless than(<)を要求するけど、strncmp(a, b, 1) <= 0;を返してもいいの？一致するとtrueを返すけど。
VC++のデバッグ版では_Pred(_Left, _Right)と_Pred(_Right, _Left)が共にtrueだと、operator< として不適当だって怒られる。
# これがSegmentation faultの原因かどうかは知らない。
strlen(s) < 17だとSegmentation faultにならないんですが、
strlen(s) >= 17になるとSegmentation faultになるんですよね…。
maruさんありがとうございます。
> sortの二項述語はless than(<)を要求するけど、strncmp(a, b, 1) <= 0;を返してもいいの？一致するとtrueを返すけど。
strncmp(a, b, 1)では、aはbと同じか, aの方が小さければゼロ以下の値を返すので
strncmp(a, b, 1) <= 0; でOKだと思ったのですが、ダメでしたっけ？
> VC++のデバッグ版では_Pred(_Left, _Right)と_Pred(_Right, _Left)が共にtrueだと、operator< として不適当だって怒られる。
VC++をもっていないので分からないのですけど、コンパイルエラーになるのですか？
g++ では -Wall をつけても何も警告もなくコンパイルできています。
> strncmp(a, b, 1)では、aはbと同じか, aの方が小さければゼロ以下の値を返すので
> strncmp(a, b, 1) <= 0; でOKだと思ったのですが、ダメでしたっけ？
strncmp(a, b, 1) は a と b が同じなら0, a の方が小さければ負の値を返します。
なので、 return strncmp(a, b, 1) < 0 じゃないとまともな結果にならないと思います。
Segmentation faultが起きるのは、cmpが"変な"値を返しているせいで挿入位置が決まらなくて、v の範囲外まで見に行っちゃてるせいかもしれません。
> strncmp(a, b, 1)では、aはbと同じか, aの方が小さければゼロ以下の値を返すので
ここまでは正しい（ゼロ以下：ゼロまたは負）が、
> strncmp(a, b, 1) <= 0; でOKだと思ったのですが、ダメでしたっけ？
これは正しくない。
> VC++をもっていないので分からないのですけど、コンパイルエラーになるのですか？
まさか。デバッグ版って言ってるでしょ。ランタイムです。
それより、何故にわざわざstrncmp(a, b, 1)を使うのか不思議。
return *a < *b;
ですむだろうに。
それに、ポインタ集合をソートって何をやりたいんだろう？
> それに、ポインタ集合をソートって何をやりたいんだろう？
こんな例を考えてみた
void test1() {
char text[]="A Quick Brown Fox Jumps Over The Lazy Dog.";
std::sort(text, text+sizeof(text)-1);
std::cout << text << std::endl;
}
bool cmp(const char* l, const char* r) {
return *l<*r;
}
void test2() {
const char text[]="A Quick Brown Fox Jumps Over The Lazy Dog.";
std::vector<const char *> v;
for (size_t n=0; n<sizeof(text)-1; ++n) {
v.push_back(text+n);
}
std::sort(v.begin(), v.end(), cmp);
for (std::vector<const char*>::iterator x=v.begin(); x!=v.end(); ++x) {
std::cout << **x;
}
std::cout << std::endl;
}
test1() は直接ソートできるけど test2() は直接ソートできない
間接的にならばソートすることならできるよね
> test1() は直接ソートできるけど test2() は直接ソートできない
> 間接的にならばソートすることならできるよね
なるほど。char*は、ほんとにcharへのポインタなんですね。
私の場合、char*を見ると、文字列を考えてしまう傾向があるようです。
# でも間接的にソートするためにvector<const char*>を使うのは、
# どうも牛刀割鶏の気がする。
> # どうも牛刀割鶏の気がする。
めっちゃ御意
俺ならごく単純に strcpy してコピーのほうをソートすると思う
まあ提示コードはたいした意味もない考え方のサンプルということで
turuginaさんありがとうございます。
> なので、 return strncmp(a, b, 1) < 0 じゃないとまともな結果にならないと思います。
これが間違っていました。<= ではなくて < でした。
maruさん、turuginaさん、tetrapodさんありがとうございました。
> 俺ならごく単純に strcpy してコピーのほうをソートすると思う
同意。
自分でもそうする（文字列コピーしてからソート）だろうなぁ、って思ったので、
> それに、ポインタ集合をソートって何をやりたいんだろう？
という疑問になったんですけどね。
それに比較にstrncmpを使っているから、なおさら混乱する。
確かに長さ1の文字列は文字だろうけど、strncmpを使っていたら文字を比較し
ようとしているなんて思わない。この辺はプログラムのセンスなんだろうけど、
プログラムを作る人には、「動けばいい」と言う考えは改めて「読んで、何を
やりたいかが分かる」プログラムの書き方を目指して欲しいを思う。
strncmp(a, b, 1) は strcmp(a, b) と書くべきでした。
この点は誤解をまねいてしまったと思います。すみません。
ただ、ポインタ集合をソートしているというのは誤解だと思いますので、
その点は説明させてください。
上のプログラムで行っていたのは、Suffix Array の構築です。
接尾辞配列 - Wikipedia
http://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97
vector<char*> のようにchar*を格納しているのは、Cの文字列が
リスト構造(リンクリスト)と等価だからです。
たとえば、文字列"aabbabbbb"があるとき、この文字列の
（連続する）部分文字列のうち、一番長い重複文字列を求めるとき、
Suffix Arrayとchar*の組み合わせがとても有効です(文字列がとても大きい場合)。
(正確にはchar*ではなくてリンク構造(リンクリスト)であればよい)
bool cmp(const char* a, const char* b) {
return strcmp(a, b) < 0;
}
vector<char*> v;
char* s = "aabbabbbb";
for (int i=0; i < strlen(s); i++) // (**1**)
v.push_back(s + i);
sort(v.begin(), v.end(), cmp);
ソートするとvの中身は次のようになります:
v[0] = aabbabbbb
v[1] = abbabbbb
v[2] = abbbb
v[3] = b
v[4] = babbbb
v[5] = bb
v[6] = bbabbbb
v[7] = bbb
v[8] = bbbb
一番長い重複文字列を調べるには、ソート後にO(strlen(v[i]) + v.size())で分かります。
文字列の先頭部分を比較するだけで良いからです。
この場合abb、またはbbbです。
もし文字列"aabbabbbb"の中で、(連続する)「長さが n である」部分文字列のうち、
もっとも出現頻度が高い文字列を求めたいとき、cmp()のなかでstrcmpを使うのは
効率が悪いのでstrncmpを使うべきです。なぜなら、「長さが n」であるので、
文字列末尾まで調べる必要はなく、
先頭から n 文字まで比較するだけでソートを行えるからです。(補足*1)
(これがぼくが最初の質問でstrcmpではなく、strncmpを使った理由です。
ただ、strncmpの引数に 1 を指定してしまって、
文字の比較と誤解させるようなコードを書いてしまったことは申し訳なかったです。
すみません)
補足*1 たとえば、「長さが 3」の場合、先頭から3文字調べるだけで十分です。
このとき strlen(v[i]) が 3 以上になるように (**1**)のforループを
調節します。
| ツイート |  |