【C言語】lfind関数の使い方

lfind関数の解説ページアイキャッチ

このページでは、C言語の標準関数である lfind 関数について主に解説していきたいと思います。また、同じような関数に lsearch 関数もあるので、こちらについても簡単に解説したいと思います。

lfind 関数とは

それでは、まずは lfind 関数がどのような関数であるのかについて解説します。

MEMO

配列をベースに解説しますが、malloc 関数などで確保したメモリ上のデータでも同様のことを行うことが可能です

lfind 関数は配列からデータを探索する関数

lfind は、引数で指定したデータを配列の中から探索する関数です。

lfind関数の動作を示す図

スポンサーリンク

bsearch 関数との違い

同じように探索を行う関数としては bsearch 関数がありますが、動作としての違いは探索時に用いられるアルゴリズムのみです。

bsearch 関数では探索のアルゴリズムに “二分探索” が使用されますが、この lfind 関数では探索のアルゴリズムに “線形探索” が使用されます。

この2つのアルゴリズムについては下記ページで解説していますので、2つのアルゴリズムの違いや実装方法などを知りたい方は是非読んでみてください。

探索アルゴリズム解説ページのアイキャッチ【C言語】データの探索アルゴリズム(線形探索・二分探索)について解説

使い方に関していうと、lfind 関数と bsearch 関数の違いは下記の4つのみになります。

  • lfind 関数は search.h で宣言
  • lfind 関数では第3引数にアドレスを指定
  • lfind 関数ではソートが不要
  • lfind 関数の比較関数では2つのデータが同じかどうかのみを判断

bsearch 関数の使い方に関しては下記ページで詳細に解説していますので、このページでは上記の4つの違いに注目して lfind 関数の使い方をサラッと解説させていただきたいと思います。

bsearchの使い方の解説ページアイキャッチ【C言語】bsearch関数の使い方

このページで解説不足な点があっても、おそらくそれは上記の bsearch 関数の解説ページで説明していると思いますので、その場合はお手数ですが上記ページを参照していただければと思います。

lfind 関数の使い方

それでは lfind 関数の使い方(実行の仕方)について解説していきます。

lfind 関数の定義

まず lfind の関数定義は下記のようになります。

lfind関数
#include <search.h>

void *lfind(const void *key, const void *elems, size_t *num_elem, size_t size_elem, int (* compar)(const void *, const void *));

その一方で、bsearch の関数定義は下記のようになります。

bsearch関数
#include <stdlib.h>

void *bsearch(const void *key, const void *elems, size_t num_elem, size_t size_elem, int (* compar)(const void *, const void *));

lfind 関数は search.h で宣言

まず lfind 関数と bsearch 関数とでは、プロトタイプ宣言されているヘッダーファイルが異なります。

bsearch 関数が宣言されているのは stdlib.h であるのに対し、lfind 関数が宣言されているのは search.h です。

bsearch 関数と同様に stdlib.h で宣言されていると勘違いしがち(少なくとも私は勘違いしていた)なので注意してください。

スポンサーリンク

lfind 関数の引数

lfind 関数の引数で指定するデータは以下の通りです。第3引数以外に関しては、lfind 関数と bsearch 関数とは全く同じものになります。

  • 第1引数 key:探索したいデータ(キー)のアドレス
  • 第2引数 elems:探索を開始するデータのアドレス
  • 第3引数 num_elem:探索対象のデータの数への “アドレス”
  • 第4引数 size_elem:探索対象の各データのサイズ(バイト)
  • 第5引数 compare:比較関数のアドレス

上記の引数に対し、lfind 関数では、アドレス elems から *num_elem 個分のデータ(各データのサイズは size_elem)を探索対象として、key の指すデータの探索が実行されます。探索に必要な比較は compare の指す関数により行われます。

lfind 関数では第3引数にアドレスを指定

bsearch 関数では、”ソート対象のデータの数” そのものを第3引数に指定すればよかったのですが、lfind 関数では、”ソート対象のデータの数” が格納された変数のアドレスを指定する必要があるので注意してください。

lfind 関数の第3引数に、bsearch 関数同様に “ソート対象のデータの数” を指定しまうと、おそらくプログラムが異常終了します。

lfind 関数の戻り値

また、lfind 関数の戻り値は下記のようになります。この戻り値に関しては bsearch 関数と全く同じです。

  • 第2引数 elems から第1引数 key の指すデータが見つかった時:
    • 最初に見つかった elems のデータのアドレス
  • 第2引数 elems から第1引数 key の指すデータが見つからなかった時:
    • NULL

lfind 関数の基本的な使い方

ここまでの復習の意味も込めて、lfind 関数の基本的な使い方を紹介していきたいと思います。

例えば、下記のような int 型の配列 array の中から  7lfind 関数を使用して探索する場合について考えてみましょう。

探索対象の配列array
int array[10];

