C++ map большая числовая строка в числовые диапазоны строк

Question

Мне нужно написать функцию C++, где ввод представляет собой 12-значную цифровую строку. Я должен найти диапазон, который также хранится в строковых массивах.

Для примера,

массив Диапазон [10]:
1 - 111115555522 - 111225555521
2 - 111225555522 - 111335555521
3 - 111335555522 - 111445555521
4 - 111445555522 - 111555555521
5 - 111555555522 - 111665555521
6 - 111665555522 - 111775555521
7 - 111775555522 - 111885555521
8 - 111885555 8 - 1118855510 522 - 111995555521
9 - 111995555522 - 112005555521
10- 112005555522 - 113005555521

вход -
Выход - номер принадлежит диапазоне -

Я использовал «длинный длинный "тип данных для числовых диапазонов и ввода, а также выполнил его. Но поскольку я должен также поддерживать производительность, может ли кто-нибудь дать мне лучшую идею сделать так, чтобы входное значение оставалось строковым, а диапазоны также оставались в строке?

P.S .: Я отлично использую указатели «char» вместо std :: string.

Answer 1

Не используйте строку, за исключением случаев преобразования любых входных данных. Это будет на порядок медленнее, чем использование интегральных типов. Вместо этого поддерживайте позиции диапазона в std::vector<std::uint64_t>.

Отметив, что ваш вектор будет отсортирован, используйте std::lower_bound или std::upper_bound, чтобы получить диапазон, в котором можно найти данный номер. Эти функции работают O (log N), и так быстро. Прочитайте тонкие различия между этими функциями.

(Обратите внимание, что std::uint64_t является всегда 64-битовое беззнаковое целое число, так что хорошо для 12 цифр, но учтите, что компилятор C++ делает не обязательно должны поддерживать его, хотя это было очень давно, так как я 'натолкнулся на тот, который этого не делает.)

Answer 2

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

Пример: допустим, что вы сохраняете диапазоны в массиве, number_ranges [10], где number_ranges [0] является нижней границей первого диапазона, number_ranges [1] является нижней границей второго диапазона (и все, что находится ниже этого, все еще находится в первом диапазоне) и т. д. Давайте также будем иметь массивы логических значений, возможных_ranges [10], где true означает, что диапазон все еще возможен, а false означает, что это не так.Поскольку мы ничего не устранили перед запуском, все должно быть установлено в true. Теперь нам нужно пройти каждую строку и, если необходимо, устранить диапазоны.

for (int i = 0; i < (length of input); i++) { 
    for (int j = 0; j < (number of ranges, which is ten); i++ { 
     if (input[i] is less than number_ranges[j][i], then there is no way we're in that range, so make that range false) 
     if (input[i] is greater or equal to number_ranges[j][i], then there is no way we're in the range below it, so make that false) 
     if (everything is false but one, you have your answer, so return it) 
    } 
} 

Answer 3

Идея куки: попробуйте набор. Набор будет заказывать все значения, которые вы вставляете. Тогда вам просто нужно найти, где в наборе вводится входное значение. Если вам нужно повторно использовать диапазон, не забудьте удалить вход после. Следующие строки используются. Версия, которая преобразует строки в целые числа некоторого типа, почти наверняка будет быстрее.

int main(int argc, char* inpp[]) 
{ 
    if (argc < 2) 
    { 
     cout << "Need input, dude." << endl; 
    } 
    string in = inpp[1]; 
    set<string> range; 
    range.insert("111225555521"); // add all range end values to set 
... 
    range.insert("113005555521"); 

    range.insert("111115555522"); // add start value of first range 

    range.insert(in); // add the input value 
    int result = std::distance(range.begin(), range.find(in)) ; 
    cout << result << endl; 
    set.erase(loc); 
}