将元素按升序存储在列表中

Question

目标是，我有多个可用元素列表，并且我希望能够以有序方式将所有这些元素存储到结果列表中。

我想到的一些想法是 a) 将结果保留为集合 (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

我会对各个列表进行排序，然后使用 STL 的 list::merge 来创建结果列表。然后，如果列表很大，您可以付费将结果传输到向量。

Answer 2

乍一看，您的代码似乎正在对列表进行线性搜索，以便找到插入项目的位置。虽然 std::set 确实必须平衡其树（我认为它是一个 红黑树）为了保持效率，它很可能会比你建议的更有效。

Answer 3

回答所提出的问题：

有没有一种有效的方法可以做到这一点？

是的。使用std::set。