Добрый день. Нужна помощь в реализации динамических структур. Нужно написать дек с использованием malloc.

Как я понял, дек это обычный список. Можно вставлять и взад и вперед. Суть работы списков заключается в правильной передачи связей при вставке\удалении (смотри метод push_back). Нужно учитывать m_head. Если вставляем, и m_head == 0, то просто всё указываем в m_head. Если удаляем, и это был последний элемент, то надо будет вставить m_head = 0; Все эти связи, указатели на левый и правый и тд., сложно связать в голове.

Так как используются функции malloc\free, потребуется уметь вызывать конструктор\деструктор вручную.

В реальном контейнере необходимо дать возможность выбора, каким способом выделять память, malloc, new, через АПИ операционной системы и т. д. По этому, пишем аллокатор.

template<typename _type>
struct shprotAllocatorMalloc {

typedef _type* pointer;

pointer allocate(std::size_t count) {
pointer ptr = (pointer)std::malloc(count * sizeof(_type));
new((void *)ptr) _type();
return ptr;
}
void deallocate(pointer ptr) {
ptr->~_type();
std::free(ptr);
}
};
template<typename _type>
struct shprotAllocatorStdNew {

typedef _type* pointer;

pointer allocate(std::size_t count) {
return new _type[count];
}
void deallocate(pointer ptr) {
delete[] ptr;
}
};

Тест

class TestClass {
public:
TestClass() { printf("TestClass - constructor\n"); }
TestClass(int v) { a = b = c = d = v; printf("TestClass - constructor2\n"); }
~TestClass() { printf("TestClass - destructor\n"); }
int a, b, c, d;
};

int main(){
shprotAllocatorMalloc<TestClass> testAllocatorMalloc;
shprotAllocatorStdNew<TestClass> testAllocatorStdNew;
auto ptr1 = testAllocatorMalloc.allocate(1);
auto ptr2 = testAllocatorStdNew.allocate(1);
testAllocatorMalloc.deallocate(ptr1);
testAllocatorStdNew.deallocate(ptr2);
...
}

Теперь основы списков.
Когда суём объект в список, мы создаём специальный объект, который хранит передаваемый нами объект. Этот объект указывает на следующий элемент в списке, и может указывать так-же на предидущий элемент.

template<typename _type>
struct shprotListNode{
shprotListNode()
:
m_left(nullptr),
m_right(nullptr)
{}

_type m_data;

shprotListNode* m_left;
shprotListNode* m_right;
};

Теперь список.

template<typename _type, typename _allocator = shprotAllocatorMalloc<shprotListNode<_type>>>
class shprotList {
public:
shprotList() : m_head(0) {}
~shprotList() { clear(); }

void push_back(const _type& value) {
shprotListNode<_type>* new_node = m_allocator.allocate(1);
new_node->m_data = value;
if (m_head)
{
// к хвосту цепляем ноду. теперь это новый хвост
m_head->m_left->m_right = new_node;
new_node->m_left = m_head->m_left;
// хвост цепляю к голове
new_node->m_right = m_head;
m_head->m_left = new_node;
}
else
{
m_head = new_node;
m_head->m_left = m_head;
m_head->m_right = m_head;
}
}

void clear() {
if (!m_head) return;
auto _curr = m_head;
auto _end = m_head->m_left;
while (true){
auto next = _curr->m_right;
m_allocator.deallocate(_curr);
if (_curr == _end)
break;
_curr = next;
}
m_head = 0;
}

private:
_allocator m_allocator;
shprotListNode<_type>* m_head; // хвост это m_head->m_left
};

test
{
shprotList<TestClass> list_malloc;

list_malloc.push_back(TestClass(1));
list_malloc.push_back(TestClass(2));
list_malloc.push_back(TestClass(3));
list_malloc.push_back(TestClass(4));
list_malloc.push_back(TestClass(5));
}
{
shprotList<TestClass, shprotAllocatorStdNew<shprotListNode<TestClass>>> list_new;
list_new.push_back(TestClass(-1));
list_new.push_back(TestClass(-2));
list_new.push_back(TestClass(-3));
list_new.push_back(TestClass(-4));
list_new.push_back(TestClass(-5));
}