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

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

size_type  size() const                             
{
       return _size;
}

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

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

Как известно, в С++, как и в его предке С, инструкция typdef не создает новых типов, а всего лишь псевдонимы для существующих. И если в слаботипизированном С это не было проблемой, то в строгом С++ это приводит к недоумению, особенно среди новичков, а так же трудноуловимым багам в программе.

В этой статье мы попробуем обойти эту неприятную особенность.