c++ - 按升序存储列表中的元素

Question

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

我想到的一些想法是 a) 将结果保留为一个集合 (std::set)，但 B-tree 需要时不时地重新平衡。 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 )以保持效率，但它可能比你做的更有效率重新提议。