@-NEURON-

Есть какой - то список уже существующих уникальных ID, нужно наибыстрейшим способом создать новый уникальный для этого списка ID. (пусть тип ID будет допустим unsigned int)
1. В каком виде лучше хранить список переменной длинны всех уникальных ID ? std::map ?
2. Каким наибыстрейшим способом можно сгенерить уникальный ID ? Если map - ну там всё просто, но сдаётся мне, что это не наибыстрейший способ... Может хранить всё в std::vector, а во время генерации проверять std::binary_search-ем наличие ID в списке и если такого нет - добавлять, если есть - генерить заново ...

0

@Nick Alte

Завести счётчик, скажем, unsigned int. Каждый раз, когда нужен новый ID, брать его значение и увеличивать на единицу. Первые 4 миллиарда ID, выданных таким счётчиком, будут уникальными. Если "малавата будет", есть long long, это ещё в 4 миллиарда раз больше. Если изначально докрутить его до числа, на 1 большего из всех существующих ID, можно как-то к ним приспособиться.
В смысле поиска самым быстрым будет unordered_map, у binary_search и map эквивалентная сложность поиска O(log N).

1

@DrOffset

Т.е. задача получить список уникальных ID исходя из другого списка уникальных ID?
y = f(x), где x старый ID, а y - новый? Так?

Зависит от задачи. Как планируется этот список использовать?
Разве std::map что-то генерирует? std::map - это хранение и доступ, а не генерация.

Добавлено через 7 минут
Это зависит от характера данных. Если у нас ключи какие-нибудь длинные строки, для которых нет достаточно хорошей хэш-функции, то он запросто может оказаться не лучшим решением.

-NEURON-, нельзя выбирать быстрейшее решение абстрактно. Оно всегда привязано к задаче.

1

@-NEURON-

нее - задача сгеннерить один новый id, которого ещё нет в списке уникальных id.
ну у него ключ то уникален, чиста ради этого. Ну типа map .... count() > 1 - значит уже есть ...ну да не суть.
Да, именно об это я конечно же сразу и подумал. Но в моём случае речь идёт и крутой клиент серверной системе, работающей нон стоп 10-и летиями. А самая засада в том, что вот есть этот список элементов, у каждого свой уникальный ID, я спокойно добавляю туда новые элементы инкрементом последнего ID как бы, но, из этого списка элементы могут удаляться (по одному, по несколько), то есть получается что освобождаются потенциальные номера для новых id и я подумал, может их тоже использовать ... Т.к. лет за 10 даже unsigned long long может исчерпаться, учитывая то, что в день может добавляться по 1000 новых id в систему ... Хотя я не считал - ща проверю на сколько хватит Просто сама мысль о том, что когда - то они закончатся - как то меня тревожит ...

0

@Nick Alte

Тогда рекомендую сразу за компанию посчитать, когда закончатся 16 квинтиллионов чисел (1.6e19, на минуточку), выражаемых long long, при пиковой скорости выдачи ID.

0

@-NEURON-

Хотя я тут подсчитал, даже если по миллиону новых ID в день добавлять, размера unsigned long long хватить больше чем на 50 миллиардов лет ))))))))))))))))))))))
Единственных косяк, программа x86, по этому на каждую операцию будет намного больше времени тратится, нежели на x64... Ща подсчитаю, на сколько мне unsigned int хватить

0

@DrOffset

При условии 64 разрядного счетчика это будет 50539024859478 лет, если считать, что в год добавляется 365000 записей.

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

0

@-NEURON-

Вот думал тут не гемороиться с инкрементами и всякими проверками ну уникальность, просто брать уникальный в каждую микросекунду ID, основывая на тайм штампе каком - нибуть, скажем 1970-го года... Ну считать, cколько микросекунд прошло с того года... Но тут дело в том, что на компе могут перевести время и привет

0

@DrOffset

Ничего себе не геморроится. Так-то unix time (дада, тот, который с 1970) - это тоже целое число.

Добавлено через 7 минут
Если ты действительно собираешься хранить миллиарды значений, то любой контейнер и любой алгоритм будут сильно проседать при таком подходе (т.к. все они зависят от N).
Счетчик - это лучшее решение. Если он контролируется из одного места, скажем какой-нибудь менеджер соединений. Появился клиент, выдали ему следующий ID увеличив счетчик и т.д.
uptime 10 лет - это редкость невероятная, но допустим. За 10 лет ты не исчерпаешь возможностей, как ни крути. Там скорее уже железо на сервере будут менять, чем эти ID кончатся

1

@-NEURON-

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

0

@DrOffset

Эм, а куда делись миллиарды значений?
А вообще для строк - можно использовать хэширование. Тем более если известна максимальная длина, то есть надежда найти хорошую хэш-функцию и дело в шляпе. Как раз упомянутый выше unordered_set/map подойдет.

Добавлено через 2 минуты
Вот, ознакомься.

Добавлено через 1 минуту
И вот, практика.

1

@-NEURON-

Ща покурю мануал по - поводу unordered map-а, т.к. в повседневных задачах кроме vecot-а и простого map-а (ну не считая всяких стрингов) особо ничего не приходилось использовать, вот реально - хватало.

0

@DrOffset

-NEURON-, если хочется еще производительность, то можно вместо unordered_set\map использовать одноименный контейнеры из boost.intrusive. Если про задачу известны какие-то детали, например, до начала добавления в контейнер можно сказать сколько всего будет вставок, то можно очень сильно поднять производительность, исключив перехеширование таблицы и создав ее заранее нужного размера. Ну и т.д.
Название как бы намекает

1

@-NEURON-

Нее...буст не хочу тащить за собой, вот когда его официально включать в С++17, тогда возможно. Пока что всё на Qt

0

@DrOffset

-NEURON-, А если например нужен словарный поиск или частичный поиск строк (особенно длинных строк), то тут еще лучше подойдет ternary tree и его вариации.
Короче, всегда задача на первом месте. Без изучения предметной области задачи ничего оптимизировать не надо. Иначе можно сильно сесть в лужу. Серебряной пули на все времена - нет.

Добавлено через 1 минуту
А, религия. Ну понятно

0

@-NEURON-

Ехехе...Да не... Не люблю с собой лишнюю тележку библиотек таскать
Кстати, может я отстал от жизни уже, но нет ли в стандартном STL C++11 какого - то контейнера, для хранения уникальных значений в одинарном списке, ну то есть если мне нужен контейнер, куда бы я мог бы просто вставлять уникальные строки... Ну вот std::map<std::wstring,int> например, мне для уникальных значений нужен только std:wstring, второе поле пары мне не нужно, есть какой - унарный контейнер типа мапа ?

0

@DrOffset

-NEURON-, ну std::unordered_set/std::set же

1

@-NEURON-

А, ну ок, мне просто лень было весь текст про них прочитать

0