wskaźniki na strukturę

Question

Próbuję napisać listę. Zaciąłem się na zabawie ze wskaźnikami w metodzie dodawania elementu na koniec listy. Ewidentnie czegoś nie rozumiem, bo nie potrafię przeskoczyć tych błędów.

Całość kodu: https://godbolt.org/z/obGKPr

Błędy dotyczą kolejno 28, 27, 24 i 27 linii linked_list.h :

Comments

tak na przyszłość kod wstawiaj w bloczkach kodu dostępnych tu

---

Chyba nigdy nie zrozumiem tej mody na wklejanie tekstu w formie screenshota. Że to niby prościej ma być?

Answer 1

	void add_end(T* node)
	{
		auto element = std::make_unique<T*>(std::forward<T*>(node));
		if (tail == nullptr) head = element.get();
		...
		tail = element.get();
		...
	}

• użycie std::forward w tym przypadku jest kompletnie bez sensu.
• zdecyduj się, co element ma trzymać: wskaźnik na obiekt T czy na wskaźnik T*.
• element jest właścicielem pamięci, więc po wyjściu z funkcji head i tail będą zawierać niepoprawne wskaźniki.

Comments

Muszę przenieść pamięć za pomocą move()?

---

Jesli operujesz na wskaznikach to std::forward I std::move nie ma sensu. std::move I std::forward powinno sie robic na obiektach. P.s. std::move NIC nie przenosi.

---

W takim razie jak mogę przenieść element na head?

void add_end(T* node)
	{
		auto element = std::make_unique<T>(node);
		if (tail == nullptr) head = /////////;
}

 

---

Wydaje mi się, że nie przemyślałeś tej listy do końca. Dlaczego węzły listy tworzone są poza nią? Typem T powinien być typ danych, które chcesz składować w liście, a nie typ węzła.

     if (tail == nullptr) head = /////////;

if (tail == nullptr) head = std::move(element);

i zamiast:

auto element = std::make_unique<T>(node);

std::unique_ptr<T> element(node);

 

---

@j23,

Typem T powinien być typ danych, które chcesz składować w liście, a nie typ węzła.

Wyszedłem z założenia że to właśnie węzeł jest tym typem który miałby być uniwersalny dzięki template.

Dlaczego węzły listy tworzone są poza nią?

Aby to zmienić stworzyłem dwie podobne metody:

void add_end(Arg1 v1, Arg2 v2){...}

void add_beg(Arg1 v1, Arg2 v2){...}

void add_end(Arg1 v1, Arg2 v2)
	{
		Node* element = new Node(v1, v2); // ten sam sposób inicjalizacji jak w main() nie działa
		std::unique_ptr<Node> element;
		if (!head) head = std::move(element);
		else if (!tail)
		{
			tail = element.get();
			element->prev = head.get();
			head->next = std::move(element);
		}
		else
		{
			element->prev = tail;
			auto temp = tail;
			tail = element.get();
			tail->next = std::move(element);
		}
		size++;
        this->set(size, v1, v2);
	}

Jest jakaś możliwość żebym mógł tworzyć węzły w metodach klasy czy muszę wprowadzić więcej modyfikacji? Nie wpadłem na pomysł jak to zrobić z obecnym stanem kodu.

 

całość : https://godbolt.org/z/jfsxbM

---

Aby to zmienić stworzyłem dwie podobne metody:

IMO trochę bez sensu są te dwa argumenty, bo jeśli to szablon, to nie zawsze dwa będą potrzebne. Lepiej dać jeden, a jak trzeba będzie więcej danych, to wystarczy użyć struktury czy krotki.

Tak to widzę:

template<class T>
class Linked_list
{
    struct Node {
    	std::unique_ptr<Node> next;
    	Node* prev = nullptr;
        T value;
    };
    
    
	std::unique_ptr<Node> head;
	Node* tail = nullptr;
	int size = 0;

public:
	void add_end(const T &value)
	{
		std::unique_ptr<Node> element(new Node{ nullptr, nullptr, value });
		if (!head) head = std::move(element);
		else if (!tail)
		{
			tail = element.get();
			element->prev = head.get();
			head->next = std::move(element);
		}
		else
		{
			element->prev = tail;
			auto temp = tail;
			tail = element.get();
			tail->next = std::move(element);
		}
		size++;
	}
        ...
};

int main()
{
    Linked_list<int> l;
    
    l.add_end(666);
    l.add_end(999);
}

Wersja bardziej pro:

template 
<
    typename U,
    typename = std::enable_if_t<std::is_same<T, typename std::remove_reference<U>::type>::value>
>
void add_end(U &&value)
{
	std::unique_ptr<Node> element(new Node{ nullptr, nullptr, std::forward<U>(value) });
	...

 

---

Dziękuję J23 za rady.

Obecnie próbuję stworzyć funkcję która miałaby zamienić miejscami dwa węzły na mojej liście, aby wykorzystać go do np. bubble sorta. 

Nie mogę przeskoczyć jednego błędu, ponieważ wychodzi przy bardzo podobnych operacjach które wykonywałem wcześniej (np. przy add_end) i nie rozumiem dlaczego 'tam działa a tu nie' :

"binary '=': no operator found which takes a right-hand operand of type T* (or there is no acceptable conversion)".

struct Node {
    Node(int v1 = 1, char v2 = 'a') : data1(v1), data2(v2) {}
    std::unique_ptr<Node> next;
    Node* prev = nullptr;
    int data1;
    char data2;
};

[...]

void swap(T* node, T* node2)
	{
		node2->prev = node->prev;
		node->prev = node2;
		node->next = std::move(node2->next);
		node2->next = std::move(node); // error
	}

---

Jakoś tak:

void swap(T* node, T* node2)
{
    if(node->prev) {
        node->prev->next.release();
        node->prev->next.reset(node2);
    }
    
    node->next.release();
    node2->prev = node->prev;
    node->prev = node2;
    node->next = std::move(node2->next);
    node2->next.reset(node); 
}

Pomysł użycia unique_ptr do implementacji listy jest niefortunny.

---

Pomysł użycia unique_ptr do implementacji listy jest niefortunny.

Shared_ptr mógłby okazać się lepszym wyborem?

Po użyciu twojego kodu wyrzuca mi wyjątek.

---

Shared_ptr mógłby okazać się lepszym wyborem?

Nie. Użycie jakiegokolwiek inteligentnego wskaźnika do implementacji listy jest kiepskim pomysłem. Przy usuwaniu bardzo dużych list może dojść do przepełnienia stosu, bo usuwanie węzłów z poziomu destruktora listy odbywa się rekurencyjnie.

Po użyciu twojego kodu wyrzuca mi wyjątek.

Poprawiłem poprzedni kod. Check it out.

Błąd też może być w niepoprawnym ustawianiu wskaźnika head.