Информация об изменениях

Сообщение ::operator new() в самописном стэке от 07.06.2023 20:15

Изменено 07.06.2023 22:18 Sm0ke

::operator new() в самописном стэке
Здравствуйте, rg45, Вы писали:

R>Вот прямо так, как ты описал, не получится — инициализация массива предполагает инициализацию каждого его элемента. Но ты можешь получить очень близкую функциональность при помощи std::vector и двух его функций-членов — reserve и emplace_back. Эскизно так:

R>
R>std::vector<MyItem> v;

R>v.reserve(50);                     // резервируем память под 50 элементов, без создания самих самих элементов.
R>assert(v.size() == 0);

R>v.emplace_back(arg1, arg2, arg3);  // конструируем элементы прямо по месту выделенной памяти, без промежуточных копирований и перемещений
R>v.emplace_back(arg1, arg2, arg3);  // фактически внутри вектора используется placement new, только скрыто от программиста
R>v.emplace_back(arg1, arg2, arg3);

R>assert(v.size() == 3);
R>


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

Ещё думал про std::aligned_alloc() из <cstdlib> но в студии community его нет (на сайте написано, что микрософт его не поддерживает, тк он не дружит с их free).
Есть ещё конечно сишный aligned_alloc() без std:: ...

Пока остановился на вызове ::operator new(s_size * p_reserve, s_align, std::nothrow), пришлось писать reinterprete_cast<>()
Вот такая получилась заготовочка:

using t_index = std::ptrdiff_t;

    template <typename T>
    struct vector {
        using element_type = T;
        using pointer = element_type *;

        static constexpr std::align_val_t
            s_align{alignof(element_type)};
        static constexpr t_size
            s_size{sizeof(element_type)};

        struct mem {
            static pointer allocate(t_index p_reserve) {
                return reinterpret_cast<pointer>(
                    ::operator new(s_size * p_reserve, s_align, std::nothrow)
                );
            }

            static void free(pointer p_handle) {
                ::operator delete(p_handle, s_align);
            }

            using tfn_allocate = decltype(&allocate);
            using tfn_free = decltype(&free);

            // data
            tfn_allocate
                m_alloc = &allocate;
            tfn_free
                m_free = &free;

            pointer do_alloc(t_index p_reserve) const {
                pointer ret = m_alloc(p_reserve);
                if( ret == nullptr ) { throw std::bad_alloc{}; }
                return ret;
            }
        };

        static constexpr mem s_mem{};

        using mem_const_pointer = const mem *;

    private:

        struct t_data {
            pointer
                m_handle;
            t_index
                m_reserve,
                m_count = 0;
            mem_const_pointer
                m_mem = &s_mem;
        };

        // data
        t_data
            m_data;

    public:

        vector() = delete;
        vector(const vector &) = delete;
        vector(vector &&) = delete;
        vector & operator = (const vector &) = delete;

        vector & operator = (vector && p_other) {
            std::ranges::swap(m_data, p_other.m_data);
        }

        vector(t_index p_reserve) {
            m_data.m_handle = m_data.m_mem->do_alloc(p_reserve);
            m_data.m_reserve = p_reserve;
        }

        ~vector() {
            m_data.m_mem->m_free(m_data.m_handle);
        }
    };


Выделение и освобождение памяти тут через указатели на функцию, чтобы этот вектор можно было передавать в dll (надеюсь, что такое решение рабочее).

Чем не устраивает стандартный вектор? При перерезервировании он делает copy или move конструирование элементов (что нежелательно для типов, которые я собираюсь в нём хранить). Ещё при инсерте делает move assignment.

Планирую использовать memcpy() при перерезервировании, и memmove() при инсерте/удалении. Ещё добавлю полиси роста как шаблонный параметр, чтобы при добавлении — резерв увеличивался не как в std::vector<> в 2 раза, а на фиксированный шаг. Или задавать свои полиси роста.

Изначальная задача вообще в следующем — Нужен контейнер на подобии стэка, чтобы:
  • добавлять в конец или редко на предпоследнюю позицию.
  • удалять последние N элементов.
  • иметь быстрый доступ к последним 3-м элементам.
Может стОит взять std::forward_list<> и работать с началом списка? Или какие есть ещё варианты?
p.s: Число хранимых элементов в теории не превышает 20-30, но может быть что угодно, ведь это для интерпретатора. Каждый элемент хранит 2 указателя и итератор на std::list<>
::operator new() в самописном стэке
Здравствуйте, rg45, Вы писали:

