map Inhalt wrid sortiert, wie unterbinden?

Das das klever ist habe ich nicht gesagt. ich habe nur versucht eine möglichkeit zur ursprünglichen frage bereit zustellen. ich hätte wahrscheinlich einen anderen ansatzt gewählt. da muss ich dir recht geben! Genauso finde ich es nicht gut eine map für solche zwecke zu "missbrauchen"...

lucky_tux schrieb:

Das das klever ist habe ich nicht gesagt. ich habe nur versucht eine möglichkeit zur ursprünglichen frage bereit zustellen. ich hätte wahrscheinlich einen anderen ansatzt gewählt. da muss ich dir recht geben! Genauso finde ich es nicht gut eine map für solche zwecke zu "missbrauchen"...

Und ich nicht, dass du so ne Lösung überhaupt vorschlägst :p

lucky_tux schrieb:

Das das klever ist habe ich nicht gesagt. ich habe nur versucht eine möglichkeit zur ursprünglichen frage bereit zustellen. ich hätte wahrscheinlich einen anderen ansatzt gewählt. da muss ich dir recht geben! Genauso finde ich es nicht gut eine map für solche zwecke zu "missbrauchen"...

Dein Beispiel hat nicht funcktioniert ich hab es getestet. Es war nicht sortiert udn auch nicht usortiert, es hat einfach gar nciths gemacht einfach nur die komplette Datei eingelesen und ncihts dami gemacht

Der Ansatz mit dem vector werde ich weiterverfolgen, sage dann beschied bei fragen frag ich einfach. Hab mich gestern detalliert eingelesen damit wenigsten die Grundlagenfragen wegbleiben. Bis dann!

So wieder mal da

Schreibe nun alle Zeilen aus der Datei in einen Vector.

Dann lese ich eine Position des Vector aus (Iterator) und will den herausgelesenen String nochmals im gaznen Vector suchen

Ist er da schreibe ich den ersten in einen weiten Vector und lese die naechste Position aus dem Vector aus, prufe wieder usw

Ist der Eintrag nicht da schreibe ich das ganze auch einfach in den reulst Vector

Hier Code

VecCont::iterator it;
    for(it = myvec.begin(); it != myvec.end(); ++it)
    {
        //debug output
        cout<<*it<<endl;

        //write vector w/o double entries
        result.push_back(*it);
    }

Hier lese ich Punkt fuer Punkt den Vector mit allen Zeilen aus

result.push_back werde ich dann die Eintraege in den result vector schreiben (result kommt dann in output.txt)

Nur wie schaue ich performant nach ob ein ausgelsesener Punkt schonmal im vector vorkommt?

Zur Performance:

1. Wird das gazne bei nem grossen Vector (ueber 30000 Eintraege) nicht verdammt langsam (ne Map ist ja verdammt schnell, wirds aehnlich schnell oder viel langsamer?)

2. Wie kann man es besser machen

Michael E.

Es geht schneller, wenn du es so machst, wie Jester vorgeschlagen hat: Du speicherst die Zeilen in nem vector und Hashes von den Zeilen in nem set.

Ich verfolge die Diskussion noch nicht so lange und habe nur mal quer gelesen. Aber Hashcodes sortieren? Schaun wir mal, was das Suchen eines Elements kostet:

Hashcode berechen O(1) + Hashcode im Redblack suchen (O log n) = O(log n)
nichts gewonnen gegenüber der normalen Set

Der selbe Aufwand für lookup wie in der normalen Set, nur dass die Sortierung jetzt außerdem noch keinen logischen Bezug mehr zu den Elementen hat. Der Threadersteller will offenbar nur Duplikate verhindern. Es gibt doch bestimmt ein paar Extensions zur STL, die eine Art HashSet anbieten.

das von GBC, hier ein Auszug

std::vector<T>::iterator it = find(keys.begin(), keys.end(), key);

Nur dumm das Vector keine find methode hat? Was wie wo jetzt?

OBEN stand Mist

Unter GPCs Ansatz, wie kann ich die Werte aus der map bekommen? Wie bau ich da einen Iterator ein?

GPC schrieb:

Bau diesen Ansatz hier aus:

#include <vector>

template <typename T, typename U>
class NoSortMap {
  std::vector<T> keys;
  std::vector<U> values; 
  
public:
  NoSortMap() {}
  ~NoSortMap() {}
  
  bool insert(const T &key, const U &val) {
    std::vector<T>::iterator it = find(keys.begin(), keys.end(), key);
    
    if (it !== keys.end())
      return false;   
    
    keys.push_back(key); 
    values.push_back(val);
    return true;
  }
};

MfG

GPC

So hab ich es gemacht:

