Namaran

Code daily. Without assist.

2026-09-08

attach_authors.c

#include <stdlib.h>

struct user {
    int id;
    const char *name;
};

void attach_authors(const int *author_ids, size_t n, const struct user *users, size_t m, const char **names) {
}

投稿 i の著者IDが author_ids[i] に入っています。著者は SELECT id, name FROM users WHERE id IN (...) ORDER BY id の1回でまとめて取得してあり、users の先頭 m 要素に id の昇順で並んでいます。各投稿の著者の名前を names[i] に入れる attach_authors を書いてください。users に見つからない著者(削除済みのユーザーなど)は NULL にします。1投稿あたりの手間は、m の対数に比例する程度に抑えます。author_ids = {3, 1, 3, 7}、users = {{1, "ann"}, {3, "bob"}} → names = {"bob", "ann", "bob", NULL}、n = 0 → names には何も書かない

Reference
static int cmp_user(const void *key, const void *elem) {
    int id = *(const int *)key;
    const struct user *u = elem;
    return (id > u->id) - (id < u->id);
}

void attach_authors(const int *author_ids, size_t n, const struct user *users, size_t m, const char **names) {
    for (size_t i = 0; i < n; i++) {
        const struct user *u = bsearch(&author_ids[i], users, m, sizeof users[0], cmp_user);
        names[i] = u ? u->name : NULL;
    }
}

1投稿ごとに users を先頭から探すと、手間が m に比例します。users は id の昇順に並んでいるので、標準ライブラリの bsearch で二分探索できます。

bsearch は比較関数の第1引数に探しているキーへのポインタを、第2引数に配列要素へのポインタを渡します。qsort の比較関数と違い、この2つは同じ型でなくてかまいません。参考実装ではキーを int のまま渡し、比較関数の中で第1引数を const int *、第2引数を const struct user * として読んでいます。探すためだけに struct user を1つ作る必要はありません。

見つからないとき bsearch は NULL を返すので、それをそのまま names[i] の NULL に使えます。比較の結果を id - u->id ではなく (id > u->id) - (id < u->id) で作っているのは、引き算だと値の組み合わせによって int が溢れるからです。

掲載したのは参考実装で、唯一の正解ではありません。二分探索を自分で書いても、同じ手間で対応づけられます。