Решил написать хотя бы похожий на класс вектор свой класс

Хочется узнать, что нужно еще сделать, чтобы метод erase() был похож на erase() из вектора.
Просто,работая с деревом(тема)
При замене на свой вектор появляются многочисленные ошибки памяти(bad_alloc и другие)
erase

конструктор копировщик



Это сообщение отредактировал(а) toxx - 1.4.2010, 17:47

что делает твой метод erase я так и не понял, а конструктор копирования вроде правильный

По идее должен удалять к-й элемент массива, нумерация 1 2 ...

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

ИванМ
Ну я перекопировал элементы старого массива 
потом уменьшил размерность старого массива

И перекопирую уже в новый
Может быть так лучше будет, с точки зрения вашего совета?

Чето намудрил с operator delete он отказывается удалять )

Это сообщение отредактировал(а) toxx - 31.3.2010, 20:39

toxx, ты перекопировал элементы массива V из объекта buf  в объект this странным кривым образом, а потом еще вдобавок удалил весь массив V объекта this и заново его создал. зачем тогда вообще предыдущая операция была нужна?

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

и это что означает? delete это операция, применимая к указателю, а не значению. и к нулю твой тип приравнять нельзя. 

ой, понял что вы имеете ввиду только со 2го раза, вот сделал вродебы


Да, вот с этим


проблема, щас переделываю...

toxx, нет, вы так ничего и не поняли. Остальной код вы сами писали? Странно, если сами.

Все писал сам, в книге только структура дана была и конструктор(не копировщик).
Я просто этим первый раз занимаюсь, отсюда такие проблемы.
может быть вы имели ввиду вот эту строчку:

я уже не знаю почему я не правильно вас понял...

Это сообщение отредактировал(а) toxx - 31.3.2010, 23:07

Давайте я вам напишу алгоритм по шагам.
1 пункт у вас правильный: создаете копию этого объекта this.

2 пункт. Сдвигаете элементы созданного вектора buf влево, начиная с нужного символа (не забывая, что нельзя выходить за границу массива, это у вас не предусмотрено)
3 пункт. Удаляете массив вектора this и создаете его заново, с кол-вом элементов меньшим на единицу
можно как у вас

4 пункт. Копируете элементы из измененного вектора buf в массив вектора this, исключая последний элемент в buf
Вот и все. А у вас там каша какая-то

Я вродебы таким вот образом скопировал элементы buf в массив V( как я понял V, это и есть this?)


Или нужно писать вместо моего копирования

вот это




Это сообщение отредактировал(а) toxx - 1.4.2010, 16:17

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

Добавил условие выхода за границу массива

В итоге должно быть что-то такое?


Это сообщение отредактировал(а) toxx - 1.4.2010, 16:55

все гораздо проще. на этом этапе можно обойтись с одним объектом - buf
просто проходите по элементам buf по циклу начиная с k и заканчивая n-2
и приравниваете текущей элемент следующему
и все

Вот что получил функция значительно уменьшилась...


Это сообщение отредактировал(а) toxx - 1.4.2010, 17:11

ИванМ
Первый раз когда я писал предыдущее своё сообщение я так вас и понял, но 
потом подумал может быть вы опять не это от меня хотите и увидел, что
проще это с одним циклом for...

А вот еще метод resize(int) у вектора он 
1.перевыделяет количество памяти массива на нужную?
2.и копирует все элементы предыдущего массива и если размер больше он лишние элементы зануляет?(если размер больше предыдущего массива)


Это сообщение отредактировал(а) toxx - 1.4.2010, 18:03

да


это зависит от разработчика
самое оптимально это да, занулить

ИванМ


вот этого будет достаточно?

Это сообщение отредактировал(а) toxx - 1.4.2010, 18:05

toxx, нет, надо еще сохранить элементы, которые были до этого, меньшие k

Вот, протестировал вроде бы работает.

toxx, да, вроде правильно.

ИванМ
Спасибо за подсказки.

