При апдейте на VS2015 словили, что в STL контейнерах не могут быть константые элементы. Почему нельзя?

(Есть вариант QVector или boost::vector если запрет не очень аргументирован)

Здравствуйте, Alexander G, Вы писали:

AG>При апдейте на VS2015 словили, что в STL контейнерах не могут быть константые элементы. Почему нельзя?

GCC тоже не умеет: кривая реализация аллокатора. Он явно вызывает ::operator delete, который определён над void*, но не над const void*.

Из правил для контейнеров обязательность возможности осуществлять присваивание хранимым объектам выкинули, но в требованиях к аллокаторам запрет на неизменяемые объекты оставили.

17.6.3.5 Allocator requirements
...
T any non-const object type

Попытка сделать контейнер для const int с аллокатором для просто int — неопределенное поведение.

PS А ведь студия четко ругается:

The C++ Standard forbids containers of const elements because allocator<const T> is ill-formed.

Здравствуйте, VTT, Вы писали:

VTT>Из правил для контейнеров обязательность возможности осуществлять присваивание хранимым объектам выкинули, но в требованиях к аллокаторам запрет на неизменяемые объекты оставили.
VTT>

17.6.3.5 Allocator requirements
VTT>...
VTT>T any non-const object type

ок, так это с аллокаторами — баг стандарта или фича?

не читал сообщение студии, привык, что такие сообщения малоинформативны

Здравствуйте, VTT, Вы писали:

VTT>Из правил для контейнеров обязательность возможности осуществлять присваивание хранимым объектам выкинули, но в требованиях к аллокаторам запрет на неизменяемые объекты оставили.

Дефект стандарта, или что?

С разбегу не нашёл в списке.

Не знаю, по идее это концептуальная проблема, так как аллакатору для неизменяемого объекта придется вызывать деструктор с использованием const_cast.

Здравствуйте, VTT, Вы писали:

VTT>Не знаю, по идее это концептуальная проблема, так как аллакатору для неизменяемого объекта придется вызывать деструктор с использованием const_cast.

Почему нельзя удалять константные объекты?

Смартпоинтеры на константные объекты вполне же работают.
Ну или деструктор для константного объекта на стеке.

Здравствуйте, VTT, Вы писали:

VTT>PS А ведь студия четко ругается:

Всё равно баг STL студии.
Потому что не может и с аллокатором, который не заморачивается:

struct S { int a; int b;  };

int main(int argc, char *argv[])
{
    boost::container::vector<const S, boost::container::new_allocator<const S> > v1; // ok 
    std::vector<const S, boost::container::new_allocator<const S> > v2; // fails
    return 0;
}

Тут загвоздка в том, что boost::container::new_allocator не соответствует требованиям для аллокаторов контейнеров stl.

Кроме того, в этом деаллокаторе задействован c-style cast:

void deallocate(pointer ptr, size_type) BOOST_NOEXCEPT_OR_NOTHROW
{ ::operator delete((void*)ptr); }

А в этих случаях никакие аллокаторы не задействуются.

Вообще const_cast , который нужен в deallocate для вызова ::operator delete снимал бы константность, которую сам же аллокатор нацепил на указатель после получения неконстантного результата ::operator new.

Здравствуйте, Alexander G, Вы писали:

AG>Вообще const_cast , который нужен в deallocate для вызова ::operator delete снимал бы константность, которую сам же аллокатор нацепил на указатель после получения неконстантного результата ::operator new.

Да вообще, весь std::vector, IMHO, — сплошная ошибка проектирования

E>Да вообще, весь std::vector, IMHO, — сплошная ошибка проектирования
А что с ним не так?

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, Alexander G, Вы писали:

AG>>Вообще const_cast , который нужен в deallocate для вызова ::operator delete снимал бы константность, которую сам же аллокатор нацепил на указатель после получения неконстантного результата ::operator new.

E>Да вообще, весь std::vector, IMHO, — сплошная ошибка проектирования

а можете пояснить? (и то же самое про ваше " IMHO, почти весь std:: -- сплошная ошибка проектирования... " )

Здравствуйте, b0r3d0m, Вы писали:

B>А что с ним не так?

