《その148》汎用ユーティリティ関数 bsearch　&　p.111演習3-6: C++，C++/CX に挑戦！

2017年11月23日

《その148》汎用ユーティリティ関数 bsearch　&　p.111演習3-6

　bsearch関数


// bsearch関数(あらゆる型の配列からの探索を行うことができる｡)
// #include <cstdlib>
//                            ①     ②           ③            ④
//                            ↓     ↓           ↓            ↓
//  void* bsearch(const void* key,
//                      const void* base, size_t nmemb, sizt_t size,
//                      int (*compar)(const void*, const void*));
//                            ↑
//                            ⑤ 比較関数

・ bsearch関数は、キー値①と一致する配列要素へのポインタを返します。
　　(一致する要素が見つからなければ、空ポインタを返します。)
・ ②は配列の先頭要素へのポインタです。
・ bsearch関数は、引数①,②を void型として受け取ります。
　　(void型ポインタは、どのようなポインタ型でも受け取る汎用ポインタ)
・ ③は配列要素の個数です。
・ ④は配列要素の大きさです。
・比較関数⑤ 例えば int_cmp を bsearch関数に渡す際には、キャストが必要です。
　　　　reinterpret_cast<int(*)(const void*, const void*)>(int_cmp);
　　　比較関数は、配列要素の大小の判定方法を bsearch関数に教えます。
　　　比較関数は二つの引数を比較して、第１引数の値が小さければ負の値
　　　を、大きければ正の値を、二つが等しければ 0 を返す仕様にします。
・ bsearch関数に渡す探索対象の配列は、ソート済みでなければなりません。

　bsearch関数が返す配列要素へのポインタは void*型です。
そのため、次のプログラムでは、それを int*型にキャストしています（void型ポインタをint型にする際は、明示的な型キャストが必要です）。
このプログラムでは、x が int型配列の先頭要素へのポインタ、p がキー値と一致するint型配列要素へのポインタです。
二つのポインタ x, p は同じ int型配列の要素を指す int型ポインタですから、その差、
　　　p - x
は、p が指す配列要素の添字の値と一致します。


// ------------------------------------------
#include <cstdlib>
#include <iostream>
using namespace std;

int int_cmp(const int* a, const int* b) {   // 比較関数
    return *a < *b ? -1 : *a > *b ? 1: 0;
}

int main()
{
    int x[] = { 15, 18, 18, 23, 39, 57, 68, 72 };
    int nx = sizeof(x) / sizeof(x[0]);      // 配列の要素数
    for (int i = 0; i < nx; i++)
        cout << "x[" << i << "]…" << x[i] << "  ";
    cout << '\n';


    int no;
    cout << "探索する値 : ";
    cin >> no;                  // ｷｰ値が格納されたｵﾌﾞｼﾞｪｸﾄ

    int* p = reinterpret_cast<int*>(
      bsearch(
        &no,            // ① ｷｰ値が格納されているｵﾌﾞｼﾞｪｸﾄへのﾎﾟｲﾝﾀ
        x,              // ② 配列の先頭要素へのﾎﾟｲﾝﾀ
        nx,             // ③ 配列の要素数
        sizeof(int),    // ④ 配列要素の大きさ
        // ⑤ 比較関数へのﾎﾟｲﾝﾀ(bsearch関数が受け取れる型にｷｬｽﾄ)
        reinterpret_cast<int(*)(const void*, const void*)>(int_cmp)
      )
    );

    if (p != NULL)
        cout << "x[" << p - x << "]が一致\n";
    else
        cout << "見つかりません。\n";
}
// ------------------------------------------

新版明解C++中級編　p.111 演習3-6
　bsearch関数を用いて、文字列の配列からの探索を行うプログラムを作成せよ。
　(ⅰ) 「２次元配列で実現された文字列の配列からの探索を行うプログラム」と、
　(ⅱ) 「文字列の先頭文字へのポインタの配列で実現された文字列からの探索を行うプログラム」の二つを作ること。


// 　(ⅰ)
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;

int charstr_cmpr(const char* a, const char* b) {
    return strcmp(a, b);        // strcmp関数 … ﾍｯﾀﾞ<cstring>
}

int main() {
    const char s[][10] = { "abc", "abcd", "ac", "bca", "cab", "cba" };

    for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++)
        cout << s[i] << "  ";
    cout << '\n';

    while (1) {
        char key[20];
        cout << "◆探索文字列 : key = "; cin >> key;

        char* p = reinterpret_cast<char*>(
            bsearch(
                key, s, sizeof(s) / sizeof(s[0]), sizeof(s[0]),
                reinterpret_cast<int(*)(const void*, const void*)>(charstr_cmpr)
            )
        );
        if (p != NULL)
            cout << "s[" << (p - s[0]) / sizeof(s[0]) << "]が一致\n";
        else
            cout << "無し\n";
        int cont;
        cout << "継続(1) or 終了(0) : "; cin >> cont;
        if (!cont) break;
        else cout << '\n';
    }
}


// 　(ⅱ)
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std;

int cmpr(const char* a, const char** b) {
    return strcmp(a, *b);        // strcmp関数 … ﾍｯﾀﾞ<cstring>
}

int main() {
    const char* s[] = { "abc", "abcd", "ac", "bca", "cab", "cba" };
    for (int i = 0; i < sizeof(s) / sizeof(s[0]); i++)
        cout << s[i] << "  ";
    cout << '\n';

    while (1) {
        char key[100];
        cout << "キー値 : "; cin >> key;

        char** p = reinterpret_cast<char**>(
            bsearch(
                key, s, sizeof(s) / sizeof(s[0]), sizeof(char*),
                reinterpret_cast<int(*)(const void*, const void*)>(cmpr)
            )
        );

        if (p != NULL)
            cout << "s[" << p - s << "]が一致\n";
        else
            cout << "無し\n";
        int cont;
        cout << "継続(1) or 終了(0) : "; cin >> cont;
        if (!cont) break;
        else cout << '\n';
    }
}