map Inhalt wrid sortiert, wie unterbinden?

Alles in nen vector speichern und danach mit unique_copy nen neuen vector befüllen

CStoll

Wobei unique_copy() nur benachbarte identische Werte ausfiltert

@tux: Mit deinem Verfahren bekommst du definitiv nichts brauchbares heraus - dein "true_"-Funktor definiert keine Strict Weak Orderingund ist deshalb als Vergleichskriterium unbrauchbar.

Doch das Vergleichskriterium funktioniert. Man bedenke bei anderen Datenstrukturen wie vectoren klappt alles wunderbar (habe ich ausgetestet!). Das Problem liegt daran, wie die map intern die Daten verwaltet.

CStoll

Ein Vector benötigt auch kein Vergleichskriterium Eine Map dagegen schon (und wenn du deinen Code ausführen willst, landest du voll im Bereich "undefiniertes Verhalten" - d.h. du kannst weder sagen, in welcher Reihenfolge die Elemente eingefügt werden, noch kannst du in der map<> etwas suchen).

Sry hab grad nicht genau nachgedacht als ich ein beispiel für einen container, mit dem es funktioniert, geben wollte.

Die Vergleichsfunktoren std::less<T> liefern true oder false. Der Funktor true_ liefert immer true; es findet also keine sortierung statt. Die Verwendung von true_ funktioniert mit jedem Container, der auch Vergleichsfunktoren wie less oder greater unterstützt. Selbst mit der Map funktioniert dies. Versuche doch einmal das von mir gegebene Beispiel zu kompilieren und schau dir die Ausgaben an. Bei der Ausgabe via Iterator auf dem Container werden, wie du sehen wirst, alle Schlüsssel mit den passenden Werten korrekt ausgegeben. Das Problem ist der Zugriff per Indexoperator!

CStoll

Ja, das Programm lässt sich compilieren und wird sogar etwas ausgeben - das ist ja das Problem bei "undefiniertem Verhalten". Aber was dein Programm wirklich machen wird, kann niemand vorhersagen.

(es sortiert die Elemente vermutlich willkürlich ein, es schmeißt definitiv keine Duplikate aus der map heraus - und nach bestimmten Werten kannst du sowieso nicht suchen).

Nein das ist falsch. Die Werte werden korrekt einsortiert, nämlich alle unsortiert nacheinander. Der Funktor true_ erfüllt seine Aufgabe zu 100%. Nur ist es ein wiederspruch unsortierte Werte in einem Container abzulegen, der sortierte Werte verlangt. Das Ablegen der Werte funktioniert ohne Probleme auch lässt sich auf dem Container iterieren und die Werte werden korrekt ausgegeben. Es liegt keine undefiniertes Verhalten vor. Probleme entstehen bei dem Zugriff via Indexoperator, bei dem Aufruf von unique_copy, etc.

Jester

So ein Quark! Im Standard steht, daß die Vergleichsfunktion gewisse Eigenschaften haben muß. Deine Vergleichsfunktion hat das nicht, also ist das Verhalten undefiniert. Da gibt's garkeine Diskussion.

Pellaeon

lucky_tux schrieb:

Die Werte werden korrekt einsortiert, nämlich alle unsortiert

Allein dieser Satz zeigt doch nun, dass deine Containerwahl falsch ist^^
Sinnlos an der Map dran rumbiegen ist nicht wirklich clever.

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