toxx, вообще-то твой код метода resize() довольно замысловат и далеко не оптимален.
Ты должен, создать новый объект нового размера, скопировать туда остающиеся данные из старого вектора. Затем, ты должен обменять поля V и n этих объектов.
По-хорошему, вектор вообще нужно делать с использованием размещающего new, чтобы при уменьшении размера не было необходимости освобождать память и копировать оставшиеся данные. А при увеличении - увеличивать несколько больше, чем требуется, чтобы было меньше этих затратных операций (например, если вызывать push для stl-вектора, то выделенная память (capacity) будет выделсять так: 2, 4, 8, 16, 32, 64, 128, 256, ...; таким образом, нетрудно заметить, что для 256 элементов память будет перевыделяться только 8 раз, а по твоему алгоритму - все 512, если использовать resize).

Это сообщение отредактировал(а) bsa - 2.4.2010, 11:37

Если это будет оптимально, то я попробую переделать щас )Тогда у меня пара вопросов:

1.выделение больше это не плохо?(например мне надо 129 а выделяется 256...)
2.Это так хорошо компенсируется количеством вызовов resize?

Просто нас всё учат сколько нужно столько и выдели)Лишнего не выделять, а то приводятся примеры с размерностью массивов не 10 а в энное количество раз больше.


Это сообщение отредактировал(а) toxx - 2.4.2010, 13:37

Есть рамки разумного. Конечно, если ты заполняешь массив путем 513 вызовов метода push, то любой алгоритм будет работать неоптимально. Или сильно тормозить, или выделит память под лишние 511 элементов. Учитывая нынешние объемы памяти, второе предпочтительней первого.
Но в любом случае, реализация resize через 1 полное и оно частичное копирование всего массива - это перебор. Достаточно одного "частичного".

Да это верно...=)
Только разберусь со своим деревом(опять чето не удаляет ничего), и попробую реализовать,что вы посоветовали...

Вектор не может знать сколько нужно, поэтому он должен подбирать средне-оптимальную стратегию,
но при этом должен оставлять возможность "ручного" управления.
Т.е. если программист в курсе что у него будет именно 129 элементов, он может сделать vector.reserve (129), и спокойно через push добавлять элементы, не испытывая (лишней) переаллокации.
Также хочу отметить, что это плохое решение - выбирать один контейнер на все случаи жизни.. 
Вектор удобен в случае рандомного доступа к элементам, но для "произвольного" наполнения он не эффективен. 
Но и тут не все так плохо, как кажется.
Программист может для наполнения использовать например очередь, которая не будет столь необдуманно копировать содержимое, как вектор, а также не будет столь жадная на память как список. Ну а как наполнение закончено и необходим быстрый рандомный доступ и линейное расположение, то можно за один присест, перекопировать очередь в вектор.

Исходя из вышесказнного считаю, что создание своего вектора иначе, чем для учебных целей, плохая затея.. 

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

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

примерно так :


и Вам будет легче, и у форумчан глаза целей.

P.S. содержимое  использованно только для примера оформления, ибо оно далеко от приемлегого..

bsa
Вродебы сделал чего-то сделал
Класс

метод

Изменил конструктор



mes
Ну я уже взялся, тем более я взялся, чтобы понять как работают классы как перекгружать и т.д. 
Да конечно я буду использовать свой вектор тока в лабах, но думаю мне пойдет на пользу если я сделаю грамотно всё.

А мне показалось, что как раз сейчас самое время показать, как обойти недостатки вектора, и чтоб пришло понимание, что неоптимальность вектора это не вина вектора, а неправильный выбор программистом либо контейнера либо алгоритма использования  

Добавлено @ 18:04

При таком подходе польза обязательно должна быть 

Добавлено @ 18:09

изменение типа k на  unsigned .. поможет избавиться от ненужной нагрузки на логику такой как проверка k<0.


