新規記事の投稿を行うことで、非表示にすることが可能です。
2017年12月06日
《その164》 メンバ関数へのポインタ
クラスのメンバ関数へのポインタ
クラスのメンバ関数を、直接呼び出すのではなく、目的の関数へのポインタを通じて動的に呼び出すことを考えます。
次のプログラムは、記念日が何年年月何日であるかを当てさせる単純なものですが、コード中にコメントとして、メンバ関数へのポインタの記述方法やそれに関連したことを書き込みました。
// ------------------------------------
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
class Anniversary {
// 記念日クラス Anniversary は
// 日付( 1980/01/01 〜 2017/12/31 )を１つだけ保持します。
int y, m, d;
public:
Anniversary() {
srand((unsigned)time(NULL));
y = rand() % 38 + 1980; // 1980 〜 2017
m = rand() % 12 + 1; // 1 〜 12
switch (m) {
case 2: d = rand() % 28 + 1 + (
y % 4 == 0 && y % 100 != 0 ||
y % 400 == 0); // うるう年を考慮
break;
case 4:
case 6:
case 9:
case 11: d = rand() % 30 + 1; break;
default: d = rand() % 31 + 1; break;
}
}
int yy() const { return y; }
int mm() const { return m; }
int dd() const { return d; }
};
int main() {
Anniversary date;
// Anniversaryクラスの dateオブジェクトを作成。
// 日付を１つ保持しています。
cout << "記念日( 1980/01/01 〜 2017/12/31 )を当ててください。\n";
typedef int (Anniversary::*Anniv)() const;
// Anniversaryクラスのメンバ関数 yy, mm, dd は、仮引数無し、
// 返却値 int ですから、これらのメンバ関数
// へのポインタ型は、次のようになります。
// int (Anniversary::*pointer)()
// このメンバ関数へのポインタ型に typedef名 Anniv を与える
// には、const関数でもあることを考慮して、
// typedef int (Anniversary::*Anniv)() const; と記述します。
Anniv ymd[] = {
&Anniversary::yy,
&Anniversary::mm,
&Anniversary::dd
};
// 配列 ymd は、Anniv型を要素型とする配列で、その要素数は
// 3 です。
// ymd[0] は Anniversary::yy を指し、
// ymd[1] は Anniversary::mm を指し、
// ymd[2] は Anniversary::dd を指すことになります。
int menu; // 配列 ymd の添字(要素番号 0 〜 2)です。
// 配列 answer の添字でもあります。
int val; // 入力された値を受け取るための変数です。
int answer[3] = { 0 }; // 年が正解したら answer[0] = 1
// 月が正解したら answer[1] = 1
// 日が正解したら answer[2] = 1
do {
do {
cout << "年(0) 月(1) 日(2) のどれを入力しますか : "; cin >> menu;
} while (menu < 0 || menu > 2);
cout << "値を入力 : "; cin >> val;
if (val == (date.*ymd[menu])()) {
// date.*ymd[menu] は、
// (date.*ymd[0])() のときは、date.yy() のこと、
// (date.*ymd[1])() のときは、date.mm() のこと、
// (date.*ymd[2])() のときは、date.dd() のことになります。
cout << "正解です。\n";
answer[menu] = 1;
}
else {
cout << (date.*ymd[menu])() - val << " を加えてください。\n";
answer[menu] = 0;
}
} while (answer[0] == 0 || answer[1] == 0 || answer[2] == 0);
cout << date.yy() << "年" << date.mm() << "月" << date.dd() << "日\n";
}
// ------------------------------------
 | 新品価格 |  | 新品価格 |
