О деталях и возможностях реализации <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 и не вылечу ли я за границы массива?". Хотя, конечно, последнее не всегда актуально.

Новые блоги и статьи Все статьи Все блоги /
Установка MinGW GCC 16.2 и CMake 8Observer8 10.08.2026 VK Видео: https:/ / vkvideo. ru/ video-240781534_456239017 YouTube: eY5-5PyI9NM Текстовая версия	Неделя из жизни имитационной модели склада: мои кривые руки растут, откуда надо anaschu 10.08.2026 Неделя из жизни имитационной модели склада: как я почти написал неправильную логику и что с этим делать Работаю сейчас над учебно-рабочим проектом: строю в AnyLogic имитационную модель процессов. . .	Калькулятор для расчета родства russiannick 07.08.2026 1. Задача: Создать калькулятор для расчета родства. Родственных связей существует 8 ступеней, такие как: p - отец P - мать q - муж Q - жена b - брат B - сестра s - сын S - дочь	Мир по моей воле kumehtar 07.08.2026 Когда-то кажется, что всё просто. Ты весь такой светлый. Причиняешь добро. Борешься за справедливость в этом тёмном мире. Потом начинаешь замечать одну неприятную вещь. Почти каждый хороший. . .
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .

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