Я уже реализовал шаблонный связанный список, который использует уникальные указатели внутри. Сначала я создаю ListNode структуру, которая содержит этот указатель на следующий узел и данные. Наконец, он также имеет удобную функцию для преобразования его в строку (для последующей печати):
template < typename T>
struct ListNode;
template<typename T >
using ListNodePtr = std::unique_ptr<ListNode<T>>;
template < typename T>
struct ListNode
{
ListNode(T data) : data(data) {}
T data;
ListNodePtr<T> next = nullptr;
std::string str()
{
std::string output;
ListNode<T>* curr = this;
while (curr)
{
output += std::to_string(curr->data) + " ";
curr = curr->next.get();
}
return output;
}
};
В связанном списке хранится умный указатель на узел, который содержит все другие узлы. Было реализовано несколько методов с базовыми функциями списка c, например вставка элемента, удаление в позиции n или обращение к списку.
template <typename T>
class LinkedList
{
public:
LinkedList() = delete;
LinkedList(const std::vector<T>& data)
{
createListFromVector(data);
}
void createListFromVector(const std::vector<T>& data)
{
if (data.empty())
{
return;
}
ListNodePtr<T> head = nullptr;
ListNode<T>* curr = nullptr;
for (const auto& item : data)
{
if (!head)
{
head = std::make_unique<ListNode<T>>(item);
curr = head.get();
continue;
}
curr->next = std::make_unique<ListNode<T>>(item);
curr = curr->next.get();
}
m_list = std::move(head);
};
// insert node at head
void insertNode(T data)
{
ListNodePtr<T> newNode = std::make_unique<ListNode<T>>(data);
newNode->next = std::move(m_list);
m_list = std::move(newNode);
}
// delete the nth node
void deleteNode(int pos)
{
if (pos < 1) { return; }
ListNode<T>* curr = m_list.get();
while ((pos-1) && curr)
{
curr = curr->next.get();
--pos;
}
if (curr)
{
ListNodePtr<T> next = std::move(curr->next->next);
curr->next = std::move(next);
}
}
// reverse the list iteratively
void reverse()
{
ListNodePtr<T> prev = nullptr;
ListNodePtr<T> curr = std::move(m_list);
ListNodePtr<T> next = nullptr;
while (curr)
{
next = std::move(curr->next);
curr->next = std::move(prev);
prev = std::move(curr);
curr = std::move(next);
}
m_list = std::move(prev);
}
void print() { std::cout << str() << std::endl; };
std::string str() { return getHead()->str(); }
private:
ListNode<T>* getHead() const { return m_list.get(); };
std::unique_ptr<ListNode<T>> m_list = nullptr;
};
Как видите, я реализовал некоторые базовые функции c таким образом, однако, это кажется слишком запутанным, по сравнению с тем, как я, например, сделал бы это в Python. Все было бы намного проще без ограничения unique_ptr .
Например, предположим, что я хочу создать метод: toOddThenEven , который переставляет элементы в списке - сначала все нечетные позиции, затем все четные позиции: 1 , 7, 2 , 14, 5 , 32 становится 1, 2, 5, 7, 14 32. Первый индекс считается 1 и, следовательно, нечетный .
Обычно этого можно легко сделать sh, сделав несколько копий головы. из шансов, глава событий, а затем еще два указателя для продвижения вперед по списку. В конце вы можете получить список шансов: 1-> 2-> 5 и список четных чисел: 7-> 14-> 32 , которые можно объединить, установив следующий указатель последнего нечетного индексного элемента на начало четных и возвращающий заголовок коэффициентов.
Пример в Python:
def toOddThenEven(node):
if not node:
return None
headO = node
headE = headO.next
curr = headO
nxt = headE
while(nxt and nxt.next):
# skip adjancent element for both curr and nxt
curr.next = curr.next.next
nxt.next = nxt.next.next
# move forward
nxt = curr.next.next
curr = curr.next
# concatenate odds list and evens list
curr.next = headE
return headO
Теперь, возможно, есть лучший способ реализовать это, но, тем не менее, вам, вероятно, нужно сделать несколько временных копий, как я делал выше, чтобы это работало без взрыва вашего мозга.
Поэтому, решение C ++ будет использовать shared_ptr s вместо unique_ptr s. ОДНАКО, в этом случае мы будем использовать в 2 раза больше памяти для каждого указателя, таким образом делая наши структуры данных LinkedList НЕ ОПТИМАЛЬНЫМИ - по сравнению с простой реализацией простого использования необработанных указателей с new / удалите и RAII , чтобы пользователь наших структур данных не заботился об управлении своей памятью напрямую.
Итак, в случае проектирования такой структуры данных - особенно когда время короткое (например, во время интервью или в демонстрационных целях для других разработчиков), кажется, что необработанные указатели являются лучшим выбором в этом случае. Либо так, либо shared_ptr , если вас не волнует дополнительный удар по производительности. Любые мысли по этому поводу будут оценены. Спасибо.