辞書式順序

質問

C++で、2次元（以上の）配列に対して、
辞書式順序でsortできるようにするためには、
bool operatorとsortを使えばよいらしいというのは、
分かったのですが、具体的なコーディングが分かりません。
教えてください。

回答No.2

bilbo

>まず、bilboさんのプログラムは動きませんでした。
>いろいろこちらで手直ししてみましたがやっぱりだめです
依然載せたプログラムは一応テストしたのですが...
int版で作ってみました.
今度はちゃんと通った事を確認しています.

>よく考えたら、こちらの開発環境を伝えてませんでした
僕の開発環境はUNIXのg++ですので,少し違うかも知れませんね.

このプログラムが動かなかった場合は,配列のi行目の最後の列のデータ
とi+1行目の最後の列のデータが,隣同士にあるかどうか確かめてください.
これはm行n列の配列Aに対して,A[i][n+5]という様なアクセスで,
A[i+1][5]をアクセスできるかどうかで確かめられると思います.

もしA[i][n-1]とA[i+1][0]が隣同士に無い様な開発環境ですと,
A[i]がA[i][0]～A[i][n-1]までの配列へのポインタになってること
が考えられます(配列でそんな環境があるかは疑問ですが).
そのような場合,この方法でソートするのはイタレータを
定義しなければならないのでややこしい事になります.

それから,これは分かっておられるかと思いますが,
ソートするデータを静的配列に入れないと,A[i][n-1]と
A[i+1][0]が隣り合わないので駄目です.
動的配列に入れるとコンパイルの時点ではねられると思います.

#include<algorithm>
#include<iostream>
#include<functional>

int main() {
int m[4][6];

for(int i = 0; i < 4; ++i)
for(int j = 0; j < 6; ++j)
m[i][j] = i+ j;

for(int i = 0; i < 4; ++i) {
copy(m[i], m[i]+6, ostream_iterator<int>(cout, " "));
cout << endl;
}
cout << endl;

sort(m[0], m[0]+24, less<int>());

for(int i = 0; i < 4; ++i) {
copy(m[i], m[i]+6, ostream_iterator<int>(cout, " "));
cout << endl;
}

return 0;
}

出力結果
0 1 2 3 4 5
1 2 3 4 5 6
2 3 4 5 6 7
3 4 5 6 7 8

0 1 1 2 2 2
3 3 3 3 4 4
4 4 5 5 5 5
6 6 6 7 7 8

補足

たびたび申し訳ないです。
コンパイラのエラー情報によると、
copyやostream_iteratorは「定義されていない識別子」だそうです。
UNIX CとWindowsではまったく違うものなのでしょうか？

回答No.1

bilbo

2次元配列上のデータをソートするというのは、
どのような基準で並べ替えるということなのでしょうか?
(列数)*(行インデックス)+(列インデックス)
が大きくなる程、値が大きくなるようにソートしたいということでしょうか?
そうであると仮定して話を進めさせてもらいます。

又、bool operator>とsortを使えばいいというのは、
C++の標準テンプレートライブラリの、<algorithm>のsortを使って、
2次元配列をソートしたいということなのでしょうか?
そうであると仮定して話を進めさせてもらいます。

まず、operator>についてですが、配列に格納するデータに対して
このメンバ関数を定義する必要があります。ソートの基準のためです。
また、必ずしもoperator>を使わなくても、ソートの基準を決めてくれる
関数をsortに渡してやってもいいです。

辞書式順序といっておられるので、格納するデータは文字列でしょうか?
stringクラスにはoperator>が定義してあるので、stringクラスを
利用する場合でしたら必要ありません。
ここでは文字型の配列に文字列を入れている事にしましょう。
この場合、strcmpで比較する事になりますね。
例えば、次のようなコードになります。

#include<algorithm>
#include<iostream>
#include<cstring>

bool my_less(const char *str1, const char *str2) {
return (strcmp(str1, str2) < 0);
}

int main() {
char *a[4][6];

for(int i = 0; i < 4; ++i)
for(int j = 0; j < 6; ++j) {
a[i][j] = new char[4];
a[i][j][0] = 'a'+i*j;
a[i][j][1] = 'a'+j/(i+1);
a[i][j][2] = 'a'+j+i;
a[i][j][3] = '\0';
}

for(int i = 0; i < 4; ++i) {
for(int j = 0; j < 6; ++j)
cout << " " << a[i][j];
cout << endl;
}
cout << endl;

sort(a[0], a[0]+24, my_less);

for(int i = 0; i < 4; ++i) {
for(int j = 0; j < 6; ++j)
cout << " " << a[i][j];
cout << endl;
}

return 0;
}

補足

ご解答ありがとうございます。

まず、bilboさんのプログラムは動きませんでした。
いろいろこちらで手直ししてみましたがやっぱりだめです。
よく考えたら、こちらの開発環境を伝えてませんでした。
申し訳ないです。
MicrosoftVisualC++6.0になります。
あと何か必要なデータはありますか？

> (列数)*(行インデックス)+(列インデックス)が大きくなる程、
>値が大きくなるようにソートしたいということでしょうか?

そうです。

>C++の標準テンプレートライブラリの、<algorithm>のsortを使って、
>2次元配列をソートしたいということなのでしょうか?

これもそうです。

>格納するデータは文字列でしょうか?

数字です。すみません、忘れてました・・・

で、こちらでも調べて
lexicographical_compareとかいうのがあるらしいというので、
こんなプログラムを作ったのですが、やっぱり動きません。
八方ふさがりになってきました・・・
#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;

class data
{
int num1,num2;
public:
void setnum1(int i){num1=i;}
int getnum1() const {return num1;}
void setnum2(int j){num2=j;}
int getnum2() const {return num2;}
};
bool operator < (const data& a,const data& b){
return lexicographical_compare(a.begin(),a.end(), b.begin(), b.end());
}
int main()
{
int i,k,l;
data dat;
vector<data> d;

cout << "数字を入力" << endl;

for(i=0;i<5;i++){
cin >> k;
cin >>l;
dat.setnum1(k);
dat.setnum2(l);
d.push_back(dat);
}
cout << "出力" << endl;
sort(d.begin(),d.end());
for(i=0;i<5;i++){
cout << d[i].getnum1() << " " << d[i].getnum2() << endl;
}
}