Сращивание полного списка за постоянное время

Я пытаюсь соединить (объединить) два полных списка std::list за постоянное время. Из чтения документации и других вопросов (Как выполнять объединение диапазонов в постоянное время с помощью std::forward_list?), у меня есть два уточняющих вопроса:

  1. Можно ли соединить два списка std::list за постоянное время и сохранить полный список каждого из них?

  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/другие библиотеки не подходят)


c++ list stdlist
person qwerty3    schedule 14.10.2015    source источник
comment
splice — деструктивная операция — списки физически объединяются. Вы не можете объединять списки неразрушающим образом за постоянное время.   -  person molbdnilo    schedule 14.10.2015

Ответы (2)


arrow_upward
2
arrow_downward

  1. Да, и std::list::splice работает таким образом (имеет сложность O(1))(1)< /а>:

Никакие элементы не копируются и не перемещаются, перенаправляются только внутренние указатели узлов списка.

  1. Предполагая абстрактный односвязный список, вы бы сделали

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

    Для двусвязного списка вы также должны сделать

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

    Если вы хотите вставить элементы list2 после nth элемента list1, вам нужно будет найти этот элемент и сделать то же самое.

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

    В любом случае данные не копируются, вы просто меняете местами указатели.

person SingerOfTheFall    schedule 14.10.2015
comment
Это то, о чем я думал. Однако код, который я включил, работает в линейном времени. Согласно документации std::list::splice, он выполняется за постоянное время в любом из следующих случаев: void splice (const_iterator position, list& x); void splice (const_iterator position, list&& x); Я что-то упустил в своем коде выше? Я подумываю просто создать свой собственный список, чтобы получить эту функциональность - person qwerty3; 15.10.2015
comment
@qwerty3, копирование списков - это O(n), так что я думаю, что эта строка работает медленно, а не сращивается: std::list<unsigned int> list1 = buckets_large_[thread_number]; - person SingerOfTheFall; 15.10.2015
comment
Я пропустил это!! Правильно ли я понимаю: list1.splice(buckets_large_[thread_number].end(), Buckets_small_[i][thread_number]); не вызовет конструктор копирования? Спасибо за вашу помощь. - person qwerty3; 15.10.2015
comment
@qwerty3, да, так должно быть хорошо - person SingerOfTheFall; 15.10.2015

arrow_upward
-1
arrow_downward

(Ниже псевдокод)

Сплайсинг – это переплетение:

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 ;
}

Почти уверен, что вам нужно определить, что ваш список содержит в возвращаемом значении и аргументах (или использовать шаблоны для полиморфизма, которые сейчас вне меня)

Отказ от ответственности: я был испорчен рубином и забыл, действительно ли это С++...

person MarkJL    schedule 14.10.2015
comment
Вы ошибаетесь в том, что делает std::list::splice. - person Sneftel; 14.10.2015
comment
Да, я был, когда писал это. Это плохое имя для этой функции. - person MarkJL; 14.10.2015
comment
Это стандартное название деструктивной вставки элементов в связанный список. Я не могу придумать ни одного языка, который бы называл чередование сплайсингом. - person Sneftel; 14.10.2015
comment
Английский. Это была моя ошибка. - person MarkJL; 15.10.2015