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

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

*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 :).

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 :).