Тут где-то был эпический срач про недостатки STL, там подробно разбиралось.
Если кратко
1) Не было нормальной поддержки move-семантики. Что-бы хоть как-то привинтить, пришлось курочить язык
2) unsigned индекс.
3) Нельзя сделать буфер для коротких массивов на борту объекта
4) Аллокаторы не умеют сообщить массиву реальный размер блока/не умеют его увеличивать без перемещения, если можно (это примерно один и тот же недостаток)

Из вкусовщины, я бы ещё запретил неявное копирование.

В любом случае достижение авторов STL парадоксально. std::list обычно оказывается быстрее std::vector'а

E>1) Не было нормальной поддержки move-семантики. Что-бы хоть как-то привинтить, пришлось курочить язык
Да и ладно. Были всегда оптимизации компиляторов, по крайней мере.

E>2) unsigned индекс.
В чём проблема? Предполагаю, что речь идёт об итерировании с конца в начало, да?

E>3) Нельзя сделать буфер для коротких массивов на борту объекта
Ничего не понял. В смысле, нет возможности выделить память под объекты vector'а на стеке?

E>4) Аллокаторы не умеют сообщить массиву реальный размер блока/не умеют его увеличивать без перемещения, если можно (это примерно один и тот же недостаток)
Что подразумевается под "реальным размером блока"?

E>В любом случае достижение авторов STL парадоксально. std::list обычно оказывается быстрее std::vector'а
На каких операциях?

Здравствуйте, _hum_, Вы писали:

__>а можете пояснить? (и то же самое про ваше " IMHO, почти весь std:: -- сплошная ошибка проектирования... " )

Тут был эпичный срач про критику STL, лучше там

Автор: gid_vvp
Дата: 23.08.06

посмотреть...

Если же за пределами stl смотреть, то, например, в std можно сделать текстовый поток любой хрени, но никак нельзя открыть файл с Unicode-именем...

Здравствуйте, b0r3d0m, Вы писали:

B>Да и ладно. Были всегда оптимизации компиляторов, по крайней мере.
Никогда нельзя было сделать массив некопируемых, но перемещаемых объектов...

E>>2) unsigned индекс.
B>В чём проблема? Предполагаю, что речь идёт об итерировании с конца в начало, да?
Ну в любую сторону. Просто большая опасность переполнения. Индекс же число, он может вычисляться...

E>>3) Нельзя сделать буфер для коротких массивов на борту объекта
B>Ничего не понял. В смысле, нет возможности выделить память под объекты vector'а на стеке?
Да. Что-то вроде http://rsdn.org/forum/cpp/6420663.1

E>>4) Аллокаторы не умеют сообщить массиву реальный размер блока/не умеют его увеличивать без перемещения, если можно (это примерно один и тот же недостаток)
B>Что подразумевается под "реальным размером блока"?
Очень часто, когда я прошу у аллокатора х байт, он, на самом деле, выделяет y, где y > x.
Было бы хорошо, что бы вектор мог утилизировать эту память...
Например, представь себе аллокатор, который на VirtualAlloc работает, и, следовательно, все блоки выравнивает на размер страницы?

B>На каких операциях?
Ну итерация коллекции, например...

E>Ну в любую сторону. Просто большая опасность переполнения. Индекс же число, он может вычисляться...
Что-то я не понял. Большая опасность переполнения у signed индекса? Вы ведь на нём настаиваете.

E>Очень часто, когда я прошу у аллокатора х байт, он, на самом деле, выделяет y, где y > x.
Неспроста ведь, наверное, ему же виднее. Golden ratio, не?

E>Ну итерация коллекции, например...
Итерация по std::list быстрее итерации по std::vector?

Здравствуйте, b0r3d0m, Вы писали:

E>>Да вообще, весь std::vector, IMHO, — сплошная ошибка проектирования
B>А что с ним не так?

Очень многое.
Например, у стека нет метода clear.

Здравствуйте, Erop, Вы писали:

E>Здравствуйте, b0r3d0m, Вы писали:

B>>Да и ладно. Были всегда оптимизации компиляторов, по крайней мере.
E>Никогда нельзя было сделать массив некопируемых, но перемещаемых объектов...

Потому что не было такого понятия в языке в то время, STL тут вообще ни при чем.

E>>>2) unsigned индекс.
B>>В чём проблема? Предполагаю, что речь идёт об итерировании с конца в начало, да?
E>Ну в любую сторону. Просто большая опасность переполнения. Индекс же число, он может вычисляться...

