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

Question

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

是否可以在常数时间内拼接两个 std::lists 并保留每个的完整列表？
我的理解是，可以通过创建我自己的列表数据结构并使用类似于以下（伪代码）的函数来实现此功能：
```
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/other 库不是一个选项）

Answer 1

是的，std::list::splice 就是这样工作的（复杂度为 O(1)）(1):

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

假设一个抽象的单链表，你会做
```
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;
```
在任何一种情况下，都不会复制任何数据，您只是在这里和那里交换指针。

Answer 2

(以下为伪代码)

拼接即交织：

new_list = list1[0], list2[0], list1[1], list2[1], ...

连接是将两个列表连接在一起：

new_list = list1, list2

（以下是未经测试的（略微伪造的）代码）

拼接：

List splice(List list1, List list2){
  List<stuff> things ;
  List<stuff> * small_list = list1.size() > list2.size() ? &list2 : &list1 ;
  List<stuff> * big_list = list1.size() > list2.size() ? &list1 : &list2 ;
  for(int i = 0 ; i < small_list->size() ; i++ ){
    things << list1[i] << list2[i] ;
  }
  for(int i = small_list->size() ; i < big_list->size()){
    things << (*big_list)[i] ;
  }
  return things ;
}

很确定您必须在 return 值和参数中定义您的列表包含的内容（或使用多态性模板，这现在超出了我的范围）

免责声明：我被 ruby 宠坏了，忘记了这是否是有效的 c++...

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

Splicing full list in constant time

c++

list

stdlist