Поскольку bsearch() возвращает только один элемент, я интерпретирую «найти несколько экземпляров ключа» как «найти первый экземпляр ключа».Затем вызывающая сторона может выполнить шаг вперед по массиву из этого элемента, чтобы обработать каждый элемент, соответствующий ключу, до тех пор, пока он не достигнет конца или не достигнет элемента, который не соответствует.
Если необходимо использовать стандартную библиотеку bsearch()и убедите его найти первый элемент, соответствующий заданному ключу, тогда все, с чем вам действительно нужно работать, это функция сравнения, которую вы представляете.bsearch() вернет элемент, который соответствует ключу в соответствии с этой функцией, но если более одного элемента соответствует, то нет гарантии, какой из них будет возвращен.Таким образом, вы должны убедиться, что соответствует только тот элемент, который вы хотите.
Вы можете подойти к этому с соответствующей реализацией функции сравнения, но есть существенная проблема.В некоторых случаях функция должна оценивать элемент, предшествующий указанному ей, но не должна пытаться проверить элемент, предшествующий первому массиву.bsearch() сама не передает никакой информации о границах массива в функцию сравнения.
Существует как минимум два возможных решения, ни одно из которых не является звездным.
- Storeнижняя граница массива в каком-то известном месте, к которому может получить доступ функция. Например, если функция сравнения является статической функцией-членом, то, возможно, вам следует использовать статическую переменную этого класса.Но это не потокобезопасно.Вы можете сделать что-то похожее с локальными переменными потока, но даже тогда это ужасно.В любом случае, вы должны быть уверены, что установили эту переменную перед вызовом
bsearch(), и это тоже уродливо.
ИЛИ
Убедитесь, что вы никогда не набрали bsearch() для первого элемента. Один из способов сделать это - предварительно проверить, соответствует ли первый элемент (но не через функцию сравнения), и использовать его напрямую.вместо вызова
bsearch() в случае совпадения.Я бы обернул это в метод, сам, и если вы не должны делать этого, то требование, чтобы такая вызывающая дисциплина использовалась вручную, также ужасно.
Выбрав один из вышеперечисленных, вы можетереализовать функцию сравнения, которая смотрит на ключ предыдущего элемента в дополнение к указанному элементу.Что-то вроде этого (что предполагает второй вариант):
struct my_item {
int key;
void *data;
};
// bsearch() passes the target item as the first argument, and the one to compare
// to it as the second
int compare_items(const void *to_find, const void *to_check) {
const struct my_item *to_find_item = (const struct my_item *) to_find;
const struct my_item *to_check_item = (const struct my_item *) to_check;
// Check first how the key members are ordered
if (to_find_item->key < to_check_item->key) {
return -1;
} else if (to_find_item->key > to_check_item->key) {
return 1;
} else {
// The key members match, so check whether we're looking at the first
// such item.
const struct my_item *previous_item = to_check_item - 1;
// If the previous item's key does match, then we know the item we're
// looking for is an earlier one than we are presently checking.
return (previous_item->key == to_check_item->key) ? -1 : 0;
}
}