• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

wskaźniki na strukturę

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
232 wizyt
pytanie zadane 26 października 2020 w C i C++ przez komboboost0 Użytkownik (570 p.)

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

image

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

image

komentarz 26 października 2020 przez wizarddos Pasjonat (21,640 p.)
tak na przyszłość kod wstawiaj w bloczkach kodu dostępnych tu
2
komentarz 26 października 2020 przez j23 Mędrzec (189,220 p.)
Chyba nigdy nie zrozumiem tej mody na wklejanie tekstu w formie screenshota. Że to niby prościej ma być?

1 odpowiedź

+1 głos
odpowiedź 26 października 2020 przez j23 Mędrzec (189,220 p.)
	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.
komentarz 26 października 2020 przez komboboost0 Użytkownik (570 p.)
Muszę przenieść pamięć za pomocą move()?
komentarz 26 października 2020 przez Patryk Kaczmarek Użytkownik (630 p.)
edycja 26 października 2020 przez Patryk Kaczmarek
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.
komentarz 26 października 2020 przez komboboost0 Użytkownik (570 p.)

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 = /////////;
}

 

1
komentarz 26 października 2020 przez j23 Mędrzec (189,220 p.)
edycja 26 października 2020 przez j23

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);

 

komentarz 27 października 2020 przez komboboost0 Użytkownik (570 p.)
edycja 29 października 2020 przez komboboost0

@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

1
komentarz 27 października 2020 przez j23 Mędrzec (189,220 p.)

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) });
	...

 

komentarz 29 października 2020 przez komboboost0 Użytkownik (570 p.)

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
	}
1
komentarz 29 października 2020 przez j23 Mędrzec (189,220 p.)
edycja 29 października 2020 przez j23

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.

komentarz 29 października 2020 przez komboboost0 Użytkownik (570 p.)

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.

1
komentarz 29 października 2020 przez j23 Mędrzec (189,220 p.)
edycja 29 października 2020 przez j23

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.

Podobne pytania

0 głosów
2 odpowiedzi 588 wizyt
pytanie zadane 3 czerwca 2017 w C i C++ przez Dorota95 Nowicjusz (210 p.)
0 głosów
1 odpowiedź 3,010 wizyt
pytanie zadane 19 września 2017 w C i C++ przez Sic Dyskutant (8,500 p.)
0 głosów
1 odpowiedź 249 wizyt
pytanie zadane 29 stycznia 2019 w C i C++ przez Giero112 Nowicjusz (170 p.)

90,401 zapytań

139,013 odpowiedzi

311,512 komentarzy

60,082 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...