Сохранение элементов в списке в порядке возрастания

Question

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

Некоторые из идей, которые мне приходят в голову, - это результат: как результат: set (std :: set), но B-дерево необходимо перебалансировать время от времени. b) Сохраните все элементы в списке и отсортируйте список в конце.

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

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

void findItemToInsertAt(std::list<int>& dataSet, int itemToInsert, std::list<int>::iterator& location) 
{ 
    std::list<int>::iterator fromBegin = dataSet.begin(); 
    std::list<int>::iterator fromEnd = dataSet.end() ; 
    // Have two pointers namely end and begin 
    if (!dataSet.empty()) 
     --fromEnd; 

    // Set the location to the beginning, so that if the dataset is empty, it can return the appropriate value 
    location = fromBegin; 
    while (fromBegin != dataSet.end() ) 
    { 
     // If the left pointer points to lesser value, move to the next element 
     if (*fromBegin < itemToInsert) 
     { 
      ++fromBegin; 
      // If the end is greater than the item to be inserted then move to the previous element 
      if (*fromEnd > itemToInsert) 
      { 
       --fromEnd; 
      } 
      else 
      { 
       // We move only if the element to be inserted is greater than the end, so that end points to the 
       // right location 
       if (*fromEnd < itemToInsert) 
       { 
        location = ++fromEnd; 
       } 
       else 
       { 
        location = fromEnd; 
       } 
       break; 
      } 
     } 
     else 
     { 
      location = fromBegin; 
      break; 
     } 
    } 

} 

И вот вызывающий функции

void storeListToResults(const std::list<int>& dataset, std::list<int>& resultset) 
{ 

    std::list<int>::const_iterator curloc; 
    std::list<int>::iterator insertAt; 

    // For each item in the data set, find the location to be inserted into 
    // and insert the item. 
    for (curloc = dataset.begin(); curloc != dataset.end() ; ++curloc) 
    { 
     // Find the iterator to be inserted at 
     findItemToInsertAt(resultset,*curloc,insertAt); 
     // If we have reached the end, then the element to be inserted is at the end 
     if (insertAt == resultset.end()) 
     { 
      resultset.push_back(*curloc); 
     } 
     else if (*insertAt != *curloc) // If the elements do not exist already, then insert it. 
     { 
      resultset.insert(insertAt,*curloc); 
     } 
    } 
} 

Answer 1

С первого взгляда ваш код выглядит так, как будто он выполняет линейный поиск списка, чтобы найти место для вставки элемента. Хотя верно, что std::set придется балансировать свое дерево (я думаю, что это Red-Black Tree), чтобы поддерживать эффективность, скорее всего, он будет делать гораздо более эффективно, чем то, что вы предлагаете.

Answer 2

Я бы отсортировать indivual списки, а затем использовать STL в list::merge для создания списка результатов. Затем, если список является довольно большим, вы можете заплатить за перевод результата в вектор.

Answer 3

Отвечая на поставленный вопрос:

Есть ли эффективный способ сделать то же самое?

Да. Используйте std::set.