✔ Template in Templates und Iteratoren

[Guillermo]

Hi tutorials.de Benutzer,

ich versuche gerade ein kleine Templatefunktion zu implementieren. Ich will dass die Funktion zwei Parameter hat, und zwar zwei Iteratoren unbestimmten Typs (Ich weiß also beim Kompilieren noch nicht ob es Vektoren, eine List o.Ä. ist.). Die Aufgabe der Funktion ist den Wert in dem iterierbaren Container zu finden der am häufigsten vorkommt. Hier ein Beispiel wie ich die Funktion aufrufen möchte und wie deren Ergebnisse aussehen sollen (Ich nennen die Funktion "most_frequent"):

std::vector<int> v = {1,1,1,2};
most_frequent(v.begin(), v.end()); // Soll 1 zurückgeben, Typ int

std::list<std::string> l = {"hallo","welt","hallo"};
most_frequent(l.begin(), l.end()); // Soll "hallo" zurückgeben, Typ std::string

Mein Ansatz sieht folgendermaßen aus:

template <typename E, template<typename , typename> class C>
E most_frequent(typename C<E, std::allocator<E> >::iterator &begin, typename C<E, std::allocator<E> >::iterator &end) {
	return NULL;
}

Wie ich die Funktion letztlich implementiere ist erstmal zweitrangig, wichtig ist für mich primär das Template. Es kompliert, versuche ich aber die Funktion wie oben aufzurufen, bekomme ich einen Fehler dass keine passende Funktion gefunden werden kann.

main5.cpp: In function ‘int main(int, char**)’:
main5.cpp:35:34: error: no matching function for call to ‘most_frequent(std::vector<int>::iterator, std::vector<int>::iterator)’
main5.cpp:35:34: note: candidate is:
main5.cpp:18:3: note: template<class E, template<class, class> class C> E most_frequent(typename C<E, std::allocator<_T1> >::iterator, typename C<E, std::allocator<_T1> >::iterator)
main5.cpp:18:3: note: template argument deduction/substitution failed:
main5.cpp:35:34: note: couldn't deduce template parameter ‘E’

Ich glaub ich steig da noch nicht ganz durch. Was mache ich falsch? Gibt es vielleicht bessere Ansätze? Ich habe es auch mit einem allg. Iteratortyp probiert, ich brauche aber unbedingt den generischen Typ des Inhaltes der Container (oben int und std::string) weil ich die Anzahl der gleichen Werte z.B. in einem Hash speichern will.

Über Anregungen oder Hilfe würde ich mich sehr freuen!
Vielen Dank schon mal,
Guillermo

 

[Muepe32]

Hallo Guillermo

Verwende hier doch die gleiche Variante wie in der STL:

template<typename FwdIter>
FwdIter most_frequent(FwdIter first, FwdIter last) {
}

Du verwendest dann first und last wie du willst mit den entsprechenden Operatoren die du implementiert haben willst vom übergebenen Typen (++, * und so) und der Aufrufer muss einen Typen übergeben, der diese dann unterstützt.

Gruss
Muepe

 

[Guillermo]

Hi Muepe,

danke für deine Antwort! Das hatte ich oben ja mit "einem allg Iteratortyp" gemeint, hab mich wohl unglücklich ausgedrückt. Ich würde es gerne so haben dass ich den Typ den die Container beherbergen nicht explizit angeben muss (Also die Funktion genau so aufrufen wie ich es geschrieben habe, ohne generische Typen anzugeben). Geht das irgendwie?

Mit deiner Variante würde meine Funktion jetzt so aussehen:

template<typename E, typename FwdIter>
E most_frequent(FwdIter first, FwdIter last) {

	std::map<E, int> map;

	for(FwdIter current = first; current != last; ++current) {
		map[*current]++;
	}

	auto pr = std::max_element(map.begin(), map.end(), [](const std::pair<E, int>& p1, const std::pair<E, int>& p2) { return p1.second < p2.second; });
	return pr->first;
}

Hier ein Anwendungsbeispiel:

int main(int argc, char **argv) {

	// Test with vector<int>
	std::vector<int> v = {1,1,1,2,2,2,2};
	int max_int = most_frequent<int, std::vector<int>::iterator>(v.begin(), v.end()); 
	std::cout << max_int << std::endl;

	// Test with list<string>
	std::list<std::string> l = {"Hallo", "Welt", "Hallo"};
	std::string max_string = most_frequent<std::string, std::list<std::string>::iterator>(l.begin(), l.end());
	std::cout << max_string << std::endl;

	return 0;
}

Viele Grüße,
Guillermo

 

[Cromon]

Hallo Guillermo

