Funktionstemplate, das am häufigsten auftauchenden Wert in einem Container findet

[Mizar]

Guten Abend :),

da ich seit langem endlich mal wieder etwas mehr Zeit habe, habe ich den "C++-Primer" weitergelesen und beschäftige mich nun seit ein paar Tagen mit Templates. Dazu wurde in dem Buch folgende Übungsaufgabe gestellt:

C++-Primer schrieb:

Übung 16.12: Schreiben Sie ein Funktionstemplate, das ein paar Werte übernimmt, die Iteratoren unbekannten Typs repräsentieren. Suchen Sie den Wert, der am häufigsten in der Folge vorkommt.

Meine Lösung sieht nun so aus:

template <typename Iter>
Iter mostOccurrence(Iter& beg, Iter& end)
{
	typedef std::vector< std::pair<Iter, unsigned int> > OccurVec;
	OccurVec occurrence;
	while(beg != end) {
		for(OccurVec::iterator it(occurrence.begin()), it_end(occurrence.end()); it != it_end; ++it) {
			if(*beg == *(it->first)) {
				++(it->second);
				break;
			} else if(it == it_end - 1) {
				occurrence.push_back(std::make_pair(beg, 1));
				break;
			}
		}
		if(occurrence.empty()) {
			occurrence.push_back(std::make_pair(beg, 1));
		}
		++beg;
	}
	unsigned int count(1);
	Iter ret_iter(end);
	for(OccurVec::iterator it(occurrence.begin()), it_end(occurrence.end()); it != it_end; ++it) {
		if(it->second > count) {
			count = it->second;
			ret_iter = it->first;
		}
	}
	return ret_iter;
}

Und das folgende kleine Testprogramm liefert mir auch die erwartete Ausgabe:

int main()
{
	std::vector<int> ivec;
	ivec.push_back(77);
	ivec.push_back(78);
	ivec.push_back(79);
	ivec.push_back(79);
	ivec.push_back(80);

	std::vector<int>::iterator vec_result(mostOccurrence(ivec.begin(), ivec.end()));
	if(vec_result != ivec.end())
		std::cout << "Am meisten kam das Element " << *vec_result << " vor." << std::endl;
	else
		std::cout << "Nichts gefunden." << std::endl;

    return 0;
}

Ausgabe:

Am meisten kam das Element 79 vor.

Meine Frage ist nun gewissermaßen, wie ihr die Aufgabe lösen würdet, da mir meine Lösung irgendwie lang vorkommt. Vielleicht kennt ihr bessere und / oder kürzere Löungsansätze. Ich weiß, dass es recht ungewöhnlich ist eine Frage dieser Art zu stellen, aber ich verspreche mir davon in Sachen generischer Programmierung etwas dazuzulernen, da ich mich, wie eingangs erwähnt, noch nicht sehr lange damit beschäftige :).

EDIT: Upps, einen kleiner Fehler im Code berichtigt.

[volkard]

Kommt drauf an.
Entweder wie Du, nur daß OccurVec eine map wäre. Die erste Schleife von Z6 bis Z20 zerfällt dann zu

for(beg != end ; ++beg)
  ++OccurMap[*beg];

Wäre die Menge aber schon sortiert oder meistens oder beinahe oder so, würde ich sie vielleicht sortieren und von vorne nach hinten durchlaufen und den längsten bereich gleicher Werte suchen.

[Gilder]

Wenn der Container verändert werden darf kannstes ja so machen: (sonst vorher ne kopie vom container anlegen)

template <typename Iter>
Iter mostOccurrence(Iter beg, Iter end)
{
    Iter Max = beg;
    Iter it = unique ( beg, end );
    unsigned int MaxCounter = 0;

    for( ; beg != it; ++beg)
    {
        unsigned int counter = count ( beg, it, *beg );
        if ( counter > MaxCounter )
            Max = beg;
    }

    return Max;
}

[Gilder]

*edit

template <typename Iter>
Iter mostOccurrence(Iter beg, Iter end)
{
    Iter Max = beg;
    Iter it = unique ( beg, end );
    unsigned int MaxCounter = 0;

    for( ; beg != it; ++beg)
    {
        unsigned int counter = count ( beg, it, *beg );
        if ( counter > MaxCounter )
        {
            Max = beg;
            MaxCounter = counter;
        }
    }

    return Max;
}

So sollte es stimmen

[Mizar]

Oh man, wenn ich mir eure beiden Lösungsansätze (vielen Dank dafür) so anschaue, dann merke ich erstmal wie kompliziert ich mir das ganze gemacht habe. Vor allem auf die std::map hätte ich eigentlich kommen müssen. Naja, ich habe wohl noch einen weiten Weg zu gehen :).

[Gilder]

Irgendwie klappt mein Ansatz nicht (und ja, ich weis dass in zeile 10 "end" statt "it" gehört).
Aber zur Not der das auch (ist halt nicht besonders performant), aber ändert den container nicht und gibt - wie man es aus der stl gewohnt ist - einen Iterator auf das erste object zurück, dass am häufigsten vorkommt

template <typename Iter>
Iter mostOccurrence(Iter beg, Iter end)
{
    Iter Max = beg;
    unsigned int MaxCounter = 0;

    for( ; beg!=end; ++beg)
    {
        unsigned int counter = count ( beg, end, *beg );
        if ( counter > MaxCounter )
        {
            Max = beg;
            MaxCounter = counter;
        }
    }
    return Max;
}

[Dravere]

