Применение c ++ & lt; lower_bound & quot; на массиве строк символов
Я пытаюсь использовать функцию lower_bound в C ++.
Использовал его несколько раз для типов данных 1 d.
Теперь я пытаюсь это на sorted array dict[5000][20] найти строки size <=20,
Соответствующая строка находится в str,
bool recurseSerialNum(char *name,int s,int l,char (*keypad)[3],string str,char (*dict)[20],int
dictlen)
{char (*idx)[20]= lower_bound(&dict[0],&dict[0]+dictlen,str.c_str());
int tmp=idx-dict;
if(tmp!=dictlen)
printf("%s\n",*idx);
}
Согласно http://www.cplusplus.com/reference/algorithm/lower_bound/?kw=lower_bound , эта функция должна возвращать индекс ‘last’ (за пределами end), если совпадение не найдено, т.е. tmp должно быть равным dictlen,
В моем случае он всегда возвращает начальный индекс, т.е. tmp equal to 0 оба 1. Когда передали строку, которая есть в dict и 2. Когда передана строка, которой нет в dict,
Я думаю, что проблема заключается в обработке и передаче указателя. default comparator должно быть доступно для этого случая, как доступно для случая вектора. Я также попытался передать явный, но безрезультатно.
Я попробовал этот компаратор —
bool compStr(const char *a, const char *b){
return strcmp(a,b)<0;
}
Я знаю ALTERNATE это использовать вектор, и т. д., но я хотел бы знать проблему в этом.
Искал по этому поводу гугл так же, как и SO, но ничего похожего не нашел.
Решение
Я считаю, что здесь есть два недоразумения.
std::lower_boundне проверяет, является ли элемент частью отсортированного диапазона. Вместо этого он находит крайнее левое место, где элемент может быть вставлен без нарушения порядка.- Вы сравниваете не содержимое строк, а адреса их памяти.
Правда, что dict в вашем случае это отсортированный диапазон в том смысле, что адреса памяти внутренних массивов возрастают. Где по отношению к этому str.c_str() ложь, конечно, не определена. На практике, dict является стековым объектом, вы часто обнаружите, что диапазон памяти для кучи (где str.c_str() всегда лежит) ниже стека, и в этом случае lower_bound совершенно правильно говорит вам, что если вы хотите вставить этот адрес в отсортированный диапазон адресов, которые вы интерпретируете dict, вы должны были бы сделать это в начале.
Для решения, так как есть operator<(char const *, std::string const &)Вы могли бы просто написать
char (*idx)[20] = lower_bound(&dict[0], &dict[0] + dictlen, str);
…но вы, возможно, действительно ищете std::find?
Другие решения