детский сад. Ошибки вычисления индекса одинаково разрушительны и в знаковом, и в беззнаковом случае, если используется [], и одинаково безопасны, если используется at().

E>>>3) Нельзя сделать буфер для коротких массивов на борту объекта
B>>Ничего не понял. В смысле, нет возможности выделить память под объекты vector'а на стеке?
E>Да. Что-то вроде http://rsdn.org/forum/cpp/6420663.1

Это, очевидно, делает все вектора с разным встроенным буфером несовместимыми типами.

E>>>4) Аллокаторы не умеют сообщить массиву реальный размер блока/не умеют его увеличивать без перемещения, если можно (это примерно один и тот же недостаток)
B>>Что подразумевается под "реальным размером блока"?
E>Очень часто, когда я прошу у аллокатора х байт, он, на самом деле, выделяет y, где y > x.
E>Было бы хорошо, что бы вектор мог утилизировать эту память...
E>Например, представь себе аллокатор, который на VirtualAlloc работает, и, следовательно, все блоки выравнивает на размер страницы?

Внезапно:

void reserve( size_type new_cap );
Increase the capacity of the container to a value that's greater or equal to new_cap.

B>>На каких операциях?
E>Ну итерация коллекции, например...
Вот это ты отжёг. Попрыгать по памяти в списке, конечно же, просто-таки на порядок быстрее, чем по линейному вектору.

You will always get what you always got
  If you always do  what you always did

Здравствуйте, b0r3d0m, Вы писали:

B>Что-то я не понял. Большая опасность переполнения у signed индекса? Вы ведь на нём настаиваете.

У беззнакового. На самом деле, где-то рядом с "минусы STL" был не менее эпичный срач signed vs unsigned.
Правда не стоит ещё раз начинать, не прочитав те обсуждения
В конце концов, если уж подходить как пуристы, то надо делать что-то вроде этого: http://rsdn.org/forum/cpp/2933445.1

Автор: Erop
Дата: 29.04.08

, а не unsigned...

Но если тебе unsigned нравится, напиши, например, как УДОБНО устроить итерацию назад группами?

E>>Очень часто, когда я прошу у аллокатора х байт, он, на самом деле, выделяет y, где y > x.
B>Неспроста ведь, наверное, ему же виднее. Golden ratio, не?
Ну просто фрагментация растёт забесплатно и всё...

E>>Ну итерация коллекции, например...
B>Итерация по std::list быстрее итерации по std::vector?
Да. Ну и вообще большинство алгоритмов, которым не нужен произвольных доступ...

Здравствуйте, jazzer, Вы писали:

J>Потому что не было такого понятия в языке в то время, STL тут вообще ни при чем.
Э-э-э? При чём тут язык? Например объект "открытый файл" копировать нельзя, а перемещать можно...

J>детский сад. Ошибки вычисления индекса одинаково разрушительны и в знаковом, и в беззнаковом случае, если используется [], и одинаково безопасны, если используется at().
Это заблуждение. Переполнение может случиться не в самом конце, а где-то по пути ВЫЧИСЛЕНИЙ. at не сломается, но индекс будет не тот
Ну и вообще, проблема не в том, что будет, если случится, а в том, что писать вычисления со знаковыми числами ПРОЩЕ и ошибок будет меньше, так как переполнение НЕ СЛУЧИТСЯ...

J>Это, очевидно, делает все вектора с разным встроенным буфером несовместимыми типами.
Да, и что?
Зачем нужны аллокаторы, если ничего не позволяют? Ни гранулярность аллокаций задать, ни преаллокации использовать и т. д?

E>>Например, представь себе аллокатор, который на VirtualAlloc работает, и, следовательно, все блоки выравнивает на размер страницы?

J>Внезапно:
J>

J>void reserve( size_type new_cap );
J>Increase the capacity of the container to a value that's greater or equal to new_cap.

Внезапно это про другое...

Здравствуйте, Erop, Вы писали:

E>В любом случае достижение авторов STL парадоксально. std::list обычно оказывается быстрее std::vector'а

Вот не правда. В каком месте list быстрее vector?

