是否可以在没有临时存储的情况下进行就地合并？

Question

我只是想,如果我要实现std::inplace_merge它可能看起来像这样:

template <class Bi, class Cmp>
void inplace_merge(Bi first, Bi middle, Bi last, Cmp cmp) {
    if(first != last) {
        typedef typename iterator_traits<Bi>::value_type T;
        typedef typename iterator_traits<Bi>::difference_type Dist;

        const Dist count = distance(first, last);
        if(count != 1) {
            // can I avoid this allocation?
            T *const temp = new T[count];       
            merge(first, middle, middle, last, temp, cmp);      
            copy(temp, temp + count, first);
            delete [] temp;
        }
    }
}

我知道我可以使用现有的实现,但除了重点之外.如果有比我所知的更好的算法,我只是好奇.

我想到这一点的原因是大多数c ++标准库(如果我没记错的话,所有的STL)都允许用户指定执行分配的方式和位置,但如果std::inplace_merge需要按设计分配,似乎没有办法如果这是一个问题,控制它.

我认为答案的一个暗示来自于标准本身的复杂性std::inplace_merge:

复杂性:当有足够的额外内存可用时,(最后 - 第一个) - 1次比较.如果没有可用的附加存储器,则可以使用具有复杂度N log N(其中N等于last-first)的算法.

对我而言,这意味着该算法的已知有效版本需要额外的存储空间.我读得对吗？如果是这样,有没有提到存储应该来自哪里？

Answer 1

有几种已知的就地合并算法,尽管其中一些算法相当复杂.它们工作的一般方式是使用一些数组元素本身作为外部存储空间进行异地合并.我知道Alex Stepanov和Paul McJones的"编程元素"详述了一种算法.

我最近阅读了一篇关于就地合并的文章,名为"实际就地合并",详细介绍了一种用于进行此类合并的相当简单的算法.我以一种接近界面的方式编写了这种算法的实现std::inplace_merge,尽管存在一些差异.也许那里有你可能觉得有用的东西？