Могу ли я предварительно загрузить карту STL без поворота карты?

Question

Я отсортировал данные, поступающие из базы данных, для инициализации карты STL. Только 5% данных будут изменены позже внутри карты.

Как я понимаю, для каждой вставки будут происходить накладные расходы на ротацию. Можно ли обойти накладные расходы для отсортированных данных? например есть ли возможность пропустить вращение и другой алгоритм STL для создания сбалансированного дерева с отсортированными данными?

PS: я знаю, что будет только 2 максимальных вращения, но мне было интересно, смогу ли я улучшить производительность дальше.

Answer 1

Полагаю, вас интересует только эффективная загрузка исходных отсортированных данных?

Стандартный map :: map (сначала InputIterator, затем InputIterator) конструктор , кажется, работает правильно.

"Для конструктора итератора: linear на расстоянии между итераторами (конструкции копирования), если элементы уже отсортированы в соответствии с comp. Для несортированных последовательностей, линейное (N * logN) на этом расстоянии ( сортировка, копирование конструкций). "

Answer 2

http://www.sgi.com/tech/stl/Map.html

Я думаю, что map (InputIterator f, InputIterator l) может вам помочь, но я не знаю, учитывает ли это сортируемые данные: /

Answer 3

Функция std::map::insert(iterator, pair) имеет амортизированные постоянные затраты, если вход отсортирован. Чтение всего набора данных означает, что вы получите O (N). (Обратите внимание, что эта программа имеет правильную семантику независимо от того, отсортирован ли ввод.)

#include <map>
#include <iostream>
int main() {
 std::map<int, int> m;
 int a, b;
 for(std::map<int,int>::iterator it = m.begin();
     std::cin >> a >> b;
     it = m.insert(it, std::pair<int,int>(a,b))) {
  /* nothing */
 }
}

Answer 4

Я не верю, что у вас есть какие-либо гарантии относительно фактической структуры данных, используемой под капотом для карты STL. Кроме того, учтите, что порядок вставки данных (вы утверждаете, что они отсортированы) может негативно повлиять на производительность, если карта не выполняет повороты! Конечно, ротация подразумевает, что используется самобалансирующееся дерево, а не список пропусков, дерево сплайнов или любая другая структура данных, выбранная автором библиотеки.

Вероятно, время, потраченное на извлечение данных из базы данных, будет меньше времени, затрачиваемого на добавление отсортированных данных в карту. Возможной оптимизацией было бы НЕ извлекать данные в отсортированном порядке. Карта не будет заботиться о сортировке.

Answer 5

Если вам необходимо использовать карту, тогда рассмотрите возможность использования контейнеров на основе политики gcc, если можете.Они намного быстрее, чем STL.

http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/interface.html