Priority Queues με classes/stuctures

TheRammer · 31 Μαρτίου 2015

Θελω να χρησημοποιήσω ενα priority queue αλλα δεν ξερω πως γινεται περα απο μεταβλητες τυπου int . συγκεκριμένα θελω να συγκρινει μια μεταβλητη μεσα στο structure για να υπολογίσει με ποιά σειρα θα ειναι τα στοιχεία στο queue . εδω ειναι το struct μου :

typedef struct
{
	char Information;
	int compareValue;
}RandomStruct;

Σε αυτην την περιπτωση η μεταβλητη η οποία θα χρησημοποιήται για συγκριση ειναι η "compareValue" .

Παρακαλω εξηγηστε το σε λιγο περισσοτερο βαθος γιατι οταν το googlara δεν καταλαβα πολλα πραγματα για την χρηση του

Kercyn · 31 Μαρτίου 2015

Πρέπει να υλοποιήσεις μια δική σου compare η οποία θα συγκρίνει 2 πράγματα από αυτό που θες και θα σου επιστρέφει ποιο είναι το "μεγαλύτερο".

Επεξ/σία 1 Απριλίου 2015 από Kercyn

defacer · 1 Απριλίου 2015

Γλώσσα;

gon1332 · 1 Απριλίου 2015

C-like. Οk, καταλαβαίνω τι εννοείς.

Το πιο σημαντικό είναι αν αυτό που χρειάζεται είναι μόνο μία priority queue ή

μία priority queue για το τάδε project δικτύων/λειτουργικών/ο,τιδήποτε. Παίζει

ρόλο.

TheRammer · 1 Απριλίου 2015

Γλώσσα;

C++ . sorry νομιζα οτι ενοείται

Kercyn · 1 Απριλίου 2015

Δες το πρώτο αποτέλεσμα του Google για "priority queue c++ custom compare".

wink wink

gon1332 · 1 Απριλίου 2015

C++ . sorry νομιζα οτι ενοείται

https://en.wikipedia.org/wiki/Struct_(C_programming_language)

Το ερώτημα παραμένει. Θέλεις να υλοποιήσεις απλά μία Queue,

ή τη θες για κάποιο απότερο σκοπό;

TheRammer · 1 Απριλίου 2015

Δες το πρώτο αποτέλεσμα του Google για "priority queue c++ custom compare".

wink wink

Παρακαλω εξηγηστε το σε λιγο περισσοτερο βαθος γιατι οταν το googlara δεν καταλαβα πολλα πραγματα για την χρηση του

https://en.wikipedia.org/wiki/Struct_(C_programming_language)

Το ερώτημα παραμένει. Θέλεις να υλοποιήσεις απλά μία Queue,

ή τη θες για κάποιο απότερο σκοπό;

Just a queue . Απο αυτα της STL (built in library)

Kercyn · 1 Απριλίου 2015

Σε μια priority queue βάζεις διάφορα (ίδιου τύπου) στοιχεία και αυτά ταξινομούνται από το μεγαλύτερο στο μικρότερο. Το αν ένα στοιχείο είναι μεγαλύτερο από ένα άλλο εξαρτάται από το είδος του. Για τους θετικούς αριθμούς, πχ, λέμε ότι ένας αριθμός Α είναι μεγαλύτερος από έναν αριθμό Β αν το Α απέχει περισσότερο από το 0 απ' ό,τι το Β. Επειδή οι αριθμοί χρησιμοποιούνται για πάρα πολλά πράγματα, υπάρχει ήδη μια υλοποίηση που συγκρίνει 2 αριθμούς και σου λέει ποιος είναι μεγαλύτερος.

