слияние сортированной коллекции с картой

Question

У меня есть (скажем, три) сортированные коллекции ключевых значений. Самый простой способ их слияния - использовать std :: map. Просто. Однако, поскольку сортируются, стоит подумать о том, чтобы перебирать одну коллекцию и вставлять пару из второй коллекции в нужном месте, не используя map :: insert, которая всегда будет иметь O (n log n). Поэтому мне кажется, что лучше всего для этой ситуации будет использовать std :: list с std :: pair. Я также рассмотрел использование std :: vector с некоторыми ключами для сопоставления индексов и слиянием коллекций с использованием нового вектора, однако это будет сложнее.

Этот способ мышления имеет смысл? Или есть эффективный способ использования карты в такой задаче.

Thank you.

РЕДАКТИРОВАТЬ:

Пример:

{{60: 1}, {{75: 4},  {{100: 3}, 
{70: 5},  {80: 2},  {120: 9}, 
{80: 4}  {85: 4}}  {140: 7}} 
{90: 9}} 

Если это поможет, общая схема для ввода является:

{{offset: random0}, 
{offset + 1 * k: random1}, 
{offset + 2 * k: random2}, 
{offset + 3 * k: random3}, 
{offset + 4 * k: random4}, ... } 

и {offset: random0} означает, что для каждого элемента из <offset, offset + 1 * k) значения диапазона равен random0.

Вывод должен быть:

{{60: 1}, 
{70: 5}, 
{75: 9}, //{70: 5} + {75: 4} 
{80: 6}, //{80: 4} + {80: 2} 
{85: 8}, //{80: 4} + {85: 4} 
{90: 9}, 
{100: 3}, 
{120: 9}, 
{140: 7}} 

Наконец, я считаю, используя вектор:

int upper_bound = 200; 
vector<unsigned int> v(upper_bound, 0); 

Затем перебирать каждую карту, и приращение надлежащего элемента в векторе. Если ключ превысит границу, я буду просто изменять размер вектора. Затем я уменьшу вектор от элементов, которые равны 0.

Answer 1

Вы можете просто использовать map, предоставляя вам собственный класс Compare, когда вы его объявите (третий параметр определения шаблона). Затем вы можете свободно использовать range insert и прочитать свои упорядоченные элементы с помощью правильных итераторов (знаете, методы begin, end).

Внутреннее представление map неявно упорядочено по контракту, поэтому вам не нужно заботиться о том, как вы вставляете свои элементы, вместо этого вы должны предоставить действительную функцию для их сравнения.

Действительно, ваши коллекции сортируются, но я предполагаю, что они не совмещенной отсортирован (я имею в виду, коллекция C1 содержит элементы, которые разбросаны по всему в коллекции C2, никаких гарантий, что они не будут размещены contiguosly), это ?.