Du solltest besser einen Iterator zurückgeben und nicht den effektiven Wert. Das ermöglich dir auch zum Beispiel last zurückzugeben wenn irgendwas schief läuft oder sonst etwas. Du musst so überhaupt kein Template angeben.

Beispiel:

template<typename FwdItr>
FwdItr most_frequent(FwdItr first, FwdItr last) {
	FwdItr tmpFirst = first;
	++first;

	while(first != last) {
		++first;
		if(*first == *tmpFirst)
			return first;
	}

	return last;
}

int main() {
	std::vector<int> vInt;
	vInt.push_back(3);
	vInt.push_back(2);
	vInt.push_back(3);
	vInt.push_back(2);

	auto freqInt = most_frequent(vInt.begin(), vInt.end());
	std::cout << *freqInt << std::endl;

	std::vector<std::string> vStr;
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("hallo Tutorials.de!");
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("Tschüss Tutorials.de!");

	auto freqStr = most_frequent(vStr.begin(), vStr.end());
	std::cout << *freqStr << std::endl;
}

Ausgabe:
3 und "Hallo Tutorials.de!"

/Edit:
Oder mit deiner Version von most_frequent:

template<typename FwdItr>
FwdItr most_frequent(FwdItr first, FwdItr last) {
	std::map<FwdItr::value_type, int> countMap;
	FwdItr cur = first;

	while(cur != last) {
		countMap[*(cur++)]++;
	}

	std::map<FwdItr::value_type, int>::iterator maxVal = std::max_element(countMap.begin(), countMap.end(), [](const std::pair<FwdItr::value_type, int>& p1, const std::pair<FwdItr::value_type, int>& p2) { return p1.second < p2.second; });

	cur = first;
	while(cur != last)
	{
		if(*(cur++) == maxVal->first)
			return cur;
	}

	return last;
}

int main() {
	std::vector<int> vInt;
	vInt.push_back(3);
	vInt.push_back(2);
	vInt.push_back(3);
	vInt.push_back(2);

	auto freqInt = most_frequent(vInt.begin(), vInt.end());
	std::cout << *freqInt << std::endl;

	std::vector<std::string> vStr;
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("hallo Tutorials.de!");
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("Tschüss Tutorials.de!");

	auto freqStr = most_frequent(vStr.begin(), vStr.end());
	std::cout << *freqStr << std::endl;

	std::cin.get();
}

Oder wenn du die Iteratoren nicht willst:

template<typename FwdItr>
typename FwdItr::value_type most_frequent(FwdItr first, FwdItr last) {
	std::map<FwdItr::value_type, int> countMap;
	FwdItr cur = first;

	while(cur != last) {
		countMap[*(cur++)]++;
	}

	std::map<FwdItr::value_type, int>::iterator maxVal = std::max_element(countMap.begin(), countMap.end(), [](const std::pair<FwdItr::value_type, int>& p1, const std::pair<FwdItr::value_type, int>& p2) { return p1.second < p2.second; });

	return maxVal->first;
}

int main() {
	std::vector<int> vInt;
	vInt.push_back(3);
	vInt.push_back(2);
	vInt.push_back(3);
	vInt.push_back(2);

	auto freqInt = most_frequent(vInt.begin(), vInt.end());
	std::cout << freqInt << std::endl;

	std::vector<std::string> vStr;
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("hallo Tutorials.de!");
	vStr.push_back("Hallo Tutorials.de!");
	vStr.push_back("Tschüss Tutorials.de!");

	auto freqStr = most_frequent(vStr.begin(), vStr.end());
	std::cout << freqStr << std::endl;

	std::cin.get();
}

 

[Guillermo]

H Cromon,

das sieht viel besser aus, und darüber habe ich auch schon nachgedacht, nur brauche ich den Typ ja unbedingt für die Map. Deine Funktion macht ja leider noch nicht das was ich will. Und die Iteratoren kann ich in der Map ja nicht verwenden weil sie obwohl die Elemente auf die sie zeigen den gleichen Wert haben nicht gleich sind, sie also für diesen Falls als Schlüssel ungeeignet sind.. Gibts da trotzem eine Möglichkeit wie ich einen Iterator zurückgeben kann aber die Map verwenden kann?

Viele Grüße,
Guillermo

 

[Cromon]

In der Map werden ja nicht die Iteratoren verwendet sondern die Werte. countMap[*cur]

Das relevante ist da das *, damit wird der Wert des Iterators genommen.

 

[Guillermo]

Hi Cromin,

dass ich mich value_type den Typ des Elements bekomm auf das der Iterator zeigt wusste ich nicht, vielen Dank! Deine zweite Version ist also genau die die ich gesucht habe!

Viele Grüße,
Guillermo