R>Вот прямо так, как ты описал, не получится — инициализация массива предполагает инициализацию каждого его элемента. Но ты можешь получить очень близкую функциональность при помощи std::vector и двух его функций-членов — reserve и emplace_back. Эскизно так:

R>
R>std::vector<MyItem> v;

R>v.reserve(50);                     // резервируем память под 50 элементов, без создания самих самих элементов.
R>assert(v.size() == 0);

R>v.emplace_back(arg1, arg2, arg3);  // конструируем элементы прямо по месту выделенной памяти, без промежуточных копирований и перемещений
R>v.emplace_back(arg1, arg2, arg3);  // фактически внутри вектора используется placement new, только скрыто от программиста
R>v.emplace_back(arg1, arg2, arg3);

R>assert(v.size() == 3);
R>


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

Ещё думал про std::aligned_alloc() из <cstdlib> но в студии community его нет (на сайте написано, что микрософт его не поддерживает, тк он не дружит с их free).
Есть ещё конечно сишный aligned_alloc() без std:: ...

Пока остановился на вызове ::operator new(s_size * p_reserve, s_align, std::nothrow), пришлось писать reinterprete_cast<>()
Вот такая получилась заготовочка:

using t_index = std::ptrdiff_t;

    template <typename T>
    struct vector {
        using element_type = T;
        using pointer = element_type *;

        static constexpr std::align_val_t
            s_align{alignof(element_type)};
        static constexpr t_size
            s_size{sizeof(element_type)};

        struct mem {
            static pointer allocate(t_index p_reserve) {
                return reinterpret_cast<pointer>(
                    ::operator new(s_size * p_reserve, s_align, std::nothrow)
                );
            }

            static void free(pointer p_handle) {
                ::operator delete(p_handle, s_align);
            }

            using tfn_allocate = decltype(&allocate);
            using tfn_free = decltype(&free);

            // data
            tfn_allocate
                m_alloc = &allocate;
            tfn_free
                m_free = &free;

            pointer do_alloc(t_index p_reserve) const {
                pointer ret = m_alloc(p_reserve);
                if( ret == nullptr ) { throw std::bad_alloc{}; }
                return ret;
            }
        };

        static constexpr mem s_mem{};

        using mem_const_pointer = const mem *;

    private:

        struct t_data {
            pointer
                m_handle;
            t_index
                m_reserve,
                m_count = 0;
            mem_const_pointer
                m_mem = &s_mem;
        };

        // data
        t_data
            m_data;

    public:

        vector() = delete;
        vector(const vector &) = delete;
        vector(vector &&) = delete;
        vector & operator = (const vector &) = delete;

        vector & operator = (vector && p_other) {
            std::ranges::swap(m_data, p_other.m_data);
        }

        vector(t_index p_reserve) {
            m_data.m_handle = m_data.m_mem->do_alloc(p_reserve);
            m_data.m_reserve = p_reserve;
        }

        ~vector() {
            m_data.m_mem->m_free(m_data.m_handle);
        }
    };


Выделение и освобождение памяти тут через указатели на функцию, чтобы этот вектор можно было передавать в dll (надеюсь, что такое решение рабочее).

Чем не устраивает стандартный вектор? При перерезервировании он делает copy или move конструирование элементов (что нежелательно для типов, которые я собираюсь в нём хранить). Ещё при инсерте делает move assignment.

Планирую использовать memcpy() при перерезервировании, и memmove() при инсерте/удалении. Ещё добавлю полиси роста как шаблонный параметр, чтобы при добавлении — резерв увеличивался не как в std::vector<> в 2 раза, а на фиксированный шаг. Или задавать свои полиси роста.

Изначальная задача вообще в следующем — Нужен контейнер на подобии стэка, чтобы:
  • добавлять в конец или редко на предпоследнюю позицию.
  • удалять последние N элементов.
  • иметь быстрый доступ к последним 3-м элементам.
Может стОит взять std::forward_list<> и работать с началом списка? Или какие есть ещё варианты?
p.s: Число хранимых элементов в теории не превышает 20-30, но может быть что угодно, ведь это для интерпретатора. Каждый элемент хранит 2 указателя и итератор от std::list<>