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

Question

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

Некоторые идеи, которые приходят к моемупомните: а) Сохраняйте результат как набор (std :: set), но 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 придется сбалансировать свое дерево (я думаю, что это Красно-черное дерево ), чтобы поддерживать эффективность, но есть вероятность, что оно будет работать намного эффективнее, чем то, что вы предлагая.

Answer 2

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

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

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

Answer 3

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