B>>Что-то я не понял. Большая опасность переполнения у signed индекса? Вы ведь на нём настаиваете.
E>У беззнакового. На самом деле, где-то рядом с "минусы STL" был не менее эпичный срач signed vs unsigned.
У беззнакового большая опасность переполнения? Это как так?
Во-первых, диапазон допустимых положительных значений (т.е. то, с чем мы в большинстве случаев имеем дело, когда говорим об индексах контейнеров) у него вдвое больше, чем у signed-аналога.
Во-вторых, переполнение signed типа является UB, в то время как unsigned -- нет (хотя, конечно, этого всё равно лучше избегать в большинстве ситуаций).

E>Но если тебе unsigned нравится
Мне не то, чтобы он нравится или не нравится, я просто не парюсь по этому поводу.

E>напиши, например, как УДОБНО устроить итерацию назад группами?
Да я уже глянул другой тред, понял, о чём речь идёт.

E>>>Очень часто, когда я прошу у аллокатора х байт, он, на самом деле, выделяет y, где y > x.
B>>Неспроста ведь, наверное, ему же виднее. Golden ratio, не?
E>Ну просто фрагментация растёт забесплатно и всё...
Да, но зато в угоду более опциональному росту. Почему должно быть иначе?

E>>>Ну итерация коллекции, например...
B>>Итерация по std::list быстрее итерации по std::vector?
E>Да. Ну и вообще большинство алгоритмов, которым не нужен произвольных доступ...
А чем вы подкрепляете своё утверждение?

#include <boost/timer/timer.hpp>

#include <list>
#include <vector>

#pragma optimize( "", off )

template <typename T>
void iterate(const T& c)
{
  boost::timer::auto_cpu_timer t;
  for (auto& e : c)
  {

  }
}

#pragma optimize( "", on )

int main()
{
  std::list<int> l;
  for (int i = 0; i < 10000000; ++i)
  {
    l.push_back(i);
  }

  std::vector<int> v;
  for (int i = 0; i < 10000000; ++i)
  {
    v.push_back(i);
  }

  iterate(l);
  iterate(v);
}

На моей системе это дало следующей результат:

0.046063s wall, 0.046875s user + 0.000000s system = 0.046875s CPU (101.8%)
0.000001s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

Visual C++ 11.0 (Visual Studio 2012)

Даже если предположить, что компилятор всё равно что-то соптимизировал, то можно заменить цикл на что-нибудь вроде

for (auto& e : c)
{
  if (e % 1000 == 0)
  {
    std::cout << e << '\n';
  }
}

и всё равно увидеть, что std::vector выигрывает по скорости std::list (впрочем, такой тест уже нельзя назвать чистым, т.к. помимо итерирования по контейнеру здесь присутствует вывод в stdout, время которого может сильно отличаться при каждом вызове).

Здравствуйте, Erop, Вы писали:


E>Тут где-то был эпический срач про недостатки STL, там подробно разбиралось.
E>Если кратко
E>1) Не было нормальной поддержки move-семантики. Что-бы хоть как-то привинтить, пришлось курочить язык
E>2) unsigned индекс.
E>3) Нельзя сделать буфер для коротких массивов на борту объекта
E>4) Аллокаторы не умеют сообщить массиву реальный размер блока/не умеют его увеличивать без перемещения, если можно (это примерно один и тот же недостаток)

У тебя несколько неканонический список претензий. Обычно жалуются на то, что std::vector<int, MyAlloc<int>> и std::vector<int> не являются объектами одного типа.

Здравствуйте, andyp, Вы писали:

A>У тебя несколько неканонический список претензий. Обычно жалуются на то, что std::vector<int, MyAlloc<int>> и std::vector<int> не являются объектами одного типа.

Ну это в новом стандарте отчасти допилили. Теперь можно сделать динамически переключаемый аллокатор, раньше было нельзя, так как у аллокаторов не было состояния...

Здравствуйте, b0r3d0m, Вы писали:

B>У беззнакового большая опасность переполнения? Это как так?
Ну у беззнаковых ЧИСЕЛ в ВЫЧИСЛЕНИЯХ риск переполнения выше, потому, что при верно выбранных разрядностях, участвующие в ВЫЧИСЛЕНИЯХ числа далеки от максимальных значений, но как разрядности не выбирай не уйдёшь далеко от нуля...

B>Во-первых, диапазон допустимых положительных значений (т.е. то, с чем мы в большинстве случаев имеем дело, когда говорим об индексах контейнеров) у него вдвое больше, чем у signed-аналога.

