Применение C++ «lower_bound» в массиве символов char

Question

Я пытаюсь использовать функцию 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, эта функция должна возвращать индекс «последний» (за конец) в случае, если совпадение не найдено, т.е. tmp должен быть равен dictlen. В моем случае он всегда возвращает начальный индекс i.e. Я получаю tmp equal to 0 как 1. Когда передана строка, которая есть в dict и 2. При передаче строки, которой нет в dict.

Я думаю, что проблема заключается в обработке и передаче указателя. default comparator должен быть доступен для этого случая, как доступно в случае вектора. Я также попытался передать явный, безрезультатно.

Я попробовал этот компаратор -

bool compStr(const char *a, const char *b){ 
    return strcmp(a,b)<0; 
} 

Я знаю, что ALTERNATE это используется вектор, и т.д., но я хотел бы знать, вопрос в этом. Искал на этом через google так же как SO, но не нашел ничего подобного.

Answer 1

Здесь, кажется, есть два недоразумения.

1. std::lower_bound не проверяет, является ли элемент частью отсортированного диапазона. Вместо этого он находит самое левое место, где элемент может быть вставлен без нарушения порядка.
2. Вы не сравниваете содержимое строк, а их адреса памяти.

Верно, что в вашем случае 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?