配列名は array、配列のデータ数は 10、配列の型は int なので、lfind 関数は下記のように実行することになります(比較関数の名前は compare としています)。

7の探索の実行
int main(void) {

    int array[10] = {
        10, 8, 3, 0, 16,
        8, 7, 32, 51, 99 
    };
    int key;
    int *ret;
    size_t num;

    /* 7を探索する */
    key = 7;
    num = 10;
    ret = lfind(&key, array, &num, sizeof(int), compare);

    /* 探索結果を表示 */
    if (ret != NULL) {
        printf("%dは配列内に存在します\n", *ret);
    } else {
        printf("%dは配列内に存在しません\n", key);
    }

    return 0;
}

bsearch 関数との違いは、下記ページの bsearch 関数の基本的な使い方とソースコードを対比すると分かりやすいと思います。

bsearchの使い方の解説ページアイキャッチ【C言語】bsearch関数の使い方

上記ソースコードのポイントは2つです。

lfind 関数では第3引数にアドレスを指定

前述の通り、lfind 関数の第3引数には “ソート対象のデータの数” が格納された変数のアドレスを指定する必要があります。

そのため、上記のソースコードでは、データの数をまず num に格納し、その num のアドレス(つまり &num)を lfind 関数の第3引数に指定するようにしています。

lfind 関数ではソートは不要

lfind 関数では、引数さえちゃんと指定してやれば、どんな並び方のデータであっても探索することが可能です。ですので、bsearch 関数のように事前にソートを実行する必要はありません。

スポンサーリンク

比較関数の作り方

上記のソースコードにおいて、lfind 関数の最後の引数に compare を指定していますが、これは lfind 関数がデータの探索時に比較を行う際に実行する比較関数のアドレスになります。

この比較関数は bsearch 関数同様に自作してやる必要があります。

ただ、lfind 関数を実行するために作成する比較関数においては、引数として渡される2つのポインタ引数の指すデータが “一致するかどうか” の判断だけ行えば良いです。

bsearch 関数の場合は、ソート対象のデータが昇順に並んでいるか、降順に並んでいるかを考慮して戻り値を設定する必要がありましたが、その点が lfind 関数では異なります。

具体的には、lfind 関数用の比較関数の戻り値は下記のようになります(第1引数のポインタが指すデータを “データ1”、第2引数のポインタが指すデータを “データ2” としています)。

  • データ1 == データ2 の場合:0
  • データ1 != データ2 の場合:0 以外

例えば下記は、int 型の配列からデータを探索する際の比較関数の例になります。

比較関数の例
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 == *p_int2) {
        ret = 0;
    } else {
        ret = 1;
    }

    return ret;
}

const int *p_int1 = p_data1; あたりの処理の必要性等が分からない場合は、下記の qsort の解説ページの比較関数の作り方で解説していますので、こちらを読んでいただければと思います。

qsort関数の使い方の解説ページアイキャッチ【C言語】qsort関数の使い方

lfind 関数の使用例

lfind 関数の解説の最後として、lfind 関数の使用例を紹介しておきます。下記は文字列の配列 array から、文字列 "Saturday" を探索する例になります。

文字列を探索する
#include <stdiio.h>
#include <search.h>
#include <string.h> /* strcmp, strcpy */

int compare(const void *p_data1, const void *p_data2) {
    const char *p_str1 = p_data1;
    const char *p_str2 = p_data2;

    return strcmp(p_str1, p_str2);
}


int main(void) {

    char array[7][256] = {
        "Sunday",
        "Monday",
        "Tuesday",
        "Wednesday",
        "Thursday",
        "Friday",
        "Saturday"
    };

    char key[256];
    char *result;
    size_t num;
    
    /* "Saturday"を探索 */
    strcpy(key, "Saturday");
    num = 7;
    result = lfind(key, &array[0][0], &num, sizeof(array[0]), compare);

    if (result != NULL) {
        printf("%sは配列内に存在します\n", result);
    } else {
        printf("%sは配列内に存在しません\n", key);
    }

    return 0;
}

下記の bsearch 関数の解説ページの文字列を bsearch 関数で探索するで、全く同じ配列 array から文字列 "Saturday" を探索する例を示していますので、それと比較すると違いが分かり易いと思います。

bsearchの使い方の解説ページアイキャッチ【C言語】bsearch関数の使い方

特に下記に注目してみると違いが分かりやすいと思います。

  • lfind 関数は search.h で宣言
  • lfind 関数では第3引数にアドレスを指定
  • lfind 関数ではソートが不要
  • lfind 関数の比較関数では2つのデータが同じかどうかのみを判断

(参考)lsearch 関数

最後に、lfind 関数と混同しやすい lsearch 関数について解説しておきます。

lsearch 関数は、基本的に lfind 関数と同様で、線形探索によりデータを探索する関数になります。関数に指定する引数の意味合いも同じです。

ただし、データが見つからなかった場合の動作が異なります。

