О деталях и возможностях реализации <vector>

@Fulcrum_013 · Регистрация: 14.12.2014

Студворк — интернет-сервис помощи студентам

Комментарий модератора

Эта тема выделена из темы: Работа с векторами без использования STL и библиотеки <vector>

Сообщение от hoggy

если он не будет защищен внутренними проверками.
я б такую халтуру вообще бы не принял.

Ну это уже в зависимости от зависимости. Примерно в 50% случаев внутренняя проверка только дает оверхед.
из кода AnsiString (той которая в комплекте C++ Builder)

C++
1
2
3
4
5
char operator [](const int idx) const
    {
      ThrowIfOutOfRange(idx); // Should Range-checking be optional to avoid overhead ??
      return Data[idx];
   }

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

C++
1
2
3
4
5
6
7
char operator [](const int idx) const
    {
#ifdef __DEBUG__
      ThrowIfOutOfRange(idx);
#endif
      return Data[idx];
   }

@Renji · 08.04.2016, 20:09

Сообщение от Fulcrum_013

да точно внесен. Потому как вот так останавливается.

Не внесен он никуда. Просто, std::runtime_error - наследник std::exception, а std::exception (и всех его наследников) велено ловить силами программы. Про "Сишные строки" же в catch секции ничего не сказано, так что они летят к отладчику.

@Fulcrum_013 · 08.04.2016, 20:18 **[ТС]**

Сообщение от Eldies

Внезапно, стандартных контейнеров для этого вполне достаточно.

Геморойно вся эта байда. Проще один раз изобрести список с константным временем удаления по значению элемента, пусть даже и завязанный так или иначе на элемент. Особенно если с расчетом на реюзание элементов. т.е. "удаленные" отдыхают в отдельном списочке пока не понадобятся, а физически распределяются страницами. Во всяком случае для тех кто могут интенсивно добавляться/удаляться.
Опять же это в реалтаймовой части. В части редактора и списков с O(n) временем удаления, а тем более с O(log(n)) будет выше крыши.

Добавлено через 1 минуту

Сообщение от hoggy

казалось бы: и при чем тут stl?

Ну или msvc в связке с stl екскепшинами

@Renji · 08.04.2016, 20:19

Сообщение от Fulcrum_013

т.е. "удаленные" отдыхают в отдельном списочке пока не понадобятся, а физически распределяются страницами. Во всяком случае для тех кто могут интенсивно добавляться/удаляться.

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

@Fulcrum_013 · 08.04.2016, 20:36 **[ТС]**

Сообщение от Renji

Второй аргумент std::list для подобного выпендрежа и предназначен.

Не хватало еще чтобы списки выделяли память под элементы. Не его списка забота откуда элемент взялся, куда элемент после удаления идет, и в какой список еще его потом всунут. тут им через перегрузку операторов new/delete действовать надо.

@Renji · 08.04.2016, 20:38

Сообщение от Fulcrum_013

Не хватало еще чтобы списки выделяли память под элементы.

А он и не выделяет. Он использует выделятор переданный вторым аргументом.

@hoggy · 08.04.2016, 20:45

Сообщение от Fulcrum_013

Ну или msvc в связке с stl екскепшинами

казалось бы, при чем тут msvc?

@DeadPenguin · 08.04.2016, 20:46

Не по теме:

hoggy, Renji, бросьте вы эти глупости, вы же видите, что перед вами какой-то неадекват. Человек не то что не понимает, как STL работает, так ещё и переизобретает велосипеды с адовой скоростью. А ещё (что и неудивительно в силу вышеперечисленного) он лучше всех вас знает, как писать ПРАВИЛЬНЫЙ код, как работает дебаггер и зачем нужны исключения.

@hoggy · 08.04.2016, 20:54

Не по теме:

Сообщение от DeadPenguin

бросьте вы эти глупости, вы же видите, что перед вами какой-то неадекват.

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

@Fulcrum_013 · 08.04.2016, 21:10 **[ТС]**

Сообщение от Renji

А он и не выделяет. Он использует выделятор переданный вторым аргументом

