Template, Liste, Funktion



  • @spiegelbirke2 sagte in Template, Liste, Funktion:

    Ich bin mir nicht mal sicher, ob "List" selbst irgendwo definiert sein muss, also als Liste oder Klasse oder ob es einfach ein Objekt aus #include <list> ist.

    Die List muss irgendwo definiert sein. Wahrscheinlich weiter oben in derselben Datei. Suche nach "class List" oder "struct List". List kommt nicht aus dem Standard-Header <list>. Der Typ daraus ist doch std::list<T, A>, also kleines L und mit zwei Templateparametern, außerdem im Namensbereich std.

    Wenn du fragst, wie es ohne Template ginge, dann denk dir doch einfach mal das template weg und nimm an, dass der Typ z. B. double wäre. Die Signatur wäre dann:
    bool List::insert(int pos, const double & x)
    Übrigens gibt diese Funktion true oder false zurück, nicht 1 oder 0.



  • Also ich habe jetzt meine eigene klasse List aufgebaut.
    In der allgemeinen Vorlage steht diese aber nicht. Über einen istream >> operator soll
    die Liste nun auf verschiedene Eigenschaften überprüft werden.
    In dieser Funktion gelange ich an ein weiteres Verständnisproblem.
    Über die Klasse List mit dem Template rufe ich meine Struktur Node auf. Diese habe ich in der Klasse definiert.. falsch?!
    Jetzt möchte ich hier ein Objekt erstellen, der Compiler wirft mir aber, das er den Bezeichner nicht findet.
    .. Kann mir jemand helfen?

    #include "pch.h"
    #include <iostream>
    
    using namespace std;
    
    template <typename T0>
    class List
    {
    public:
    
    	struct Node
    	{
    		Node* next;
    		T0 data;
    	};
    
    	bool insert(int pos, const T0 & x);
    	Node *head;
    private:
    	int n;
    
    };
    template <typename T0>
    bool List<T0>::insert(int pos, const T0 &x)
    {
    	if ((pos < 0) || (pos > this->n))
    	{
    		return 0;
    	}
    	Node* h = new Node;
    	h->data = x;
    	if (pos == 0)
    	{
    		h->next = head;
    		head = h;
    	}
    	else
    	{
    		Node* q = head;
    		for (int i = 1; i < pos; i++)
    		{
    			q = q->next;
    		}
    		h->next = q->next;
    		q->next = h;
    	}
    	n++;
    	return 1;
    
    }
    
    template<class T0>
    istream & operator>>(istream & is, List<T0> & r)
    {
    	if (r.n > 0)
    	{
    		cout << "Not empty" << endl;
    	}
    	else
    	{
    		int z;
    		cout << "How many?" << endl;
    		is >> z;
    		if (z > 0)
    		{
    			List<T0>::Node* last;
    		}
    	}
    }
    
    


  • Beim kompilieren Deines operator>>() steht noch nicht fest, was List<>::Node sein soll da es da noch keine konkrete Instanziierung des Templates List<> gibt. Du musst dem Compiler verklickern, daß es sich bei List<T0>::Node um einen Typ handelt (Dependent Names):

    typename List<T0>::Node *last;
    

    Auch ist es nicht Aufgabe eines Extraktionsoperators irgendetwas auszugeben. Die dinger sollen einfach nur vom Stream lesen so lange sie das was daherkommt gebrauchen können und dann den Stream (wenn sinnvoll mit gesetztem std::ios::failbit) zurückgeben.

    Eine Liste ohne Zeiger auf ihr Ende ist irgendwie witzlos weil dadurch push_back(), pop() und so Zeugs unnötig lange braucht.



  • Kannst du mir bei der Instanziierung helfen? 😞
    Weiß nciht an welcher Stelle und wie die Syntax genau ist..



  • Darum geht es nicht.

    @spiegelbirke2 sagte in Template, Liste, Funktion:

    List<T0>::Node* last;
    

    ~>

    typename List<T0>::Node* last;
    

    Was anderes. Ich würde bei so Zeugs immer mit den elementarsten Funktionen und bei denen mit den "Ausnahmen" (leere Liste) anfangen:

    #include <utility>
    #include <stdexcept>
    #include <iostream>
    
    template<typename T>
    class List
    {
    	struct Node {  // sollte in der Regel nicht public sein. Interna gehen 
    		T value;   // den Benutzer der List nichts an.
    		Node *prev;
    		Node *next;
    
    		Node(T value = T{}, Node *prev = nullptr, Node *next = nullptr)
    		: value { value },
    		  prev  { prev  },
    		  next  { next  }
    		{}
    	};
    
    	Node *head = nullptr;
    	Node *tail = nullptr;
    	std::size_t length = 0;
    
    public:
    	List() = default;	
    	
    	List(List<T> const &other)
    	{
    		if (!other.length)
    			return;
    
    		head = tail = new Node{ other.head->value };
    		
    		for (Node *write_pos{ head }, *read_pos{ other.head->next }; read_pos; read_pos = read_pos->next, write_pos = write_pos->next)
    			tail = write_pos->next = new Node{ read_pos->value, write_pos };
    
    		length = other.length;
    	}
    
    	friend
    	void swap(List<T> &first, List<T> &second)
    	{
    		using std::swap;
    		swap(head, second.head);
    		swap(tail, second.tail);
    		swap(length, second.length);
    	}
    
    	List<T>& operator=(List<T> other)
    	{
    		swap(*this, other);
    		return *this;
    	}
    
    	void clear()
    	{
    		for (auto current = head; current; ) {
    			auto next = current->next;
    			delete current;
    			current = next;
    		}
    		
    		head = tail = nullptr;
    		length = 0;
    	}
    
    	~List() { clear(); }
    
    	bool empty() const { return !length; }
    
    	void push_front(T const &value)  // Zuerst das Einfachste.
    	{
    		head = new Node{ value, nullptr, head };
    		
    		if (head->next)  // wenn head einen nachfolger hat
    			head->next->prev = head;  // prev des nachfolgers anpassen
    		else
    			tail = head;  // sonst ist das Ding leer und der Schwanz ist der Kopf.
    
    		++length;
    	}
    
    	void push_back(T const &value)
    	{
    		if (!length) {  // push_back() auf eine leere Liste ist das selbe wie push_front()
    			push_front(value);
    			return;
    		}
    
    		tail->next = new Node{ value, tail };
    		
    		if(tail->prev)  // wenn der Schwanz einen Vorgänger hat
    			tail->prev->next = tail;  // den next des Vorgängers anpassen
    
    		tail = tail->next;
    		++length;
    	}
    
    	void insert(std::size_t position, T const &value)
    	{
    		if (position > length)
    			throw std::range_error{ "List<T>::insert(): position out of range!" };
    
    		if (!position) {  // insert an Position 0 ist push_front()
    			push_front(value);
    			return;
    		}
    
    		if (position == length) {  // insert an Position length ist push_back()
    			push_back(value);
    			return;
    		}
    
    		Node *at = head;  // sonst durchlatschen und mitzählen
    		for (std::size_t i{ 1 }; i < position; ++i)
    			at = at->next;
    
    		at->next = new Node{ value, at, at->next };
    		++length;
    	}
    
    	friend
    	std::ostream& operator<<(std::ostream &os, List<T> const &list)
    	{
    		if (list.empty())
    			return os;
    
    		std::cout << list.head->value;
    
    		for (auto current = list.head->next; current; current = current->next)
    			os << ' ' << current->value;
    
    		return os;
    	}
    
    	friend
    	std::istream& operator>>(std::istream &is, List<T> &list)
    	{
    		list.clear();
    
    		// solange Ts von is gelesen werden können an die Liste anhängen:
    		for (T value; is >> value; list.push_back(value));
    
    		return is;
    	}
    };
    


  • Okay.. ja klar, Sorry..
    Was ich halt nicht verstehe ist, dass der Code eine Musterlösung von unserem Prof ist. Ich habe es 1zu1 nachprogrammiert.Die Klasse List fehlt halt und ich glaube, dass es auch 1zu1 möglich sein müsste, den Code zu kompilieren, ohne 'typename' , mit einer selbst geschriebenen Klasse.



  • Wenn Du den operator>>() als friend innerhalb der Klasse definierst, geht es ohne typename.



  • @spiegelbirke2 Visual C++ frisst den Code auch ohne typename - trotz dem er falsch ist. Und ganz aktuelle Visual C++ Versionen spucken dir hier ebenfalls einen Fehler aus wenn du mit /permissive- oder /Zc:twoPhase compilierst.

    Und GCC und Clang werden es grundsätzlich nicht compilieren. Ausgenommen vielleicht sehr alte Versionen oder evtl. Clang im Visual C++ Kompatibilitätsmodus.



  • @hustbaer Das heißt auch bei meiner "Lösung" für mit ohne typename müsste typename hin?



  • @Swordfish Ehrlich gesagt: weiss ich nicht. Ich hab' mich auf den von @spiegelbirke2 geposteten Code bezogen. Ich schätze die Version mit friend dürfte OK sein. Vielleicht 🙂



  • @hustbaer sagte in Template, Liste, Funktion:

    Vielleicht 🙂

    Ach, diese Sprache muss man einfach lieben! 🙂



  • Naja ne das wird schon klar aus dem Standard hervorgehen. Hab das nicht nachgelesen. Es fressen dann aber alle Compiler die ich probiert habe: MSVC (auch mit /permissive-), GCC 8.3 und Clang 8.0.



  • Mit meinem Kommentar bezog ich mich nicht darauf daß es nirgends geschrieben steht, sondern darauf daß keine S** auf die schnelle rausfinden kann wo. *lol*



  • Naja, hab's nicht versucht, aber auf mich bezogen wirst du Recht haben. @Columbo findet das sicher in < 1 Minute 🙂


  • Mod

    @hustbaer Aus [basic.lookup.unqual]:

    Name lookup for a name used in the definition of a friend function defined inline in the class granting friendship shall proceed as described for lookup in member function definitions.

    Und [temp.dep.type]/1:

    A name refers to the current instantiation if it is ... in the definition of a primary class template or a member of a primary class template, the name of the class template followed by the template argument list of the primary template (as described below) enclosed in <> (or an equivalent template alias specialization),


Anmelden zum Antworten