lfind 関数では、データが見つからなかったときは単に NULL を返却して関数を終了します。

その一方で lsearch 関数では、データが見つからなかったときは、そのデータを探索対象のデータの末尾に追加します。

データが見つからなかったときのlsearchの動作を示す図

さらに、データの追加により探索対象のデータの数が 1 増えるので、lsearch 関数の第3引数(探索対象のデータの数への “アドレス”)に指定されたアドレスのデータの値を 1 増やした後、追加したデータの位置のアドレスを返却して関数を終了します。

注意すべきなのは、探索対象のデータとなる配列(やメモリ)のサイズです。

データが見つからなかった時には、その配列に対してデータが追加されることになります。ですので、探索対象のデータの数 == 配列のサイズ としている場合、その配列のサイズを超えた位置にデータが追加されることになります。

lsearch実行時にメモリアクセス違反が発生する例

配列のサイズを超えた位置にデータが追加されると、プログラムが異常終了する可能性はありますし、異常終了しなかったとしても、他の変数や他のメモリに上書きする形でデータが追加される可能性があります。

ですので、そういったことが起こらないよう、そのデータの追加を見越して探索対象のデータとなる配列のサイズを決定しておく必要があります。

例えば下記は、配列 array から 99 を lsearch により探索するソースコードになります。

lsearchでの探索(NG)
#include <stdio.h>
#include <search.h>

/* 比較関数 */
int compare(const void *p_data1, const void *p_data2) {
    int ret;
    const int *p_int1 = p_data1;
    const int *p_int2 = p_data2;

    if (*p_int1 == *p_int2) {
        ret = 0;
    } else {
        ret = 1;
    }

    return ret;
}


int main(void) {

    /* 配列のサイズは10 */
    int array[10] = {
        0, 1, 2, 3, 4,
        5, 6, 7, 8, 9
    };
    int *result;
    int key;
    size_t num;

    /* 99を探索 */
    key = 99;
    num = 10;
    result = lsearch(&key, array, &num, sizeof(int), compare);

    /* 探索結果を表示 */
    if (result != NULL) {
        printf("%dは配列の中に存在します\n", key);
        printf("%dはアドレス%pに存在します\n", key, result);
        printf("%dはソート後の配列の第%ld要素に存在します\n", key, result - &array[0]);
    } else {
        printf("%dは配列の中に存在しません\n", key);
    }

    return 0;
}

私の環境で実行した場合、下記のように abort エラーが表示され、異常終了したことが確認できました。

$ gcc main.c -o main.exe
$ ./main.exe
99は配列の中に存在します
99はアドレス0x7ffeec0afa98に存在します
99はソート後の配列の第10要素に存在します
zsh: abort      ./main.exe

上記では、99array 内に見つからないため、lsearch により探索対象のデータの末尾、つまり array[10]99 が追加されることになります。

ただし、変数宣言時に array の配列サイズを 10 にしているので、array[10] へのデータの追加は、配列のサイズを超えた位置へのデータの追加となり、上記のようにプログラムが異常終了することとなります。

lsearch 関数を利用する場合は、このようなことが起こらないよう、データが追加されても問題ないように配列のサイズを設定する必要があります。

例えば、上記の異常終了する現象は、array の配列のサイズを 11 にすることで解消することが可能です。

追加を考慮したサイズ設定
/* 配列のサイズは11 */
int array[11] = {
    0, 1, 2, 3, 4,
    5, 6, 7, 8, 9
};

この場合、lsearch 関数により array[10] にデータが追加されますが、array[10] は配列のサイズ内ですので、動作として問題なくデータが追加されることになります。

こんな感じで使い方にも注意が必要なのですが、一番注意しなくてはならないのは lfind との混同だと思います。

bsearch 関数同様に純粋な探索に用いるべき関数は lsearch ではなく lfind です。

lsearch の方が bsearch に名前が似ていますが、lsearch を使うと探索だけでなくデータの追加まで行われてしまいます。

純粋に探索を行うために lsearch を使うと、上記のようなプログラムの異常終了するかもしれないので気をつけてください。

スポンサーリンク

まとめ

このページではC言語の標準関数である lfind 関数について解説しました!

詳細な説明は bsearch 関数や qsort 関数の解説ページに委ねる形での解説になりましたが、これらの関数は使い方や比較関数の作り方が非常によく似ているので、セットで覚えておくと良いと思います。

同じ探索を行う関数でも、lfind 関数は bsearch 関数とは異なり、事前のソートが不要という利点があります。

なので、サクッと探索を行いたい場合は、こっちの lfind 関数の方が使いやすいと思います!

ただ、lfind の中で実行されている線形探索は簡単に実装できるので、関数に頼らなくても自分で実装してもいいかもしれません。

自分で実装してみたいような場合は、是非下記ページを参考にしてください!

探索アルゴリズム解説ページのアイキャッチ【C言語】データの探索アルゴリズム(線形探索・二分探索)について解説

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です