VecCont::iterator compare;
    VecCont::iterator current;
    bool bAlreadyAvailable = false;

    for(current = myvec.begin(); current != myvec.end(); ++current)
    {
        if(result.empty() == true)
        {
            //first push_back
            result.push_back(*current);
        }
        else
        {
            //find double entries
            for(compare = result.begin(); compare != result.end(); ++compare)
            {             
                if(*compare == *current)
                {
                    bAlreadyAvailable = true;
                }
            }

            if(bAlreadyAvailable == false)
            {
                result.push_back(*current);
            }

            bAlreadyAvailable = false;
        }
    }

Sicher nciht das schnellste aber es geht.

Was meint ihr?

GPC

modg schrieb:

OBEN stand Mist
Unter GPCs Ansatz, wie kann ich die Werte aus der map bekommen?

Indem du die vectoren zurückgibst:

class NoSortMap {
//... Zeug von vorhin

  const std::vector<T>& getKeys() const { return keys; }
  const std::vector<U>& getValues() const { return values; }
};

Wie bau ich da einen Iterator ein?

In dem du dir z.B. die Vektoren aus der NoSortMap zurückgeben lässt und darauf nen Iterator packst?

Sicher nciht das schnellste aber es geht.

Was meint ihr?

Huh? Was soll der Code den jetzt bezwecken? Meine insert Methode filtert doch bereits doppelte Einträge raus...

MfG

GPC

Hab deinen Ansatz dohc nciht genommen.

Hab alles von vorne gemacht eigenstaendig mit teils euren Tipps

Hier das gesamte Program

#include <iostream>
#include <vector>
#include <string>
#include <fstream>

using namespace std;
typedef vector<string> VecCont;

int main(int argc, char* argv[])
{
    //Declarations
    VecCont resultVec;
    VecCont inputVec;
    string currentLine;
    size_t whiteSpacePos;
    VecCont::iterator resultOut;

    ifstream ifs("E:/test.txt");
    if(!ifs)
    {
        cout<<"Error opening in file";
        return -1;
    }

    //parse file into vector
    while(ifs.good())
    {
        getline(ifs, currentLine);

        if(currentLine != "")
        {
            whiteSpacePos = currentLine.find_first_of(' ', 4);

            //cout<<currentLine<<endl;
            inputVec.push_back(currentLine);
        }
    }

    /************************************************************************/
    /* SEARCH AND TRIM - START                                              */
    /************************************************************************/
    VecCont::iterator compare;
    VecCont::iterator current;
    bool bAlreadyAvailable = false;

    for(current = inputVec.begin(); current != inputVec.end(); ++current)
    {
        if(resultVec.empty() == true)
        {
            //first push_back
            resultVec.push_back(*current);
        }
        else
        {
            //find double entries
            for(compare = resultVec.begin(); compare != resultVec.end(); ++compare)
            {             
                if(*compare == *current)
                {
                    bAlreadyAvailable = true;
                }
            }

            if(bAlreadyAvailable == false)
            {
                resultVec.push_back(*current);
            }

            bAlreadyAvailable = false;
        }
    }
    /************************************************************************/
    /* SEARCH AND TRIM - END                                                */
    /************************************************************************/

    //Output to result.txt
    ofstream ofs("E:/result.txt");
    if(!ofs)
    {
        cout<<"Error opening out file";
        return -1;
    }

    for(resultOut = resultVec.begin(); resultOut != resultVec.end(); ++resultOut)
    {
        ofs<<*resultOut<<'\n';
    }

    return 0;
}

Was sagen Profis dazu? Was kann man aendern? Es funktioniert sehr schnell wie ich finde

Oben ist noch eine whiteSpacePos Variabel nicht in Verwendung: Das kommt noch in Verwendung

Pellaeon

#include <algorithm>

. . .

/************************************************************************/
/* SEARCH AND TRIM - START                                              */
/************************************************************************/
VecCont::iterator compare;
VecCont::iterator current;

for(current = inputVec.begin(); current != inputVec.end(); ++current)
{
    //find double entries
    compare = find(resultVec.begin(),resultVec.end(),*current)
    if(compare != resultVec.end())
    {
        continue;
    }

    resultVec.push_back(*current);    
}

Wenns funktioniert dann lass es doch^^

Besser wäre natürlich, wie schon öfters angesprochen wurde, sich eine neue Klasse zu bauen, welche auf einem vorhandenen Container aufsetzt und intern dann dafür sorgt, dass nichts doppeltes gespeichert wird. So eine Klassen könnte man dann direkt beim einlesen benutzen und müsste nicht mit diesem Puffervektor arbeiten, um später was auszusortieren.

camper

das ganze wäre etwas für boost::multi_index_container (Lists with fast lookup)