Получение нескольких экземпляров ключа с помощью bsearch ()

Question

Получение нескольких экземпляров ключа с помощью bsearch ()

есть ли способ реализовать bsearch() найти несколько экземпляров ключа.

например: (obj*)bsearch(key=r,arr,elements,sizeof(obj),(int(*)(const void*, const void*)bcompare);

Код, который я сейчас написал, находит только первый экземпляр и не может пройти дальше первого найденного из-за того, как он работает.

getline(target,81);
if(strcmp(target,"exit") == 0 || strcmp(target, "") == 0) break;
p = (Info*)bsearch(target,list,num,sizeof(Info),(int(*)(const void*, const void*))bcompare);
int foundIndex = (int)(p-list);
if(!p){
err_dis1_win();
clrscr();
}
else{
display_record(p);
cout << "\n\n found at index " << foundIndex << "\n";
getch();
clrscr();
}

Переменные:

п — указатель на объект класса Info
цель — Arr of Char
список — обр
foundIndex — индекс найденного элемента
Информация — производный класс от базового класса

** функция сравнения

int bcompare(char *a,Info *b){
return(strncmpi(a, b -> get_name(), strlen(a)));
}

Я не могу использовать другие методы, такие как std::find или написание моей собственной функции двоичного поиска и должны использовать bsearch()

Я пробовал циклы внутри блока else, и функцию сравнения, используя переменную foundIndex, а также используя цикл while для возвращаемого значения, проходящего через список объектов arr. Есть ли способ начать с определенного индекса. Я ценю любую помощь. Я не ищу код, но общий толчок в правильном направлении. Спасибо.

Предостережение — Текущий код компилируется и запускается, как и ожидалось, однако функциональность, которую я хочу, не может быть определена мной самостоятельно. Google и поиск в Stackoverflow не привели к соответствующей проблеме.

-2

bsearch c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

поскольку bsearch() возвращает только один элемент, я интерпретирую «найти несколько экземпляров ключа» как «найти первый экземпляр ключа «. Вызывающий может затем шагнуть вперед по массиву из этого элемента, чтобы обработать каждый элемент, соответствующий ключу, пока он не достигнет конца или не достигнет элемента, который не соответствует.

Если вы должны использовать стандартную библиотеку bsearch() и убедите его найти первый элемент, соответствующий заданному ключу, тогда все, с чем вам действительно нужно работать, это функция сравнения, которую вы представляете. bsearch() вернет элемент, который соответствует ключу в соответствии с этой функцией, но если более одного элемента соответствует, то нет гарантии, какой из них будет возвращен. Вы должны убедиться, что соответствует только тот элемент, который вы хотите.

Вы можете подойти к этому с соответствующей реализацией функции сравнения, но есть существенная проблема. В некоторых случаях функция должна оценивать элемент, предшествующий указанному ей, но не должна пытаться исследовать элемент, предшествующий первому массиву. bsearch() сама не передает никакой информации о границах массива в функцию сравнения.

Есть как минимум два возможных решения, ни одно из которых не является звездным.

Сохраните нижнюю границу массива в известном месте, к которому может получить доступ функция. Например, если функция сравнения является статической функцией-членом, то, возможно, вы бы использовали статическую переменную этого класса. Но это не потокобезопасно. Вы могли бы сделать что-то подобное с локальными переменными потока, но даже тогда это ужасно. В любом случае, вы должны быть уверены, что установили эту переменную перед вызовом 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;
}
}

2