2017年12月05日
《その163》 名前空間 & p.129演習3-12
名前空間
次のプログラムの、Ns_a，Ns_b はそれぞれ名前空間です。
// ------------------------------------
#include <iostream>
using namespace std;
namespace Ns_a {
void comment() {
cout << "優勝できてよかったです！\n";
}
int acc(int n) { return n * 1.08; }
}
namespace Ns_b {
void comment() {
cout << "そろそろ引退しようかな…\n";
}
int acc(int n) { return n * 1.2; }
}
int main()
{
Ns_a::comment(); // ｢優勝できてよかったです！｣
Ns_b::comment(); // ｢そろそろ引退しようかな…｣
cout << "500円預けると１年後には" << Ns_a::acc(500)
<< "円になります。\n"; // 540円
cout << "500円預けると１年後には" << Ns_b::acc(500)
<< "円になります。\n"; // 600円
}
// ------------------------------------
namespace NamaeKuukann {
ここは、名前空間 NamaeKuukann の中です。
}
namespace Harumafuji {
ここは、名前空間 Harumafuji の中です。
}
namespace {
ここは、名前無し名前区間の中です。
この中で定義された識別子などは、この名前空間が
存在するソースファイルの中でしか通用しません。
}
新版明解C++中級編 p.129 演習3-12
次の関数を作成せよ。
void mergesort(void* base, size_t nmemb, size_t size,
int(*compar)(const void*, const void*));
マージソートのアルゴリズムを用いて安定なソートを行うものとする。
// p129_演習3-12
#include <random>
#include <string>
#include <iostream>
void mergesort(
void* base,
size_t nmemb,
size_t size,
int(*compar)(const void*, const void*)
) {
// 要素数 1以下なら何もしない。
if (nmemb <= 1) return;
// 配列 base の先頭要素へのポインタを
// キャストして、char* v に代入
char* v = reinterpret_cast<char*>(base);
// 配列用の領域を確保
char* temp = new char[nmemb * size];
// 分割位置の添字 m を決定
unsigned m = nmemb / 2;
// 分割左側から mergesort を再帰呼出し
mergesort(&v[0], m, size, compar);
// 分割右側から mergesort を再帰呼出し
mergesort(&v[m * size], nmemb - m, size, compar);
for (unsigned i = 0; i < nmemb * size; i++) {
// ソート済の左側と、
// 同じくソート済の右側を、
// 配列 temp にコピー
temp[i] = v[i];
}
unsigned p = 0; // 分割左側の最初の添字
unsigned q = m; // 分割右側の最初の添字
unsigned i = 0;
do {
if (compar(
&temp[p * size],
&temp[q * size]
) <= 0) {
for (unsigned j = 0; j < size; j++)
v[i * size + j] = temp[p * size + j];
p++;
}
else {
for (unsigned j = 0; j < size; j++)
v[i * size + j] = temp[q * size + j];
q++;
}
i++;
} while (p < m && q < nmemb);
if (p == m) {
for (; i < nmemb; i++) {
for (unsigned j = 0; j < size; j++)
v[i * size + j] = temp[q * size + j];
q++;
}
}
else if (q == nmemb) {
for (; i < nmemb; i++) {
for (unsigned j = 0; j < size; j++)
v[i * size + j] = temp[p * size + j];
p++;
}
}
delete[] temp;
}
int acmp(char* x, char* y) { // 比較関数
return strcmp(x, y);
}
int pcmp(char** x, char** y) { // 比較関数
return strcmp(*x, *y);
}
int ncmp(int* x, int* y) { // 比較関数
return *x < *y ? -1 : *x > *y ? 1 : 0;
}
int main() {
std::random_device rd;
int a[20];
int nmemb = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < nmemb; i++) {
a[i] = rd() % 90 + 10;
}
std::cout << "ソート前\n";
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
mergesort(
a,
nmemb,
sizeof(a[0]),
reinterpret_cast<int(*)(const void*, const void*)>(ncmp)
);
std::cout << "ソート後\n";
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
std::cout << "------------------------------------\n";
char b[][5]
= { "cba", "cabd", "abc", "bcd",
"cab", "b", "a", "cba", "aa" };
nmemb = sizeof(b) / sizeof(b[0]);
std::cout << "ソート前\n";
for (int i = 0; i < nmemb; i++)
std::cout << b[i] << " ";
std::cout << '\n';
mergesort(
b,
nmemb,
sizeof(b[0]),
reinterpret_cast<int(*)(const void*, const void*)>(acmp)
);
std::cout << "ソート後\n";
for (int i = 0; i < nmemb; i++)
std::cout << b[i] << " ";
std::cout << '\n';
std::cout << "------------------------------------\n";
const char* p[]
= { "yx", "xxz", "zxy", "xwy", "xxy",
"y", "xy", "yx", "xww", "y", "zy" };
nmemb = sizeof(p) / sizeof(p[0]);
std::cout << "ソート前\n";
for (int i = 0; i < nmemb; i++)
std::cout << p[i] << " ";
std::cout << '\n';
mergesort(
p,
nmemb,
sizeof(p[0]),
reinterpret_cast<int(*)(const void*, const void*)>(pcmp)
);
std::cout << "ソート後\n";
for (int i = 0; i < nmemb; i++)
std::cout << p[i] << " ";
std::cout << '\n';
}
| 新品価格 | | 新品価格 |
2017年12月04日
《その162》 マージソート（２）
マージソート（２）
前回《161》のときに書いた、「先ず配列を分割する」の意味と、「再帰的な処理」の扱い方を、きちんとした形にまとめてみました。
// ------------------------------------
#include <random>
#include <iostream>
void mergesort(int* base, int nmemb)
{
// 要素数 1以下なら何もしない。
if (nmemb <= 1) return;
// 配列用の領域を確保
int* temp = new int[nmemb];
// 分割位置の添字 m を決定
int m = nmemb / 2;
// 分割左側から mergesort を再帰呼出し
mergesort(base, m);
// 分割右側から mergesort を再帰呼出し
mergesort(&base[m], nmemb - m);
for (int i = 0; i < nmemb; i++) {
// ソート済の左側と、
// 同じくソート済の右側を、
// 配列 temp にコピー
temp[i] = base[i];
}
int p = 0; // 分割左側の最初の添字
int q = m; // 分割右側の最初の添字
// 配列 temp の左側と右側は、それぞれソー
// ト済みなので、左右の要素を比較
// しながら、
// 昇順になるように配列 base にコ
// ピーしていきます。
// 以下は、その作業です。
int i = 0;
do {
if (temp[p] < temp[q]) {
base[i] = temp[p];
p++;
}
else {
base[i] = temp[q];
q++;
}
i++;
} while (p < m && q < nmemb);
if (p == m) {
for (; i < nmemb; i++) {
base[i] = temp[q];
q++;
}
}
else if (q == nmemb) {
for (; i < nmemb; i++) {
base[i] = temp[p];
p++;
}
}
// この for文はソートの途中経過を出力
// するためのものなので、削除
// しても問題ありません。
for (int i = 0; i < nmemb; i++)
std::cout << temp[i] << " ";
std::cout << '\n';
// 領域を解放します。
delete[] temp;
}
int main() {
std::random_device rd;
int a[20];
int nmemb = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < nmemb; i++) {
a[i] = rd() % 90 + 10;
}
std::cout << "ソート前\n";
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << "\n\n";
mergesort(a, nmemb);
std::cout << '\n';
std::cout << "ソート後\n";
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
}
// ------------------------------------
| 新品価格 | | 新品価格 |
2017年12月03日
《その161》 マージソート（１）
マージソート（１）
下のマージソートのプログラムは、はっきり言って良くないです (//△//)。
「先ず配列を分割する」の意味と、「再帰的な処理」の扱い方があいまいなまま作業に入ったのが良くなかったです。
無駄の多いプログラムを書いているうちに、それらのことが少し理解できたので、次回にもう少しマシなプログラムを作りたいと思っています。
だだ、無駄は多いのですが、ソートしていく手順としてはマージソートになっているので、一応下記しておきます。
最後に掲載してある実行結果の画面コピーで、数字の並びがマージソートされる過程を確認できるのではないかと思います。
// ------------------------------------
#include <iostream>
int main() {
int a[]
= { 25, 21, 16, 12, 17, 11, 23, 19, 28, 17, 13,
22, 24, 11, 18, 26, 19, 10, 21, 17, 19, 16, 14};
int nmemb = sizeof(a) / sizeof(a[0]);
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
int nmem = nmemb;
int p = 0;
while (nmem /= 2) p++;
if (nmemb > (int)pow(2, p))
nmem = (int)pow(2, p + 1);
int* f = new int[nmem];
int* g = new int[nmem];
for (int i = nmemb; i < nmem; i++)
f[i] = INT_MAX;
for (int i = 0; i < nmemb; i++)
f[i] = a[i];
for (int i = 0; ; i++) {
for (int j = 0; j < nmem / pow(2, i + 1); j++) {
// pow(2, i + 1) … 2 の i + 1 乗
// 操作対象範囲の要素数
// pow(2, i + 1) = 2, 4, 8, ･･･
int nl = (int)pow(2, i);
// pow(2, i) は操作対象範囲の左側要素数
// pow(2, i) = 1, 2, 4 ･･･
if (nl >= nmem) goto END;
// 操作対象範囲の左側要素数が、配列 f の要素数以上に
// なったら作業終了。
int nr = nl;
// 操作対象範囲の右側要素数
int xleft = (int)pow(2, i + 1) * j;
// 操作対象範囲左側の左端要素の添字
int xrght = xleft + nl;
// 操作対象範囲右側の左端要素の添字
int xl = xleft;
int xr = xrght;
for (int k = 0; k < nl + nr; k++) {
// 操作対象範囲内の要素の個数と同じ回数だけの繰返し
if (
f[xl] <= f[xr] && xl < xleft + nl
|| xr >= xrght + nr
)
// ｢ f[xl] <= f[xr]
// かつ xl が操作対象範囲左側に収まっている ｣
// または ｢ xr が操作対象範囲右側を超えている ｣
g[xleft + k] = f[xl++];
// f[xl] の値を臨時の配列 g に収容し、xl++ する。
else if (xr < xrght + nr) {
// そうではない場合
g[xleft + k] = f[xr++];
// a[xr] の値を臨時の配列 g に収容し、xr++ する。
}
}
} // j{ }
for (int i = 0; i < nmemb; i++) {
a[i] = f[i] = g[i];
}
for (int i = 0; i < nmemb; i++)
std::cout << a[i] << " ";
std::cout << '\n';
} // i{ }
delete[] f;
delete[] g;
END:
;
}
// ------------------------------------
| 新品価格 | | 新品価格 |
2017年12月02日
《その160》 マージソート & p.129演習3-9，演習3-10，演習3-11
マージソートの概略
・ 配列を、先ず、バラバラに分解します。
・ 次に２個の要素を、各値が昇順になるようにして統合します。
・ 統合してできた部品どうしをさらに統合していきますが、統合の際は、必ず値が昇順になるようにします。
・ 最終的に、全てを統合したらソート終了です。
マージソートの詳細は、次回《161》にチェックしたいと思います。
下図は、マージソートのイメージ図です。
新版明解C++中級編 p.129 演習3-9
※本ブログの《その153》のプログラムが、解答です。
新版明解C++中級編 p.129 演習3-10
※本ブログの《その155》のプログラムが、解答です。
新版明解C++中級編 p.129 演習3-11
※本ブログの《その156》のプログラムが、解答です。
| 新品価格 | | 新品価格 |
《その159》 配列の型について & p.129演習3-8
配列の型について
次のプログラムで、配列の型について、いくつか確認してみます。
// ------------------------------------
#include <iostream>
int main() {
char a[][3][4]
= {
{ "aaa", "bbb", "ccc" },
{ "abc", "bca", "cba" },
{ "aab", "bbc", "cca" },
{ "abb", "bcc", "caa" },
};
// typeid演算子を用いて型名を調べてみます。
std::cout << typeid(&a[0][0][0]).name() << '\n';
// 結果は「 char * 」
std::cout << typeid(&a[0][0]).name() << '\n';
// 結果は「 char (*)[4] 」
std::cout << typeid(&a[0]).name() << '\n';
// 結果は「 char (*)[3][4] 」
void* v1 = (void*)&a[0][0][0];
// &a[0][0][0]へのポインタを void* 型にキャストして void* v1 に代入。
// ポインタ v1 は配列の型としての情報を失います。
void* v2 = (void*)&a[3][0][0];
// &a[3][0][0]へのポインタを void* 型にキャストして void* v2 に代入。
// ポインタ v2 は配列の型としての情報を失います。
std::cout << (char*)v2 - (char*)v1 << '\n';
// v1, v2 を char*型にキャストして減算
// 結果は「 36 」
// この型の配列要素の序数差に一致します。
std::cout << (char(*)[4])v2 - (char(*)[4])v1 << '\n';
// v1, v2 を char(*)[4]型にキャストして減算
// 結果は「 9 」
// この型の配列要素の序数差に一致します。
std::cout << (char(*)[3][4])v2 - (char(*)[3][4])v1 << '\n';
// v1, v2 を char(*)[3][4]型にキャストして減算
// 結果は「 3 」
// この型の配列要素の序数差に一致します。
}
// ------------------------------------
新版明解C++中級編 p.129 演習3-8
次の関数 seqsearch を利用するプログラムを作成せよ。
// -- seqsearch -----------------------
// 汎用線形探索関数
void* seqsearch(
const void* key, // キー値へのポインタ
const void* base, // 配列へのポインタ
size_t nmemb, // 要素の個数
size_t size, // 要素１つ分の大きさ
int(*compar)(const void*, const void*)
) {
const char* x
= reinterpret_cast<const char*>(base);
for (size_t i = 0; i < nmemb; i++)
// 比較関数 compar の返却値が
// 0 でなければ検索成功
if (!compar(
key,
reinterpret_cast<const void*>
(&x[i * size])
)
)
// ポインタ値を void*型にして返却
return
const_cast<void*>(
reinterpret_cast<const void*>(
&x[i * size]
)
);
// 検索値が存在しなければ NULL を返却
return NULL;
}
// ------------------------------------
// p129_演習3-8
#include <string>
#include <iostream>
void* seqsearch(
const void* key, // キー値へのポインタ
const void* base, // 配列へのポインタ
size_t nmemb, // 要素の個数
size_t size, // 要素１つ分の大きさ
int(*compar)(const void*, const void*)
) {
const char* x
= reinterpret_cast<const char*>(base);
for (size_t i = 0; i < nmemb; i++)
// 比較関数 compar の返却値が
// 0 でなければ検索成功
if (!compar(
key,
reinterpret_cast<const void*>
(&x[i * size])
)
)
// ポインタ値を void*型にして返却
return
const_cast<void*>(
reinterpret_cast<const void*>(
&x[i * size]
)
);
// 検索値が存在しなければ NULL を返却
return NULL;
}
int acmp(char* x, char* y) { // 比較関数
return strcmp(x, y);
}
int pcmp(char* x, char** y) { // 比較関数
return strcmp(x, *y);
}
int ncmp(int* x, int* y) { // 比較関数
return *x < *y ? -1 : *x > *y ? 1 : 0;
}
void existence(int n) {
std::cout << n << "番目\n";
}
void non_existence() {
std::cout << "該当なし\n";
}
int main() {
const char a[][5]
= { "cba", "cabd", "abc", "bcd",
"cab", "b", "a", "cba", "aa" };
const char* p[]
= { "cba", "cabd", "abc", "bcd",
"cab", "b", "a", "cba", "aa" };
int num[]
= { 25, 21, 16, 12, 17, 11, 23,
19, 28, 17, 22, 24, 11, 18 };
// ------------------------------------
std::cout << "◆";
for (int i = 0; i < 9; i++)
std::cout << a[i] << ' ';
std::cout << '\n';
char key1[10];
std::cout << " 探索する文字列は？ : ";
std::cin >> key1;
std::cout << " " << key1 << " → ";
void* f = seqsearch(
key1,
a,
sizeof(a) / sizeof(a[0]),
sizeof(a[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(acmp)
);
if (f == 0) non_existence();
else existence((char(*)[5])f - a + 1);
// ------------------------------------
std::cout << "\n◆";
for (int i = 0; i < 9; i++)
std::cout << p[i] << ' ';
std::cout << '\n';
char key2[10];
std::cout << " 探索する文字列は？ : ";
std::cin >> key2;
std::cout << " " << key2 << " → ";
f = seqsearch(
key2,
p,
sizeof(p) / sizeof(p[0]),
sizeof(p[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(pcmp)
);
if (f == 0) non_existence();
else existence((char**)f - p + 1);
// ------------------------------------
std::cout << "\n◆";
for (int i = 0; i < 14; i++)
std::cout << num[i] << ' ';
std::cout << '\n';
int key;
std::cout << " 探索する整数値は？ : ";
std::cin >> key;
std::cout << " " << key << " → ";
f = seqsearch(
&key,
num, sizeof(num) / sizeof(num[0]),
sizeof(num[0]),
reinterpret_cast<int(*)(
const void*,
const void*
)>(ncmp)
);
if (f == 0) non_existence();
else existence((int*)f - num + 1);
}
| 新品価格 | | 新品価格 |
2017年12月01日
《その158》 関数形式マクロ
関数形式マクロ
次のプログラムは、版明解C++中級編 p.128 にあるint型配列用のクイックソート関数 quickに、動作確認用のプログラムを付け足したものです。
プログラムの２行目
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
は、関数形式マクロです。
このマクロ定義により、プログラム中の
swap(int, v[pl], v[pr]);
は、コンパイル時に
do { int t = v[pl]; v[pl] = v[pr]; v[pr] = t; } while (0);
に書き換えられます。
// ------------------------------------
#include <iostream>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
// int型配列のクイックソート
void quick(int v[], int n)
{
if (n > 0) {
int pl = 0;
int pr = n - 1;
int x = v[(pl + pr) / 2];
do {
while (v[pl] < x) pl++;
while (v[pr] > x) pr--;
if (pl <= pr) {
swap(int, v[pl], v[pr]);
pl++;
pr--;
}
} while (pl <= pr);
if (0 < pr) quick(v, pr + 1);
if (pl < n - 1) quick(v + pl, n - pl);
}
}
int main() {
int num[] = { 25, 21, 16, 12, 17, 11, 23, 19, 28, 17, 22, 24, 11, 18 };
std::cout << "◆ 25, 21, 16, 12, 17, 11, 23, 19, 28, 17, 22, 24, 11, 18\n";
quick(num, sizeof(num) / sizeof(num[0]));
std::cout << "→ ";
for (int i = 0; i < sizeof(num) / sizeof(num[0]); i++)
std::cout << num[i] << " ";
std::cout << '\n';
}
// ------------------------------------
| 新品価格 | | 新品価格 |
続きを読む...
《その157》 クイックソートのソート手順
クイックソートのソート手順
次の配列 a を、クイックソートの手順に従ってソートしてみます。
以下、赤色の数字がそれぞれの場合の基準値です。
プログラムは、関数の再帰的呼出し等で同じ作業を繰り返すような形のものになるので、このソート手順の例でもそうですが、不要な作業も入ってきます。場合分けして、それを避けるより、無駄な部分が生じても単純作業に徹するほうがコスト的にも有利だったりするようです。
| 新品価格 | | 新品価格 |
