Неприятная особенность std::list, о которой не все знают

Односвзязный список — это фундаментальная структура данных, о которой все знают и повсеместно используют. Все знают почему и в каких случаях он эффективнее вектора, какие операции имеют линейную сложность, а какие — константную…

Хотя постойте, знаете ли вы какова соложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»

size_type  size() const                             
{
       return _size;
}

Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.

Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.

Вот так выглядит реализация этой функции в gcc 4.x:

/**  Returns the number of elements in the %list.  */ 
size_type                                             
size() const                                          
{ return std::distance(begin(), end()); }             

Если не верите — пойдите проверьте в своем дистрибутиве.

Что мы здесь видим? Чтобы выполнисть такую тривиальную операцию, как получение размера, наш список будет выполнять полный проход с подсчетом!

Это значит, что если вы дергаете эту функцию в цикле, проходя по списку, то сложность вашего алгоритма автоматически умножается на N.

for (std::list <int>::const_iterator I = my_list.begin (); I != my_list.end (); ++I)
{
     if (*I > my_list.size ())
     {
          std::cout << "Haha! "<< *I << std::endl;
     }
}

Вместо, казалось бы очевидного, O(N), мы получим здесь O(N^2). Хорошо если в списке 100 элементов. А что если 1 000 000?

Это так же значит, что вызов size () — небезопасен в многопоточной среде.

std::list <int> my_list;

// Thread 1
void thread1_proc ()
{
     while (!stop)
     {
          std::cout << "List size: " << my_list.size () << std::endl; 
     }
}

// Thread 2
void thread2_proc ()
{
       while (!stop) 
      {
             int n = rand ()
             my_list.push_back (n);
             
             if (n % 2)
                   my_list.pop_front ();
      }
}

Имеем серьезный риск получить крэш в первом потоке.

Это так же значит, что

• Для сравнения двух списков, нам всегда придется выполнять полный проход, вместо того, чтобы тривиальным сравнением размеров отсечь 90% случаев.
• Менее эффективный resize. Здесь мы имеем два случая
  1. Уменьшение размера. Если размер списка нам известен (читай доступен за O(1)), мы можем решить, начинать нам проход с начала или с конца в зависимости от того, удаляем мы несколько элементов в конце или наоборот оставляем несколько в начале. В реализации GNU это сделать невозможно.
  2. Увеличение размера. Если размер списка нам известен, нам достаточно просто добавить недостающие елементы. В реализации GNU нам придется всегда делать полный проход по списку.
• Наверное еще что-то, кто знает, подскажите.

Так что же заставило программистов GNU реализовать список таким образом?

Оказывается, отсутствие необходимости поддерживать внутреннюю переменную _size позволяет реализовать splice за O(1), иначе было бы O(N) для худшего случая.

splice — это операция переноса последовательных элементов из одного списка в другой. Не имея необходимости подсчитывать новые размеры списков, нам достаточно «переключить» указатели с одних узлов на другие, т.е. за константное время.

Именя же внутреннюю переменную _size, нам бы пришлось посчитать сколько элементов мы переносим и соответсвенно обновить ее в обоих списках.

Вот такая вот причина. Кстати, как часто вы пользуетесь это операцией? А всеми вышеперечисленными?

Вобщем будте осторожнее. И еще имейте в виду, что в других реализациях STL переменная _size есть и size() соответственно работает за O(1). Так что будьте дважды осторожны, если вы собираете свой проэкт с разными реализациями STL на разных платформах.

На сем раскланиваюсь. Простите за ботанический пост в пятницу.

Автор: Gunnar