Хватай перрон, мешки отходят!
Вот, оказывается, какие шедевры стандартной библиотеки C++ только и ждут своего часа, чтобы о них узнал тот несчастный, что верит в здравый смысл:
std::list::size() -- Returns the size of the list. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the list. If you wish to test whether a list is empty, you should write L.empty() rather than L.size() == 0.
И я вам даже больше скажу, в GNU libstdc++ она и правда O(N)! Причем узнал я это чисто случайно -- только потому, что эта функция работала ровно половину времени всей программы, хотя планировалось, что её роль будет скромно равна одной десятой наносекунды. Спасибо, блять, товарищи Страуструпы и компания, за такую подставу. Вы вообще знаете, в скольких местах и для списков каких размеров я использовал эту функцию много лет, наивно полагая, что она O(1)?! Вы хотели 4 байта на список сэкономить, что ли? Или же гениальные generic-концепции сделали невозможным поддерживать в правильном состоянии счетчик числа элементов? Или же вы просто из принципа решили такую подставу учинить? Мне никогда особенно не нравился STL, но, тем не менее, подобного я от него не ожидал.
std::list::size() -- Returns the size of the list. Note: you should not assume that this function is constant time. It is permitted to be O(N), where N is the number of elements in the list. If you wish to test whether a list is empty, you should write L.empty() rather than L.size() == 0.
И я вам даже больше скажу, в GNU libstdc++ она и правда O(N)! Причем узнал я это чисто случайно -- только потому, что эта функция работала ровно половину времени всей программы, хотя планировалось, что её роль будет скромно равна одной десятой наносекунды. Спасибо, блять, товарищи Страуструпы и компания, за такую подставу. Вы вообще знаете, в скольких местах и для списков каких размеров я использовал эту функцию много лет, наивно полагая, что она O(1)?! Вы хотели 4 байта на список сэкономить, что ли? Или же гениальные generic-концепции сделали невозможным поддерживать в правильном состоянии счетчик числа элементов? Или же вы просто из принципа решили такую подставу учинить? Мне никогда особенно не нравился STL, но, тем не менее, подобного я от него не ожидал.