Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.66/35: Рейтинг темы: голосов - 35, средняя оценка - 4.66
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
1

Реализация вектора

10.01.2016, 11:24. Показов 6831. Ответов 80

Добрый день. Нужно мне реализовать функции самому push_back та pop_back.
Моя реализация push_back. А от как реализовать pop_back я незнаю. Там нужно только удалить останий елемент. Но как это сделать? Подскиже.
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T, typename Allocator>
void Vector<T, Allocator>::push_back(const T& value)
{
    if (m_size == m_capacity)
    {
        const size_type capacity = 2 * m_capacity;
        pointer begin = m_allocator.allocate(capacity);
 
        UninitializedCopy(m_begin, m_begin + m_size, begin);
        deallocate();
 
        m_begin = begin;
        m_capacity = capacity;
    }
 
    m_allocator.construct(m_begin + m_size, value);
    ++m_size;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.01.2016, 11:24
Ответы с готовыми решениями:

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

Реализация вектора
Здравствуйте друзья! Зашел в тупик после того как попытался реализовать структуру данных типа...

Реализация вектора ссылок
Доброго времени суток, дорогие форумчане! Проблема в следующем: мне дано было задание сделать игру...

Реализация собственного класса вектора
Создать абстрактный тип данных - класс вектор, который имеет указатель на float, число элементов и...

__________________

Записывайтесь на профессиональные курсы C++ разработчиков
80
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 13:44 21
Цитата Сообщение от vvb2011 Посмотреть сообщение
Я так понял там нужно удалить и буфер и размер которые не задействованные.
Освободить лишнюю память. Но требование не является обязательным.
В Вашем случае это будет примерно так:
C++
1
2
3
4
5
6
pointer begin = m_allocator.allocate(m_size);
unitialized_copy(m_begin, m_begin + m_size, begin);
size_t size = m_size ;
deallocate();
m_capacity = m_size = size ;
m_begin = begin ;
конечно, нужно проверки ошибок делать, защиту от исключений и т.д.
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:00  [ТС] 22
Default_070, да
0
26 / 26 / 26
Регистрация: 01.10.2015
Сообщений: 175
12.01.2016, 14:02 23
vvb, можете подсказать как написать свой аллокатор. Вот заинтересовался. Или ссылочку кинуть.
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 14:04 24
Цитата Сообщение от Default_070 Посмотреть сообщение
можете подсказать как написать свой аллокатор. Вот заинтересовался. Или ссылочку кинуть.
Выше есть код: Реализация вектора
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:06  [ТС] 25
решил сделать еще resize, смотрел пример Default_070
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template <typename T>
void vector<T>::resize(size_type count, T value = T())
{
    if (count < m_size)
    {
        m_size = count;
        for (size_type index = count; index < allocator_size; index++)
            array[index] = T();
    }
    else if (count > m_size) {
        if (count > m_size)
        {
            T* temp = new T[count];
            for (syze_type index = 0; index < m_size; index++)
            {
                temp[index] = array[index];
            }
            for (syze_type index = m_size; index < count; index++)
            {
                temp[index] = value;
            }
            m_size = count;
            delete[]array;
            array = new T[m_size];
            for (syze_type index = 0; index < count; index++)
            {
                array[index] = temp[index];
            }
            delete[]temp;
        }
        else if (count <= allocator_size) {
            for (syze_type index = m_size; index < count; index++)
            {
                array[index] = value;
            }
            m_size = count;
        }
    }
}
Добавлено через 57 секунд
Croessmah,
так? Зараз по дебажу. проверу правильно ли работает
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
template <typename T, typename Allocator>
void Vector<T, Allocator>::shrink_to_fit()
{
    pointer begin = m_allocator.allocate(m_size);
    unitialized_copy(m_begin, m_begin + m_size, begin);
    size_t size = m_size;
    deallocate();
    m_capacity = m_size = size;
    m_begin = begin;
}
0
26 / 26 / 26
Регистрация: 01.10.2015
Сообщений: 175
12.01.2016, 14:06 26
Так там нет кода про аллокатор.
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:07  [ТС] 27
Default_070, есть, под вектором
но кину еще раз сюда
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#pragma once
 
#include <new>
#include <cstddef>
 
template <typename T>
class Allocator
{
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;
 
    pointer allocate(size_type number)
    {
        void* blockBegin = ::operator new (number * sizeof(T));
        return (pointer)blockBegin;
    }
    void deallocate(pointer blockBegin, size_type number)
    {
        ::operator delete(blockBegin);
    }
    void construct(pointer block, const_reference object)
    {
        ::new (block) T(object);
    }
    void destroy(pointer block)
    {
        block->~T();
    }
};
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 14:08 28
Цитата Сообщение от Default_070 Посмотреть сообщение
Так там нет кода про аллокатор.
Внимательнее смотрите! Там два "блока с кодом"
0
26 / 26 / 26
Регистрация: 01.10.2015
Сообщений: 175
12.01.2016, 14:09 29
Спасибо, думал будет что-то труднее.
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:16  [ТС] 30
Проверьте еще эту функцию, я по примеру делалDefault_070,
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template <typename T>
void vector<T>::resize(size_type count, T value = T())
{
    if (count < m_size)
    {
        m_size = count;
        for (size_type index = count; index < allocator_size; index++)
            array[index] = T();
    }
    else if (count > m_size) {
        if (count > m_size)
        {
            T* temp = new T[count];
            for (syze_type index = 0; index < m_size; index++)
            {
                temp[index] = array[index];
            }
            for (syze_type index = m_size; index < count; index++)
            {
                temp[index] = value;
            }
            m_size = count;
            delete[]array;
            array = new T[m_size];
            for (syze_type index = 0; index < count; index++)
            {
                array[index] = temp[index];
            }
            delete[]temp;
        }
        else if (count <= allocator_size) {
            for (syze_type index = m_size; index < count; index++)
            {
                array[index] = value;
            }
            m_size = count;
        }
    }
}
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 14:22 31
C++
1
2
3
4
5
6
7
    if (count < m_size)//Если m_size больше, чем нам нужно элементов(count), то нужно удалить лишние из контейнера.
    {
        //А что делается здесь не ясно...
        m_size = count;
        for (size_type index = count; index < allocator_size; index++)
            array[index] = T();
    }
плюс ко всему, Вы начинаете напрямую дергать new и delete, вместо аллокатора.
0
26 / 26 / 26
Регистрация: 01.10.2015
Сообщений: 175
12.01.2016, 14:25 32
Цитата Сообщение от vvb2011 Посмотреть сообщение
if (count > m_size)
Если m_size это текущей размер(количество элементов), то нужно заменить m_size на размер выделенной памяти, иначе запрошенный размер может оказать больше.

Добавлено через 2 минуты
чтобы не перевыделять память мы просто заполняем по умолчанию, а размер устанавливаем в запрошенный
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:30  [ТС] 33
передела, но не кампилюется
C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
template <typename T, typename Allocator>
void Vector<typename T, typename Allocator>::resize(size_type count, T value = T())
{
    if (count < m_size)
    {
        m_size = count;
        for (size_type index = count; index < allocator_size; index++)
            array[index] = T();
    }
    else if (count > m_size) {
        if (count > m_size)
        {
            T* temp = new T[count];
            for (size_type index = 0; index < m_size; index++)
            {
                temp[index] = array[index];
            }
            for (syze_type index = m_size; index < count; index++)
            {
                temp[index] = value;
            }
            m_size = count;
            deallocate(array);
            construct(array);
            for (syze_type index = 0; index < count; index++)
            {
                array[index] = temp[index];
            }
            deallocate(temp);
        }
        else if (count <= allocator_size) {
            for (syze_type index = m_size; index < count; index++)
            {
                array[index] = value;
            }
            m_size = count;
        }
    }
}
0
26 / 26 / 26
Регистрация: 01.10.2015
Сообщений: 175
12.01.2016, 14:32 34
C++
1
2
else if (count > m_size) {
        if (count > m_size)  // m_size замени на allocator_size
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 14:42  [ТС] 35
Croessmah, но я же везеде заменил на deallocate
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 14:45 36
Примерно:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename T>
void vector<T>::resize(size_type new_size, T value = T())
{
    if(new_size > m_size){
        if ( new_size > m_capacity ) {
           pointer begin = m_allocator.allocate(new_size);
           unitialized_copy(m_begin, m_begin + m_size, begin);
           size_t size = m_size ;
           deallocate();
           m_capacity = new_size ;
           m_size = size ;
           m_begin = begin ;
        }
       unitialized_fill_n(m_begin+new_size, new_size - m_size , value);
       m_size = new_size ;
    } else {
       deinitialize(m_begin+count, m_size - new_size ) ;
       m_size = new_size ;
    }
}
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 15:07  [ТС] 37
Croessmah, програма крешиться(
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 15:13 38
Цитата Сообщение от vvb2011 Посмотреть сообщение
програма крешиться
в том виде, в котором я выдал resize, она и не скомпилируется
0
0 / 0 / 0
Регистрация: 09.01.2016
Сообщений: 50
12.01.2016, 15:28  [ТС] 39
Croessmah,
компилюеться но крешиться
0
Don't worry, be happy
16986 / 9864 / 1900
Регистрация: 27.09.2012
Сообщений: 24,461
Записей в блоге: 1
12.01.2016, 15:31 40
Цитата Сообщение от vvb2011 Посмотреть сообщение
компилюеться но крешиться
и откуда же
C++
1
deinitialize(m_begin+count, m_size - new_size ) ;//здесь взялся count? Оно здесь левое.
ну и код программы в студию.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.01.2016, 15:31

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

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

Реализация функций reserve и clear для вектора
Мне нужно самой написать реализацию. От что у меня есть: template&lt;typename T&gt; void...

Как обозначить значения внутри вектора для другого вектора итератором?
Например, в одном векторе есть числа 1, 3, 4. В другом векторе их 5: 25 95 45 65 75. Как сделать...

Найти сколько элементов первого вектора совпадают с элементами второго вектора
#include &lt;iostream&gt; #include &lt;time.h&gt; #include &lt;vector&gt; #include &lt;set&gt; using namespace std; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.