c++ - 在恒定时间内拼接完整列表

Question

我试图在恒定时间内拼接(连接)两个完整的 std::lists。从阅读文档和其他问题( How to do range splice in constant time with std::forward_list? )，我有两个澄清问题:

1. 是否可以在常数时间内拼接两个 std::lists 并保留每个的完整列表？

2. 我的理解是，可以通过创建我自己的列表数据结构并使用类似于以下(伪代码)的函数来实现此功能:

   List joinLists(List list1, List list2) {
   
     list1->tail = list2->head;
   
     list1->tail = list2->tail;
   
     return list1;
   
   }
   

这是真的吗？如果没有，如果有人可以帮助我了解这里发生的事情，我将不胜感激。我觉得我错过了什么..

我正在使用的代码在这里:

 auto simple_sorter = [this, numCores](std::vector<std::vector<std::list<unsigned int>>>& buckets_small_, std::vector<std::list<unsigned int>>& buckets_large_, std::vector<bool>& finished_, unsigned int range_low, unsigned int range_high, int thread_number)
{
    //.. irrelevant

    //Combine small buckets into single large bucket per thread
    for(unsigned int i = 0; i < numCores; ++i) {
        std::list<unsigned int> list1 = buckets_large_[thread_number];
        list1.splice(list1.end(), buckets_small_[i][thread_number]);

    //...
};

(注意:Boost/其他库不是一个选项)

Answer 1

1. 是的，std::list::splice 以这种方式工作(复杂度为 O(1))(1) :

No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.

1. 假设一个抽象的单链表，你会这样做

   list1->back->next = list2->front;
   list1->size += list2->size;
   

   对于双链表，你也可以这样做

   list2->front->prev = list1->back;
   

   如果你想在 list1 的第 n 元素之后插入 list2 的元素，你需要找到那个元素，然后执行同样的事情

   element->next = list2->front;        
   //for a double-linked list:
   list2->front->prev = element;
   

   无论哪种情况，都不会复制任何数据，您只需在这里和那里交换指针。