Όταν όμως θες να συγκρίνεις 2 πράγματα που δεν είναι αριθμοί (από strings μέχρι custom κλάσεις) τότε θα πρέπει να πεις εσύ στο priority queue πότε ένα αντικείμενο είναι "μεγαλύτερο" από ένα άλλο. Εδώ είναι που έρχεσαι και φτιάχνεις μια δικιά σου συνάρτηση που θα κάνει ακριβώς αυτό το πράγμα∙ θα παίρνει 2 αντικείμενα αυτής της κλάσης και θα σου λέει ποιο είναι το μεγαλύτερο, έτσι ώστε το queue σου να ξέρει ποιο πρέπει να μπει πριν από ένα άλλο.

Για τα strings υπάρχει έτοιμη συνάρτηση compare οπότε χρειάζεται να φτιάξεις μια δικιά σου μόνον άμα δε σε ικανοποιεί η ήδη έτοιμη.

gon1332 · 1 Απριλίου 2015

Για τα strings υπάρχει έτοιμη συνάρτηση compare οπότε χρειάζεται να φτιάξεις μια δικιά σου μόνον άμα δε σε ικανοποιεί η ήδη έτοιμη.

@OP Επίσης για τα C++ strings μπορείς να χρησιμοποιείς και τους operators ==, >, < κλπ.

παπι · 1 Απριλίου 2015

Ενα παρα πολυ καλο site http://en.cppreference.com/w/

TheRammer · 1 Απριλίου 2015

Σε μια priority queue βάζεις διάφορα (ίδιου τύπου) στοιχεία και αυτά ταξινομούνται από το μεγαλύτερο στο μικρότερο. Το αν ένα στοιχείο είναι μεγαλύτερο από ένα άλλο εξαρτάται από το είδος του. Για τους θετικούς αριθμούς, πχ, λέμε ότι ένας αριθμός Α είναι μεγαλύτερος από έναν αριθμό Β αν το Α απέχει περισσότερο από το 0 απ' ό,τι το Β. Επειδή οι αριθμοί χρησιμοποιούνται για πάρα πολλά πράγματα, υπάρχει ήδη μια υλοποίηση που συγκρίνει 2 αριθμούς και σου λέει ποιος είναι μεγαλύτερος.

Όταν όμως θες να συγκρίνεις 2 πράγματα που δεν είναι αριθμοί (από strings μέχρι custom κλάσεις) τότε θα πρέπει να πεις εσύ στο priority queue πότε ένα αντικείμενο είναι "μεγαλύτερο" από ένα άλλο. Εδώ είναι που έρχεσαι και φτιάχνεις μια δικιά σου συνάρτηση που θα κάνει ακριβώς αυτό το πράγμα∙ θα παίρνει 2 αντικείμενα αυτής της κλάσης και θα σου λέει ποιο είναι το μεγαλύτερο, έτσι ώστε το queue σου να ξέρει ποιο πρέπει να μπει πριν από ένα άλλο.

Για τα strings υπάρχει έτοιμη συνάρτηση compare οπότε χρειάζεται να φτιάξεις μια δικιά σου μόνον άμα δε σε ικανοποιεί η ήδη έτοιμη.

Παρακαλω εξηγηστε το σε λιγο περισσοτερο βαθος

Αυτο το καταλαβα αλλα θελω λιγη περισσότερη εξηγηση στην συνταξη του κωδικα γιατι δεν καταλαβα αρκετα απο το stack overflow . Φυσικα μπορώ να κανω copy paste τα παντα απο το stack overflow αλλα θελω και να ξερω πως δουλευει ο κωδικας γιατι μερικά πραγματα με πμερδεψαν οπως : "operator" , και η συνταξη στο declaration του priority queue

Kercyn · 1 Απριλίου 2015

Δες εδώ. Όταν φτιάχνεις ένα priority queue, το πρώτο argument είναι το τι θα έχει μέσα, το δεύτερο ο container που θες να χρησιμοποιήσεις και το τρίτο είναι η συνάρτηση σύγκρισης. Ο container και η συνάρτηση είναι προαιρετικά, αλλά στην περίπτωσή σου χρειάζεσαι συνάρτηση, οπότε πρέπει να βάλεις και τα τρία.

παπι · 2 Απριλίου 2015