не очень удачное решение, удалять контейнер, до получения нового..
Логичнее заполнять новый, потом swap`нуть и только после этого удалять ненужное..

Добавлено через 7 минут и 49 секунд

память находящуюся между size и capacity не нужно занулять.. Это логически лишнее..

Добавлено через 11 минут и 58 секунд

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


Это сообщение отредактировал(а) mes - 2.4.2010, 18:09

Тогда желаю удачи в своем совершенствовании. Это правильная позиция.

ну а это что еще за извращение ? увеличивать на коэффицент вместимость нужно только в том случае, если происходит переполнение при вставке, а не тогда, когда напрямую задается размер.

Добавлено через 2 минуты и 4 секунды

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

mes 
1.Заменил тип(как посоветовал bsa на size_t, чтож попробуем)

2.Цикл поправил

3. А вот насчет 


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

4.Я не понимаю почему тогда столько книг написано по STL и довольно многие пользуются,
что не глянь тему, люди вашего уровня все переделывают на vector, iterator и пишут,что лучше его использовать(да наверно не везде)...

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


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

нет, лучше добавить оператор swap , пригодится не только для текущей ситуации...  не бойтесь он очень простой в реализации 

 

Исправил, пока без swap'a


и конструктор заодно


Еще + в том, что я сразу могу проверить свой вектор на деле( я с помощью него дерево храню эн-мерное, в соседней теме)

Это сообщение отредактировал(а) toxx - 2.4.2010, 18:38

вместимость  не может быть меньше размера..

Добавлено @ 18:56

у вас получается, что вместимость всегда равна степени 2ки, а суть не в этом,
а в том чтоб увеличивать текущую вместимость на определенный коэффициент.

кстати хотелось бы также отметить, что коэф. 2 не самый оптимальный, но для простоты пойдет.

Добавлено @ 18:57
В остальном нужно подождать, пока внесете изменения уже озвученные в этой теме..


Это сообщение отредактировал(а) mes - 2.4.2010, 19:01

ИванМ,mes 
Да... идей вы мне подкинули массу, спасибо.
Как с деревом разберусь еще добавлю идею swap(mes'a).


Это сообщение отредактировал(а) toxx - 2.4.2010, 21:09

mes
А скажите пожалуйста основную идею swap?
т.е. как я понял(т.е. не понял) если менять местами векторы Х и Y это чтото типа

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

вот что получилось(если честно судя по моему забору он не верный...+ он не компилируется)


Еще есть идея, что он как конструктор копирования вызывается для указателя(это больше похоже на правду)

все гораздо проще:



Это сообщение отредактировал(а) mes - 3.4.2010, 20:23

mes
оу, до такого ябы не додумался(даже не знал о существовании такого)

Переписал resize() со swap
capacity у меня по степени двойки=)

Вы уверены ? попробуйте исправить сами без подсказки ..

Добавлено @ 21:17

имхо логичней все таки




Это сообщение отредактировал(а) mes - 3.4.2010, 21:18

mes
Интересно, я сначала подумал почему не работает...
потом откомпилировал 5 раз подряд из них 4 раза компилирует и работает, на 5й показывает ошибку доступа к памяти crtexe.c


Это сообщение отредактировал(а) toxx - 3.4.2010, 22:25

вообще-то resize() возвращает void 
ну а ошибки не все исправили ..


Это сообщение отредактировал(а) mes - 3.4.2010, 22:30

Хммм... компилятор перестал выдавать ошибки crtexe.c 
я уже даже вектор нарисовал на бумажке до и после увеличения для:

компилятор проверяет корректность , а не логичность.. 

Как сложно делать вещи логичными оказывается....

1.тут я делаю чтобы ёмкость у изменяемого вектора была new_size*2;

2.Так вродебы это не прямая рекурсия, а косвенная...какие слова я знаю ухх
3.Пока я был уверен что я прав в предыдущем посте... набросал функцию push_back(уже боюсь что тут что-то я не логично сделал, но я старался быть таковым)

4.Мне нужна будет сортировка массива, вношу быструю сортировку с разделением


Это сообщение отредактировал(а) toxx - 3.4.2010, 23:51

что за удаление/создание внутри push_backa?  

Добавлено через 7 минут и 40 секунд

вопрос не в том что Вы делаете, а для чего изменяете переменную того объекта, который Вам больше не понадобится ?


ну а что меняет ? 


сортировка не является методом вектора.. Она должна быть внешней  функцией.

блин, вот и блин...
А рекурсия не идет в методе?или я совсем чтото затупил...

Это сообщение отредактировал(а) toxx - 4.4.2010, 00:12

прежде всего будьте проще :




Это сообщение отредактировал(а) mes - 4.4.2010, 00:25

Про сортировку понял...

Добавлено @ 00:30
у меня  reserve нету =(

ну у меня тоже красиво выгрядит push_back...
я себя прям чувствую совсем бесполезным на фоне вашей логики=(
А можно хотябы пузырьковую как метод добавить?или одельно только совсем?

Это сообщение отредактировал(а) toxx - 4.4.2010, 00:32

Добавлено @ 00:33

ну так кто мешает добавить ?

Добавлено @ 00:39


Добавлено @ 00:40

к сожалению не моей.. я ее когда-то подсмотрел )

Добавлено @ 00:41

зачем его как метод добавлять ?

Добавлено @ 00:42
P.S. код писал здесь и не проверял..к тому же сейчас ночь - могут быть ошибки.. я просто передавал суть..  так что внимательней  


Это сообщение отредактировал(а) mes - 4.4.2010, 10:21

Добавлено @ 00:50
mes
Охх спасибо за эти советы вроде бы разобрался в том что вы скинули...
код вродебы простой, но меня не посещают пока такие строки =(

...Пока разбирался и искал что такое reserve() вы ушли =)

Это сообщение отредактировал(а) toxx - 4.4.2010, 01:36

reserve() отвечает за capacity
resize()    отвечает за size

на будущее, если захотите вектор довести до ума, то еще неплохо бы посмотреть, на функции
uninitialized_copy и uninitialized_fill
http://cplusplus.com/reference/std/memory/...itialized_copy/
http://cplusplus.com/reference/std/memory/...itialized_fill/

и разобраться что представляет из себя аллокатор
http://cplusplus.com/reference/std/memory/allocator/

Это сообщение отредактировал(а) mes - 4.4.2010, 10:30

Да я всё нашел  
И еще у вас в коде я увидел некоторые, я бы сказал для себя фишки например
1.

как я понимаю это отсюда

Но в чем отличие?Для себя я уяснил что это тоже самое, как для любого типа занулить?
только почему не (*this)[m_size++] = T, а именно Т()?
2. в этойже строчке (*this)[m_size++]  m_size++  увеличивается прям в []? вродебы как пост инкремент...
Сам я боюсь использовать такую конструкцию, боюсь что неверный результат будет стараюсь делать это за квадртаными скобками.
Еще нашел, что приоритет у [] выше чем у m_size++, получается что выполняется сначала в цикле для m_size а в следующем цикле для увеличенного m_size на 1.

ну так а в чем отличие к примеру между int и int() знаете ? в одном случае имя типа, а в другом создание объекта.


"не уверен не обгоняй" ©  - пока делайте за скобками, как прочувствуете  эту операцию, перестанете бояться 


приоретет сказывается на разбор команды,  но не на ее выполнение.
Особенность постинкремента (а также постдекремента) в том, что результатом будет значение до его изменения..

Проверил все эти новшества на своём дереве, что-то перемудрили походу с функциями
resize() reserve()
mes 
p.s. скажите, пожалуйста только за что отвечает эта ошибка?
Ошибка

она говорит о том, что выходите за  границы памяти.. т.е пишите не куда положено... 




ну показывайте код вектора, посмотрим чего там перемудренно 

mes
Только не говорите пожалуйста, я сам попробую

ну я только слегка подскажу..  

функция erase не вызывает переаллокации и никак не влияет на вместимость, она только удаляет (затирает) ненужный элемент.

А я нашел...)))
Нужно добавить:

Память массива не увеличивалась, но цикл шел и обнулял до новой помяти=)


Добавлено через 4 минуты и 13 секунд
или не нашел...

Добавлено через 7 минут и 20 секунд
А если убрать в erase()

То тоже работает, да верно этот метод я не трогал с последних советов ИванМ
А щас нужно измить слегка с учетом новых методов.

а вызов reserve() на что ?



вообще то новые методы на функционал erase не влияют ..

mes
Тогда странно, если не влияют я при удалении вершин использую только erase() 

Еще также использую resize() при создании дерева.
Да, я понимаю что reverse() вместо этих строк

Но если они присутствуют всё работает =)