将数据插入排序向量的有效方法

Question

排序后

std::vector

，可以使用此代码按顺序插入元素。

template< typename T >
typename std::vector<T>::iterator 
   insert_sorted( std::vector<T> & vec, T const& item )
{
    return vec.insert
        ( 
            std::upper_bound( vec.begin(), vec.end(), item ),
            item 
        );
}

与调用

emplace_back

相比，此代码效率不高。

是否有在排序向量中插入数据的最佳实现

Answer 1

使用摊销分析几乎可以得到同样好的结果。您所做的就是拥有一个包含向量的包含数据结构。您将 push_back 或 emplace_back 放入向量中并假装它是已排序的插入，但事实并非如此。您在内部记录有新的（未排序的）条目。

然后下次有人访问数据时，然后您对整个数据进行排序。

std::sort

对于连续数据非常有用。如果您在下次访问之前有很多已排序的插入，那么这种方法非常有效。无论是分析还是实践。

Answer 2

您展示的代码与

emplace_back

做了不同的事情，比较它们的运行时间没有意义。你不可能变得更好了。