map Inhalt wrid sortiert, wie unterbinden?

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)