Как эффективно вставлять ряд последовательных целых чисел в std :: set?

Question

В C++ у меня есть std :: set, который я хотел бы вставить ряд последовательных целых чисел. Как я могу сделать это эффективно, надеюсь, в O (n) времени, где n - длина диапазона?

Я думаю, что я буду использовать версию ввода std :: insert, используемую inputIterator, но неясно, как создать входной итератор.

std::set<int> mySet; 

// Insert [34 - 75): 
mySet.insert(inputIteratorTo34, inputIteratorTo75); 

Как создать итератор ввода и будет ли это O (n) в размере диапазона?

Answer 1

Принимая намек предоставляется Акша, я вижу ответ:

#include <boost/iterator/counting_iterator.hpp> 

std::set<int> mySet; 

// Insert [34 - 75): 
mySet.insert(boost::counting_iterator<int>(34), 
      boost::counting_iterator<int>(75)); 

Answer 2

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

std::set<int>::iterator it = mySet.end(); 
for (int x : input) { 
    it = mySet.insert(it, x); 
} 

С другой стороны, вы можете рассмотреть другие контейнеры. По возможности используйте std::vector. Если количество вложений невелико по сравнению с поиском, или если все вставки происходят заранее, то вы можете построить вектор, отсортировать его и использовать lower_bound для поиска. В этом случае, поскольку вход уже отсортирован, вы можете пропустить сортировку.

Если вставки (или удаления) происходят повсюду, вы можете рассмотреть возможность использования std::unordered_set<int>, который имеет среднюю вставку (на элемент) O(1) и стоимость поиска.

Для конкретного случая отслеживания небольших чисел в наборе, все из которых малы (от 34 до 75 - это небольшие числа), вы также можете рассмотреть возможность использования битов или даже простого массива bool, в котором вы устанавливаете элементы в true при вставке. Либо у вас будет O(n) вставка (все элементы) и O(1) поиск (каждый поиск), который лучше, чем набор.

Answer 3

Непонятно, почему вы специально хотите вставить с помощью итераторов, чтобы указать диапазон.

Однако, я считаю, вы можете использовать простой для цикла для вставки с требуемой сложностью O (n).

Цитируя страницы cppreference на станд :: гарнитур, сложность:

Если N вставлены элементы, NLog (размер + N) в целом, но линейный по размеру + N, если элементы уже сортируются в соответствии с тем же самым критерием заказа, который используется контейнером.

Таким образом, используя для петли:

std::set<int> mySet; 
for(int i = 34; i < 75; ++i) 
    mySet.insert(i); 

Answer 4

может быть Всплеск способом:

std::set<int> numbers(
boost::counting_iterator<int>(0), 
boost::counting_iterator<int>(10)); 

Большой LINK для других ответов, ответ Специально @ Мани

Answer 5

std :: set - тип двоично-поискового дерева, что означает, что затраты на размещение O (lgn) в среднем равны

C++ 98: Если N элементы вставлены, Nlog (размер + N) в целом, но по размерам линейный + N, если элементы уже отсортированы по одному и тому же критерию упорядочения, используемого контейнера ,

C++ 11: Если вставлены N элементов, Nlog (размер + N). Реализации могут оптимизировать, если диапазон уже отсортирован.

Я думаю, что реализация C++ 98 будет отслеживать текущий узел вставки и проверять, будет ли следующее значение вставки больше текущего, и в этом случае нет необходимости начинать с root снова.

в C++ 11, это дополнительная оптимизация, так что вы можете реализовать структуру skiplist, и использовать этот диапазон-вставки Feture в вашей реализации, или вы можете оптимизировать программка в соответствии с вашими сценариями