Αυτο το καταλαβα αλλα θελω λιγη περισσότερη εξηγηση στην συνταξη του κωδικα γιατι δεν καταλαβα αρκετα απο το stack overflow . Φυσικα μπορώ να κανω copy paste τα παντα απο το stack overflow αλλα θελω και να ξερω πως δουλευει ο κωδικας γιατι μερικά πραγματα με πμερδεψαν οπως : "operator" , και η συνταξη στο declaration του priority queue

Θελω να βγαλω το sum απο ενα array, πινκας, list, πες το οπως θες

Εδω μια υλοποιηση

(c like coding)

int sum(std::vector<int> vector)
{
	int s = 0;
	for (int i = 0; i < vector.size(); i++)
	{
		s += vector[i];
	}
	return s;
}


int main(int argc, char* argv[])
{
	std::vector<int> vector{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	int s = sum(vector);

	std::cout << s;
	return 0;
}

Θελω αυτο να δουλευει και για float/doble/long etc

template <typename T>
T sum(std::vector<T> vector)
{
	T s = 0;
	for (int i = 0; i < vector.size(); i++)
	{
		s += vector[i];
	}
	return s;
}


int main(int argc, char* argv[])
{
	std::vector<int> vector{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::vector<double> doubleVector{ 1., 2., 3., 4., 5., 6., 7., 8., 9., 10. };

	int s = sum<int>(vector);
	double ds = sum<double>(doubleVector);

	std::cout
		<< s
		<< std::endl
		<< ds;
	return 0;
}

Εδω εβαλα ενα template type. Δηλαδη το T θα το δηλωσω στο καλεσμα της συναρτησης. Με απλα λογια, το sum<int> μας λεει οτι, οπου υπαρχει το Τ, βαλε int.

Για να μην γραφω μεγαλο κωδικα, το παραπανω μπορει να γινει αυτοματα, αντι sum<int>(vector) μπορεις να την καλεσεις ετσι sum(vector). Επειδη υπαρχει μια δηλωση του τυπου (αυτο στο vector).

Δηλαδη το παραπανω θα γινει ετσι

template <typename T>
T sum(std::vector<T> vector)
{
	T s = 0;
	for (int i = 0; i < vector.size(); i++)
	{
		s += vector[i];
	}
	return s;
}


int main(int argc, char* argv[])
{
	std::vector<int> vector{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::vector<double> doubleVector{ 1., 2., 3., 4., 5., 6., 7., 8., 9., 10. };

	int s = sum(vector);
	double ds = sum(doubleVector);

	std::cout
		<< s
		<< std::endl
		<< ds;
	return 0;
}

Τωρα θελω αυτο να δουλευει και για απλο array ή list ή οτι να'ναι.

template <
	typename T,
	typename It
>
T sum(It first, It end)
{
	T s = 0;
	for (; first != end; ++first)
	{
		s += *first;
	}
	return s;
}


int main(int argc, char* argv[])
{
	std::vector<int> vector{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::vector<double> doubleVector{ 1., 2., 3., 4., 5., 6., 7., 8., 9., 10. };
	std::list<int> list{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	int s = sum<int>(vector.begin(),vector.end());
	double ds = sum<double>(doubleVector.begin(), doubleVector.end());
	int listSum = sum<int>(list.begin(), list.end());

	std::cout
		<< s
		<< std::endl
		<< ds
		<< std::endl
		<< listSum
		;
	return 0;
}

Εδω εβαλα αλλο ενα template type στη sum. Σε αυτο το σημειο δεν θα λεμε vector list ή οτι να'ναι, αλλα θα λεμε range. Ενα range στην stl εχει standar δυο μεθοδους. Μια begin και μια end ( +cbegin, cend που ειναι const version). Αυτες επιστρεφουν μια μεταβλητη τυπου range::iterator (πχ std::vector::iterator it = vec.begin() ). Αυτα ουσιαστικα ειναι iterators, δηλαδη ενα μεγαλο κεφαλαιο της stl.

λιγα πραματα για iterators, τα αλλα δες στο google.

Ο iterator μπορει

1) να γινει dereference, δηλαδη το *it μας επιστρεφει την τιμη που εχει (ή το object struct whateva)

2) να δειξει στο επομενο, ++it ειναι το επομενο iterator

3) Να συγκριθει με εναν αλλον, πχ it != it1

(ουσιαστικα ειναι κατι σα pointer)

Εδω μη σε σκαλωσεις με το sum<int>, το It ειναι γνωστο εφοσον περναει στη συναρτηση, το T ειναι αγνωστο για αυτο και βαζω μονο το int/double η κανονικη δηλωση ειναι sum<int,std::vector::iterator>(begin,end).

Τωρα εγω θελω αυτη η συναρτηση, εκτος το να κανει sum, να μου βγαζει και το συνολο πολλαπλασιαζοντας το. (αντι 1 + 2 + 3.. να βγαζει το αποτελεσμα απο το 1 * 2 * 3... )

template <
	typename T,
	typename It,
	typename Functor
>
T acc(It first, It end, T init, Functor fn)
{

	for (; first != end; ++first)
	{
		init = fn(init, *first);
	}
	return init;
}

template <typename T>
struct plus
{
	T operator ()(T a, T 
	{
		return a + b;
	}
};
template <typename T>
struct multiplies
{
	T operator ()(T a, T 
	{
		return a * b;
	}
};


int main(int argc, char* argv[])
{
	std::vector<int> vector{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
	std::vector<double> doubleVector{ 1., 2., 3., 4., 5., 6., 7., 8., 9., 10. };
	std::list<int> list{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

	int s = acc(vector.begin(), vector.end(), 0, plus<int>());
	double ds = acc(doubleVector.begin(), doubleVector.end(), 0., plus<int>());
	int listSum = acc(list.begin(), list.end(), 0, plus<int>());

	int ms = acc(vector.begin(), vector.end(), 1, multiplies<int>());
	std::cout
		<< s
		<< std::endl
		<< ds
		<< std::endl
		<< listSum
		<< std::endl
		<< ms
		;


	return 0;
}

Για αρχη αλλαξα ονομα, εφοσον δεν ειναι sum. Επειτα εβαλα αλλο ενα typename type Functor το οποιο δρα ως εναν binary operator ( + * - / etc). Και τελος εβαλα δυο struct (plus, multiplies) τα οποια αυτα struct ειναι τα λεγομενα fanctors. Δηλαδη μια συναρτηση που εχει state. Πως το κανουμε αυτο, φτιαχνοντας ενα struct/class και κανοντας overload τους parenthesis operators. Ετσι το

plus<int> p;
std::cout << p(1, 2);

δεν κανει τιποτα αλλο απο το να μας επιστρεφει το 1 + 2

απλο μεν, αλλα αρκετα χρησιμο.

Με αυτα και αυτα, εφτιξα αυτο

Εαν τα καταλαβες αυτα (προσεξε, εβαλα αγγλικους ορους για να googlareis) τοτε πας εδω

και βλεπεις οτι η priority παιρνει τον type, τον container (ο οποιος ειναι vector) και ενα fanctor ως compare που ειναι το std::less

τι ειναι το std::less???

		// TEMPLATE STRUCT less
template<class _Ty = void>
	struct less
		: public binary_function<_Ty, _Ty, bool>
	{	// functor for operator<
	bool operator()(const _Ty& _Left, const _Ty& _Right) const
		{	// apply operator< to operands
		return (_Left < _Right);
		}
	};

copy paste απο το msvc 13

Σύνδεση

Priority Queues με classes/stuctures

Προτεινόμενες αναρτήσεις

TheRammer

Kercyn

defacer

gon1332

TheRammer

Kercyn

gon1332

TheRammer

Kercyn

gon1332

παπι

TheRammer

Kercyn

παπι

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

Σύνδεση