Hier ein Eleminationsverfahren oder zumindest nenne ich es so. Es verändert den Container nicht und erstellt auch keine Kopien von den Werten im Container, was unter Umständen sehr teuer sein kann. Es setzt auch nichts anderes ausser den Vergleichsoperator für die Werte im Container voraus. Die Laufzeit sollte auch angemessen sein:

#include <list>
#include <string>
#include <utility>
#include <iostream>
#include <iterator>

#include <cstddef>

template<typename Iter>
std::pair<Iter, std::size_t> mostOccurrence(Iter beg, Iter end)
{
    std::list<Iter> iterList;

    for(Iter iter = beg; iter != end; ++iter)
    {
        iterList.push_back(iter);
    }

    Iter maxIter;
    std::size_t count;
    std::size_t maxCount = 0;

    std::list<Iter>::iterator endIterList = iterList.end();

    while(!iterList.empty())
    {
        count = 1;
        std::list<Iter>::iterator iter = iterList.begin();
        std::iterator_traits<Iter>::reference findVal = *(*iter);

        for(++iter; iter != endIterList; ++iter)
        {
            if(*(*iter) == findVal)
            {
                ++count;
                iter = iterList.erase(iter);
            }
        }

        if(count > maxCount)
        {
            maxIter = *iterList.begin();
            maxCount = count;
        }

        iterList.pop_front();
    }

    return std::pair<Iter, std::size_t>(maxIter, maxCount);
}

int main()
{
    std::string str = "Hello World! How are you?";

    std::pair<std::string::iterator, std::size_t> result
        = mostOccurrence(str.begin(), str.end());

    std::cout
        << "Most occurrence: " << *result.first
        << " Total: " << result.second << std::endl;

    return 0;
}

Der Code sollte selbsterklärend sein.

Grüssli

PS: Ich freue mich auf die neue Bedeutung von auto ...

[volkard]

Dravere schrieb:

Hier ein Eleminationsverfahren oder zumindest nenne ich es so.

Ungefähr das gleiche wäre passiert, wenn man zu Gilders Code einen vector<bool> dazugebaut hätte, der vermerkt, welche Elemente nicht mehr gezählt werden müssen.

Die Laufzeit sollte auch angemessen sein.

Leider nur, wenn wenige verschiedene Werte vorkommen.

PS: Ich freue mich auf die neue Bedeutung von auto ...

Ich auch.
*hüpf*

[Dravere]

volkard schrieb:

Dravere schrieb:

Die Laufzeit sollte auch angemessen sein.

Leider nur, wenn wenige verschiedene Werte vorkommen.

Naja, das ist auch irgendwo logisch. Ist bei der Lösung mit std::map auch nicht anders. Gäbe es überhaupt eine Möglichkeit eine Verbesserung durchzuführen, wenn es viele verschiedene Werte hat?

Grüssli

[volkard]

Dravere schrieb:

volkard schrieb:

Dravere schrieb:

Die Laufzeit sollte auch angemessen sein.

Leider nur, wenn wenige verschiedene Werte vorkommen.

Naja, das ist auch irgendwo logisch. Ist bei der Lösung mit std::map auch nicht anders.

Bei 1 Million verschiedenen Werten hat man mit der map nur 20 Millionen Vergleiche oder so, statt 500 Milliarden.

[Dravere]

volkard schrieb:

Bei 1 Million verschiedenen Werten hat man mit der map nur 20 Millionen Vergleiche oder so, statt 500 Milliarden.

Und dann kommt die grosse Frage, was ist teuerer? Der Vergleich oder die Kopie? Und in welchem Verhältnis?

Aber da kommt mir eine andere Idee ...

#include <map>
#include <string>
#include <utility>
#include <iostream>

#include <cstddef>

template<typename Iter>
std::pair<Iter, std::size_t> mostOccurrence(Iter beg, Iter end)
{
    // CompareHelper
    struct CompareHelper
    {
        bool operator ()(Iter lhs, Iter rhs)
        {
          return *lhs < *rhs;
        }
    };

    typedef std::map<Iter, std::size_t, CompareHelper> Occurrence;
    typedef typename Occurrence::iterator OccurrenceIterator;
    Occurrence occurrence;

    for(; beg != end; ++beg)
    {
      ++occurrence[beg];
    }

    OccurrenceIterator iter = occurrence.begin();
    OccurrenceIterator mapEnd = occurrence.end();

    OccurrenceIterator maxIter = iter;

    for(++iter; iter != mapEnd; ++iter)
    {
        if(iter->second > maxIter->second)
        {
          maxIter = iter;
        }
    }

    return *maxIter;
}

int main()
{
    std::string str = "Hello World! How are you? Oooh!";

    std::pair<std::string::iterator, std::size_t> result
        = mostOccurrence(str.begin(), str.end());

    std::cout
        << "Most occurrence: " << *result.first
        << " Total: " << result.second << std::endl;

    return 0;
}

Kombination

Grüssli

[volkard]

Kombination

[Mizar]

Ich habe mich an volkards Ansatz mit der std::map orientiert und versucht damit das Funktionstemplate zu schreiben, was mir allerdings misslang (mein Kopf war wohl noch zu voll :p). Und nun sehe ich in Draveres zuletzt geposteten Code einen Komparator und möchte am liebsten meinen Kopf gegen die Tischkante hauen, weil nämlich in dem vorhergehenden Kapitel des Buches eine beispielhafte Anwendung eines Komparators gezeigt wurde (dort für ein std::set ) und ich für das Lösen dieser Aufgabe noch gar nicht an diesen gedacht hatte.

Ich möchte mich nochmal für alle Codebeispiele bedanken, da mich diese ein gutes Stück voran gebracht haben, was mir bei den nächsten Übungsaufgaben sicherlich weiterhelfen wird :).