c++ - 以相反的顺序连接两个链表

Question

我有两个列表，我目前正在使用 std::list < size_t > .我们称它们为列表 A 和列表 B。设列表 A 有元素 [1, 2, 3, 4]，列表 B 有元素 [5, 6, 7, 8]。

我想连接两个列表。但是，在我的应用程序中，有八种连接方式。我将描述两种使其最小化的方法:

1. 直接连接 A 和 B。所以列表 C = [1, 2, 3, 4, 5, 6, 7, 8]。
2. 反转列表 A 和 B，然后连接起来。所以列表 C = [4, 3, 2, 1, 8, 7, 6, 5]。

对于第一种情况，我可以使用以下代码 ( source: cppreference ):

std::list <size_t> C; 
C.splice(C.begin(), A); 
C.splice(C.end(), B);

这提供了一个很好的常数时间实现。

对于第二种情况，我必须反转列表，我可以为此目的使用 reverse() (source: cppreference):

A.reverse();
B.reverse();
C_reversed.splice(C_reversed.begin(), A);
C_reversed.splice(C_reversed.end(), B);
std::cout << "C_reversed: " << C_reversed << std::endl;

这很好用，但是，它具有线性时间复杂度。有一个更好的方法吗？我通读了 Stack Overflow: Why does std::list::reverse have O(n) complexity? , 并且明白不能使用 reverse() 来完成.有没有其他方法可以在恒定时间内完成此任务？

---

我的后备选项是维护四个列表，A 和 B 各有两个，这样我就可以在常数时间内连接起来。然而，这会导致额外的空间复杂性。示例如下:

std::list <size_t> A1 = {1, 2, 3, 4};
std::list <size_t> A1_reversed = {4, 3, 2, 1};
std::list <size_t> B1 = {5, 6, 7, 8};
std::list <size_t> B1_reversed = {8, 7, 6, 5};
std::list <size_t> C1;
C1.splice(C1.begin(), A1);
C1.splice(C1.end(), B1);
std::list <size_t> C1_reversed;
std::cout << "C1: "<< C1 <<std::endl;
C1_reversed.splice(C1_reversed.begin(), A1_reversed);
C1_reversed.splice(C1_reversed.end(), B1_reversed);
std::cout << "C1_reversed: "<< C1_reversed <<std::endl;

---

实验代码如下:

  /** Concatenation of two lists **/
#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list< size_t >& list) {
    for (auto &i : list) {
        ostr << " " << i;
    }
    return ostr;
}

int main(int argc, char **argv) {

    /** Initialize **/
    std::list < size_t > A = {1, 2, 3, 4};
    std::list < size_t > B = {5, 6, 7, 8};

    /** A + B **/
    std::list < size_t > C;
    C.splice(C.begin(), A);
    C.splice(C.end(), B);
    std::cout << C << std::endl;

    /** Reverse A + reverse B **/
    A = {1, 2, 3, 4};
    B = {5, 6, 7, 8};
    std::list < size_t > C_reversed;
    A.reverse();
    B.reverse();
    C_reversed.splice(C_reversed.begin(), A);
    C_reversed.splice(C_reversed.end(), B);
    std::cout << C_reversed << std::endl;

    /** Maintaining four lists **/
    std::list <size_t> A1 = {1, 2, 3, 4};
    std::list <size_t> A1_reversed = {4, 3, 2, 1};
    std::list <size_t> B1 = {5, 6, 7, 8};
    std::list <size_t> B1_reversed = {8, 7, 6, 5};
    std::list <size_t> C1;
    C1.splice(C1.begin(), A1);
    C1.splice(C1.end(), B1);
    std::list <size_t> C1_reversed;
    std::cout << "C1: "<< C1 <<std::endl;
    C1_reversed.splice(C1_reversed.begin(), A1_reversed);
    C1_reversed.splice(C1_reversed.end(), B1_reversed);
    std::cout << "C1_reversed: "<< C1_reversed <<std::endl;

    return 0;
}

Answer 1

为了使其成为 O(1)，我们可以扩展 STL::list 类或以其他方式实现类似的接口(interface)。下面是一个开始的例子。 声明: STL::list 的每个功能都可以为 ReversedConCatList 实现，与原始 STL::list 的复杂度相同甚至更好。

template <typename T> 
class ReversedConCatList {  
  public:
    typedef value_type& reference;
    typedef /*implementation-defined: special_iterator*/ iterator; // special_iterator(l1, l2);
    void push_back(T value) {
      b_.emplace_front(value);
    }
    void push_front(T value) {
      a_.push_back(value);
    }
    reference front() {
      return a_.empty() ? b_.back(): a_.back();
    }
    reference back() {
      return b_.empty() ? a_.front() : b_.front();
    }
    iterator begin() noexcept {
      return special_iterator(a_, b_);
    }
    iterator end() noexcept {
      return a.begin().base(); // end of special iterator
    }
    size_type size() const noexcept {
      return a_.size() + b_.size();
    }
    bool empty() const noexcept {
      return a_.empty() && b_.empty();
    }
    // ...
  private:
    std::list<T> a_; // Takes ownership
    std::list<T> b_; // Takes ownership
};

基本上，列表的所有操作都可以在其他情况下使用 ReversedConCatList 来实现，例如 A + reversed(B) 或 reversed(A) + B，只需保留列表是否反转的 bool 标志。甚至更好地使用模板在编译时摆脱标志。

Insight 是列表 API 从头部和尾部具有相同的功能，因此我们能够做到这一点，std::list 可以实现复杂度为 O(1) 的 reverse()，但这会产生合并列表的复杂性非平凡的(目前是 O(1))。