заполнение STL map
Самый быстрый способ вставлять - использовать функцию:
iterator insert(iterator position, const value_type& val) тогда вставка одного элемента приблизительно - const. (если подсказка конечно верная)
iterator insert(iterator position, const value_type& val) тогда вставка одного элемента приблизительно - const. (если подсказка конечно верная)
то есть, если я, например, буду вставлять элементы в порядке возрастания, то pos нужно всегда указывать end? не будет ли в таком случае там каких-нибудь излишне частых балансировок? или он там внутри не балансируется сам?
Балансируется. Можно самому задать хеширующую функцию. Для численных значений проще задать <>, тогда при добавлении в порядке возрастания перестраивать ничего не надо, и хэш будет без дырок.
А я не очень понял, что ты имел под "балансируется". map организован на основе list-a, поэтому операции со списками у него быстрые в лучшем случае константа, как выше было сказано, а в худшем - O(log N). Сверху описанная функция делает проверку три раза: элемент слева, элемент стоящий на указываемую позицию, элемент справа, если все в порядке выделяет память под новую пару, и присоеденяет listo-вые указатели. Скорее всего так.
хм...
Каким это образом в list-е можно организовать поиск за log(N)?
Каким это образом в list-е можно организовать поиск за log(N)?
Я не имел ввиду что на основе std::list, а что принцип связи элементов основан на листовом, т.е. у каждого элемента есть пара указателей на предыдущий и последующий элементы. Иначе не понятно, почему элементы могут так быстро втсавляться.
Проблема в том, что после вставки элементов необходимо обеспечить, чтобы последующие поиски работали за log(N). - это и есть балансировка.
вставка порядка O(log N) - плохо, так как тогда N элементов вставится за время порядка O(N log N а надо O(N)
iterator
insert(iterator position, const value_type& x);
If a value_type with the same key as x is not present in the map, then x is inserted into the map. Otherwise, the pair is not inserted. A position may be supplied as a hint regarding where to do the insertion. If the insertion is done right after position, then it takes amortized constant time. Otherwise it takes O(log N) time.
Это цитата из Борландовского хелпа.
Если будешь правильно подсказывать, то будет O(N).
insert(iterator position, const value_type& x);
If a value_type with the same key as x is not present in the map, then x is inserted into the map. Otherwise, the pair is not inserted. A position may be supplied as a hint regarding where to do the insertion. If the insertion is done right after position, then it takes amortized constant time. Otherwise it takes O(log N) time.
Это цитата из Борландовского хелпа.
Если будешь правильно подсказывать, то будет O(N).
Для реальных N O(N) и O(NlogN) - это почти одно и то же.
Оставить комментарий
Landstreicher
Есть std::map (для примера, std::map<double, int>).Его нужно записывать/читать с диска.
Записать можно в отсортированном порядке пробегая map итератором.
Вопрос: а вот в каком порядке надо вставлять элементы в map, чтобы суммарное время вставки было порякда O(N где N - число элементов? Предполагается, что есть уже отсортированный по double массив пар.