В чем разница между SGI slist и C ++ 11 forward_list?

Question

И SGI slist, и C ++ 11 std::forward_list кажутся мне идентичными, если только я что-то не пропустил; оба реализуют односвязный список.

Я полагаю, что есть разница, поскольку стандартный комитет C ++ не принял список имен и вместо этого выбрал новое имя forward_list, когда они добавили контейнер в стандартную библиотеку для C ++ 0x.

Answer 1

Одно существенное отличие состоит в том, что std::forward_list не имеет функции-члена size(), тогда как sgi::slist - нет. Мотивация для этого состоит в том, что O (N) size() было проблематичным. N2543 содержит более подробную информацию о проектных решениях для forward_list.

Обновление:

Недавно у меня было хорошее оправдание, чтобы присмотреться к этой теме. slist также имеет другие функции-члены, о которых можно подумать: O (1), но на самом деле O (N). К ним относятся:

iterator previous(iterator pos);
const_iterator previous(const_iterator pos) const;
iterator insert(iterator pos, const value_type& x);
iterator erase(iterator pos);
void splice(iterator position, slist& x);
void splice(iterator position, slist& x, iterator i);

Короче говоря, если вы не очень осторожны, вы можете столкнуться со значительными проблемами производительности, используя slist. Использование std::forward_list вместо этого гарантирует, что вы получите ожидаемую производительность O (1) из своего односвязного списка.

Answer 2

Проще говоря, sgi :: slist и forward_list очень похожи.

Различия в том, что forward_list не имеет функции-члена size (), которая включена в sgi :: slist, а forward_list включает функцию-член emplace_after, которая не включена в sgi :: slist. Кроме того, forward_list не предоставляет функции вставки и удаления, как это делает sgi :: slist.

Если вы знаете о каких-либо других различиях, пожалуйста, не стесняйтесь упоминать их.

Answer 3

Я недавно столкнулся с другим отличием. Метод splice_after имеет другой интерфейс и другое поведение.

1) forward_list Требуется, чтобы вы передавали контейнер, из которого вы перемещаетесь, в качестве второго аргумента:

void splice_after( const_iterator pos, forward_list& other,
                   const_iterator first, const_iterator last );

SLIST:

void splice_after(iterator pos, iterator before_first, iterator before_last)

Это похоже на перегрузки.

2) Специально для упомянутой выше перегрузки: последний итератор интерпретируется по-разному! Где slist перемещает диапазон [before_first + 1, before_last + 1>, forward_list перемещает диапазон . Итак, при преобразовании кода (так как slist устарел в GCC, например), обязательно используйте: last = before_last + 1.