ОБЫЧНО вектора СИЛЬНО меньше допустимого диапазона...
Кроме того, для вычисления индекса можно взять целое подлиннее, если уж 32/16 бит не хватает (64 бита фиг переполнишь всё-таки). Знаковость менять сложнее, чем разрядность, так как увеличение разрядности -- это продвижение.
Фактически, у нас есть размен. Возможность иметь вектора длиннее INT_MAX или иметь знаковый индекс.
IMHO, первая возможность сугубо теоретическая, а второе ограничение -- неудобное...

E>>Но если тебе unsigned нравится
B>Мне не то, чтобы он нравится или не нравится, я просто не парюсь по этому поводу.
Я тоже не парюсь. Меня просто спросили о содержании старого флейма

B>Да, но зато в угоду более опциональному росту. Почему должно быть иначе?
Это не понял. Речь о том, что многим аллокаторам некоторые размеры блоков выделять УДОБНЕЕ, к сожалению аллокаторы в STL не могут сообщать об этом коллекциям...
Это приводит к тому, что память всё равно фактически выделяется, но не используется.

B>А чем вы подкрепляете своё утверждение?
Ну, когда был тот срач, профилировали разные алгоритмы, вроде поиска там или сложения элементов диапазона, и, парадоксальным образом список был быстрее...
Сейчас компиляторы покрутели и может теперь я не прав. Честно говоря лень выяснять, так как STL уже навсегда
Но тогда я был поражён...

B>На моей системе это дало следующей результат:

B>

B>0.046063s wall, 0.046875s user + 0.000000s system = 0.046875s CPU (101.8%)
B>0.000001s wall, 0.000000s user + 0.000000s system = 0.000000s CPU (n/a%)

Ну, очевидно, что итерация вектора и списка не может отличаться на 4 десятичных порядка
Я бы глянул asm...

B>Visual C++ 11.0 (Visual Studio 2012)

B>Даже если предположить, что компилятор всё равно что-то соптимизировал, то <...>впрочем, такой тест уже нельзя назвать чистым, т.к. помимо итерирования по контейнеру здесь присутствует вывод в stdout, время которого может сильно отличаться при каждом вызове).

Это слишком синтетический тест, так как код ничего не делает, и не оптимизируется. Это слишком далеко от реального использования.
Но, IMHO, это всё не особо важно уже. На то были ошибки в проектировании STL тогда, или нет, современное положение дел влияет мало...

Здравствуйте, Erop, Вы писали:

E>2) unsigned индекс.

Ну вообще знаковый индекс в целом неоптимальнее, но, по идее, тип индекса, как и тип указателя, должен быть настраиваем через аллокатор.

Здравствуйте, Alexander G, Вы писали:

AG>Ну вообще знаковый индекс в целом неоптимальнее, но, по идее, тип индекса, как и тип указателя, должен быть настраиваем через аллокатор.

Ну, как вариант. Только по умолчанию всё равно лучше знаковый...

Правда, через механизм частичной специализации, такая возможность есть и сейчас, жаль, что остальной STL на этот тип не смотрит всё равно...
В общем я считаю, что прибитый гвоздями беззнаковый тип индекса -- одна из ошибок проектирования...

Здравствуйте, Alexander G, Вы писали:

AG>Вообще const_cast , который нужен в deallocate для вызова ::operator delete снимал бы константность, которую сам же аллокатор нацепил на указатель после получения неконстантного результата ::operator new.

Ну если копать на самую глубину, то контейнер (и аллокатор) по идее всегда должны внутри работать с не const, а const предоставлять только как внешний интерфейс.
т.е. и vector< char > и vector< char const > должны строится на основе некоторого base_vector< char > и allocator< char >
Тогда 1) нет проблем с const 2) нет дублирования при инстанцировании c const и с не const

Здравствуйте, VTT, Вы писали:

VTT>Тогда 1) нет проблем с const 2) нет дублирования при инстанцировании c const и с не const
3) Есть возможность поддержать ещё и volatile
4) Есть возможность поддержать касты вида vector<const int> -> const vector<int>

Здравствуйте, b0r3d0m, Вы писали:

B>Что-то я не понял. Большая опасность переполнения у signed индекса? Вы ведь на нём настаиваете.

http://rsdn.org/forum/flame.comp/2210458.flat

Автор:
Дата: 12.11.06

http://rsdn.org/forum/flame.comp/4799037.flat

Автор: esil
Дата: 01.07.12

и т. д...