То я знаю. Только толка от этого как с козла молока. Потому как выделятся они будут совсем не выделятором списка а на стороне. И удаляться тоже. т.е. смысл - вызвал delete он из всех списков выбросился, и в список свободных этого типа ушел. вызвали new - дернули из списка свободных, поместили в какие нужно списки. При этом общее количество очень быстро устаканится на каком то числе. Самый главный вопрос утрясти все это с наследованием и динамическим полиморфизмом, потому как в списках отдыха они естественно должны по типам сидеть, а пихать каждому указатель на список в который его отправлять на отдых тоже не есть очень карашо, так же как и виртуальную функцию возвращающую статик в каждый копипастить . млин лучше бы оператор __classid стандартизировали, и остальную rtti чем лисапеды стандартизировать из серии лаб первого семестра, причем еще и превращающих текст в говнокод.
Лисапед это таки очень многовариантная high-tech штука, на которую патенты выдают не раз в 10 лет как на колесо, и не раз в год как на гусеницу, а не реже раза в месяц.

@Renji · 08.04.2016, 21:32

Сообщение от Fulcrum_013

То я знаю. Только толка от этого как с козла молока. Потому как выделятся они будут совсем не выделятором списка а на стороне. И удаляться тоже. т.е. смысл - вызвал delete он из всех списков выбросился, и в список свободных этого типа ушел.

Тогда действительно перегрузите operator new/operator delete для конкретного типа. Кто-то мешает что ли?

Сообщение от Fulcrum_013

млин лучше бы оператор __classid стандартизировали

typeid в стандарте еще с прошлого века.

@Fulcrum_013 · 08.04.2016, 21:54 **[ТС]**

Сообщение от Renji

Кто-то мешает что ли?

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

Сообщение от Renji

typeid в стандарте еще с прошлого века.

а вот так этот typeid умеет:

C++
1
FreeLists[__classid(this)]->Add(this);

Ну а чтобы из списка по указателю на элемент ремувить за O(1) элемент должен быть на список завязан. т.е. опять STL в пролете.

@Renji · 08.04.2016, 22:08

Сообщение от Fulcrum_013

Да нет. только вот чтобы из списка за O(1) ремувится нужно чтобы элемент был на список завязан.

Делается через сохранение в элементе итератора на узел списка. Хотя да, оптимальней было бы отнаследоваться от абстрактного list_node.

Сообщение от Fulcrum_013

а вот так этот typeid умеет:

Умеет. Про ассоциативные массивы слышали?

@Fulcrum_013 · 08.04.2016, 22:11 **[ТС]**

Сообщение от Renji

Про ассоциативные массивы слышали?

а за O[1]?

Добавлено через 1 минуту
Неужели компилятору так трудно положить в VMT ее порядковый номер и по оператору его возвращать?

@Renji · 08.04.2016, 22:12

Сообщение от Fulcrum_013

а за O[1]?

А за сколько по вашему std::unordered_map работает?

@Fulcrum_013 · 08.04.2016, 22:13 **[ТС]**

Сообщение от Renji

А за сколько по вашему std::unordered_map работает?

O(log(n)) не быстрее однозначно.

@Renji · 08.04.2016, 22:16

Сообщение от Fulcrum_013

O(log(n)) не быстрее однозначно.

Значит, идите курить маны. Оно на хеш-таблицах, так что в 99% случаев работает за константное время. Еще 1% на феерических неудачников, словивших лбом фантастическое число коллизий.

@Fulcrum_013 · 08.04.2016, 22:20 **[ТС]**

Сообщение от Renji

Оно на хеш-таблицах, так что в 99% случаев работает за константное время.

Время вычисления хеша? Время сравнения? константное время тоже понятие растяжимое 1e1024 тоже константа.
Lists[__classid(this)] работает за нулевое время. ни одного сравнения. без всяких коллизий

@Renji · 08.04.2016, 22:27

Сообщение от Fulcrum_013

Время вычисления хеша? Время сравнения? константное время тоже понятие растяжимое 1e1024 тоже константа.

"Вычисляется" через typeid(*this).hash_code(). Если авторы компилятора не совсем идиоты, то очевидно что hash_code тупо возвращает вбитую на стадии компиляции константу.

