Односвзязный список — это фундаментальная структура данных, о которой все знают и повсеместно используют. Все знают почему и в каких случаях он эффективнее вектора, какие операции имеют линейную сложность, а какие — константную…
Хотя постойте, знаете ли вы какова соложность функции size ()?
«Конечно же я знаю — О(1)!», ответят многие из вас, «Что может быть проще?»
size_type size() const
{
return _size;
}
Тривиально, эффективно и безопасно, не так ли?
Я бы реализовал эту функцию именно так, большинство из вас сделали бы тоже самое.
Однако, те, кто писал реализацию GNU STL, другого мнения на этот счет.
Читать полностью »