@Fulcrum_013 · 08.04.2016, 22:41 **[ТС]**

Сообщение от Renji

Если авторы компилятора не совсем идиоты, то очевидно что hash_code тупо возвращает вбитую на стадии компиляции константу

Которая потом в этом унордеред мап сравнивается с каждым насколько понимаю.

@Renji · 08.04.2016, 23:11

Сообщение от Fulcrum_013

Которая потом в этом унордеред мап сравнивается с каждым насколько понимаю.

Гугл, "хеш-таблица". Ни с чем там хеш не сравнивается, он используется как индекс в хеш-таблице (константное время). После чего из таблицы извлекается список всех элементов с идентичным хешем. В нормальных условиях это полтора элемента. Вот у этих полутора элементов да, ключи сравниваются с образцом. При этом пихать в такой мап можно любые значения, не задаваясь вопросом "а не окажется ли __classid равным over 9000 и не вылечу ли я за границы массива?". Хотя, конечно, последнее не всегда актуально.

Новые блоги и статьи Все статьи Все блоги /
сукцессия 29. Переход от одних деревьев на другие делать более или менее вероятностным? anaschu 12.07.2026 Насколько смена типов микоризы — исключительное событие в двухвековой сукцессии? Оценка вероятности в пространстве параметров В текущей версии модели успешно реализован ключевой механизм. . .	сукцессия 27. Думаю, как переделывать уже написанную статью с планами на сукцессию. anaschu 12.07.2026 Анализ соответствия модели требованиям Реализованные компоненты: Механизм закисления почвы через протонную помпу Конкуренция между типами микориз pH как триггер сукцессии C/ P соотношение. . .	Сукцессия 26. Мат модель создана. anaschu 12.07.2026 Модель смены растительных сукцессий посредством управления грибами работает внутри небольшой ячейки почвы, восстанавливающейся после пожара, где ненадолго бывшее царство хвойных снова захватили. . .	Решил проблему с ошибкой пагинации сообщений с сервера на алгоритме обхода дерева "Эстафета хвоста". Hrethgir 12.07.2026 Проблема была в том, что удалялась именно новая кнопка, а не старая. Ни один ИИ не обнаружил это, а сам я смог только когда с работой стало попроще и когда заставил работать будущее автономное. . .
сукцессия 25. Хронология ошибок anaschu 12.07.2026 # От 50-тонного гриба до устойчивого леса: хроника ошибок при построении модели вековой сукцессии микоризы ## О чём эта статья В процессе построения ОДУ-модели (система дифференциальных. . .	сукцессия 24. Промежуточное общее описание модели anaschu 12.07.2026 Хендофф: модель АМ→ЭКМ сукцессии микоризы (ризосфера, 50 лет) Содержание проекта Симуляция вековой (50 лет) экологической сукцессии в почве леса Основные участники: АМ-гриб, ЭКМ-гриб,. . .	сукцессия 23. Более физиологичная физиология, более экологичная экология, более диффурные диффуры. anaschu 12.07.2026 Что реально нашли и починили за эти 5 часов Правило Линдемана (КПД конверсии сахара в тело, kEff) — раньше 100% полученного углерода шло прямо в биомассу гриба; теперь только kEff=0. 5 (после. . .	сукцессия 22. От артефактов к физиологии: калибровка агентной модели грибной сукцессии для воспроизведения сезонной динамики и pH-плато anaschu 11.07.2026 Аннотация В данной работе представлена калибровка агентной модели динамики грибных сообществ (fungal-succession), направленная на устранение нефизичных артефактов (коллапс биомассы, мгновенное. . .

@DeadPenguin
	08.04.2016, 20:46
	Не по теме: hoggy, Renji, бросьте вы эти глупости, вы же видите, что перед вами какой-то неадекват. Человек не то что не понимает, как STL работает, так ещё и переизобретает велосипеды с адовой скоростью. А ещё (что и неудивительно в силу вышеперечисленного) он лучше всех вас знает, как писать ПРАВИЛЬНЫЙ код, как работает дебаггер и зачем нужны исключения. 0