char array mit Seperator alphabetisch sortieren

SeppJ

happystudent schrieb:

SeppJ schrieb:

Wo kommen diese Änderungen her? Wo kommen die Daten her?

Also die Änderungen kommen von Benutzereingaben. Diese können prinzipiell beliebig sein, solange sie den Anforderungen entsprechen werden sie zur Wortliste hinzugefügt. Falls der Benutzer sie löschen will kann er das auch tun.

SeppJ schrieb:

Nicht per se schneller, aber damit sind eben Sachen möglich, die mit einem char-Array gar nicht oder nur sehr umständlich möglich sind. Zum Beispiel "die Wortliste dynamisch und nicht vorhersehbar erweitern". Wie machst du das bisher?

Ja, das wäre wahrscheinlich dann das nächste Problem, soweit bin ich noch gar nicht.

Bis jetzt hab ich ja C# verwendet, da hab ich das ungefähr so gemacht:
wortListe += " " + "neuesWort";
// Dann .Split und .Sort

Da schreit mich geradezu ein vector<string> als Datenstruktur an. Vielleicht auch (multi-)set<string>, kommt drauf an, warum du überhaupt sortieren möchtest. Ebenso für den C#-Code das entsprechende Äquivalent. Du hast doch schon alle Information, die du jemals haben willst: Eine Liste einzelner Wörter. Dann schmeißt du alles weg, indem du die Wörter hintereinander in das Array schreibst. Dann fummelst du das Array wieder auseinander, um eine Liste einzelner Wörter zu erhalten und diese zu sortieren. Dann schmeißt du wieder alles in das Array.
Lass das Array einfach weg! Wozu ist das überhaupt da? Wenn du für den dll-Call unbedingt einen char* brauchst, dann machst du dir im allerletzten Schritt aus der sortierten Wortliste einen passenden string.

P.S.: So zum Beispiel:

#include <set>
#include <string>
#include <iostream>

using namespace std;

int main()
{
  // Unsere Wörterliste. Schon sortiert.
  multiset<string> words;

  // Primitiver Datenbanksimulator, hier kommt deine Benutzerinteraktion hin
  cout << "Wörter eingeben bis Ende\n";
  string word;
  while (cin >> word)
    words.insert(word);

  // Ausgabe in einen string:
  string result;
  for(string const& word: words)
    {
      result += word;
      result += ' ';
    }
  // Benutze den String in einer Funktion, die const char* erwartet:
  cout << result.c_str() << '\n';
}

Ist doch schon gleich viel einfacher.

happystudent

Hallo,

danke für den Vorschlag. Ich hab es jetzt (ein wenig anders) hingekriegt, da dem Compiler die for Schleife nicht gefallen hat (error : missing ',' before ':') und die word variable hat ihm auch nicht gepasst (error C2530: 'word' : references must be initialized).

Habs jetzt mal so probiert:

std::vector<std::string> vec;
    vec.push_back("aaaaa");
    vec.push_back("bbb");
    vec.push_back("ccccc");

    std::string result = join(vec, " ");
    // übergeben als result.c_str() funktioniert tatsächlich

mit folgender join Funktion:

std::string join(const std::vector<std::string>& vec, const char* delim)
{
	std::stringstream res;
	copy(vec.begin(), vec.end(), std::ostream_iterator<std::string>(res, delim));
    return res.str();
}

Ist das so gut?

Ich komm leider noch gar nicht klar mit diesen ständigen Typ-Problemen in C++, in C# ging das immer alles so einfach und problemlos

Schöne Grüße,
hs

Columbo

Deine join-Funktion ist "umständlich".

da dem Compiler die for Schleife nicht gefallen hat

Kein C++11. Hast du VC++?

Ändere das ab zu etwas wie

std::string join(std::vector<std::string> const& vec, const char* delim)
{
    std::string str;

    for( std::vector<std::string>::const_iterator it = vec.begin(); it != vec.end(); ++it )
        *it += s + delim;

    return str;
}

(ungetestet)
, das ist nicht kürzer, aber direkter.

Arcoth schrieb:

Deine join-Funktion ist "umständlich".

Dito.

Gabs hier nicht mal jemand, der sich beschwert hatte, dass std::accumulate bei den C++-Programmieren noch nicht angekommen ist?

std::string join(std::vector<std::string> const& vec, const char* delim)
{
  return std::accumulate(vec.begin(), vec.end(), std::string(),
                         [=](std::string const& r, std::string const& s){return r + s + delim;});
}

Columbo

Genau daran habe ich auch gedacht. (Nur natürlich richtig, deine Version hat einen Fehler)

Nur leider ein wenig fehl am Platz, da kein C++11 erlaubt ist.

Arcoth schrieb:

Genau daran habe ich auch gedacht. (Nur natürlich richtig, deine Version hat einen Fehler)

Hoho, ein überheblicher Klugscheisser.

Na, im Gegensatz zu deinem Code ist meiner wenigstens korrekt.

volkard

akkum schrieb:

Arcoth schrieb:

Deine join-Funktion ist "umständlich".

Dito.

Gabs hier nicht mal jemand, der sich beschwert hatte, dass std::accumulate bei den C++-Programmieren noch nicht angekommen ist?
std::string join(std::vector<std::string> const& vec, const char* delim)
{
  return std::accumulate(vec.begin(), vec.end(), std::string(),
                         [=](std::string const& r, std::string const& s){return r + s + delim;});
}

Quadratische Laufzeit?

happystudent

Arcoth schrieb:

Deine join-Funktion ist "umständlich".

da dem Compiler die for Schleife nicht gefallen hat

Kein C++11. Hast du VC++?

Äh, ich hab Visual Studio 2008 Professional Edition. Hab zwar auch VS 2010 aber da gibt es ja kein Intellisense mehr für C++

Arcoth schrieb:

Ändere das ab zu etwas wie

std::string join(std::vector<std::string> const& vec, const char* delim)
{
    std::string str;

    for( std::vector<std::string>::const_iterator it = vec.begin(); it != vec.end(); ++it )
        *it += s + delim;

    return str;
}

(ungetestet)
, das ist nicht kürzer, aber direkter.

Ok, was heißt "direkter"? Schneller? Oder besserer Programmier-Stil?

EDIT:

akkum schrieb:

Na, im Gegensatz zu deinem Code ist meiner wenigstens korrekt.

volkard schrieb:

Quadratische Laufzeit?

Hm, was stimmt jetzt hier?

Nexus

happystudent schrieb:

Hab zwar auch VS 2010 aber da gibt es ja kein Intellisense mehr für C++

Das trifft auf C++/CLI zu, nicht C++.

2008 ist schon ein halbes Jahrzehnt her... Vor allem kannst du damit nicht mal C++11-Features der ersten Generation benutzen.

Aber Range-Based For ist nicht was fundamental Neues, BOOST_FOREACH gibts schon ewig. Ist nur schön, dass man es jetzt ohne Makros sauber in die Sprache integriert hat.

volkard

happystudent schrieb:

Hm, was stimmt jetzt hier?

Bisher wenig. Denke, Du solltest die chars in einem vector<char> erst sammeln und dann Schwuppdiwupps in den Zielstring kopieren oder erst die Zeichen zählen (endlich accumulate), den Zielstring mit dieser Zeichenanzahl anlegen und dann die Quellstrings alle reinkopieren.

edit: Mit http://www.cplusplus.com/reference/string/string/reserve/ vorher genug Platz reservieren, dann ist die Laufzeit von join/accumulate/schleife optimal.

Beim String steht nämlich nicht http://www.cplusplus.com/reference/vector/vector/push_back/

std::string schrieb:

Complexity
Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

Columbo

akkum schrieb:

Na, im Gegensatz zu deinem Code ist meiner wenigstens korrekt.

Tatsächlich, er ist korrekt! Ich hätte schwören können, dass er nur alle zwei Strings den Delimitter setzt! Wenn ich mal genau hinschaue, dann ist es aber völlig korrekt...
Nun, ich habe nichts getestet.

Meine Variante ist falsch, ich habe aus Versehen die Bezeichner alle verwurschtelt.
Das soll natürlich

for( std::vector<std::string>::const_iterator it = vec.begin(); it != vec.end(); ++it )
        str += *it + delim;

heißen.

was heißt "direkter"? Schneller?

Ja. Es nimmt nicht einen unnötigen Umweg.

Quadratische Laufzeit?

Wieso das

knivil

Gabs hier nicht mal jemand, der sich beschwert hatte, dass std::accumulate bei den C++-Programmieren noch nicht angekommen ist?

ranged-based for ist sehr viel kuerzer zu schreiben, deswegen wird accumulate selten genutzt. Meine "Beschwerde" war weiter gefasst.

Quadratische Laufzeit?

Wahrscheinlich. Vielleicht schafft es der Compiler trotzdem zu optimieren. Ach koennte das const weggelassen werden, was es etwas leichter fuer den Compiler machen sollte.

volkard

knivil schrieb:

Quadratische Laufzeit?

Wahrscheinlich. Vielleicht schafft es der Compiler trotzdem zu optimieren.

Nö, sehe da keine Anker, wo der Optimierer greifen könnte. Er wird nicht res.reserve(wordlist.count()+accumulate(wordlist.begin(),wordlist.end(),[]...)) herausfinden.

Aber es kann sein, daß die Implementierung von std::string den Speicher bei += geometrisch wachsen läßt. An sich eine Unsitte. Aber halt sinnvoll für Normalprogrammierer, die die quadratische Laufzeit nicht direkt sehen. Dafür wünschte ich mir ein +=, das direkt und minimal wirkt und eine andere append-Methode, die geometischg wachsen läßt.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(){
    string word="hello";
    string res;
    size_t oldCapacity=0;
    for(int i=0;i<1000000;++i){
        res+=word+" ";
        if(res.capacity()!=oldCapacity){
            cout<<res.capacity()<<'\n';
            oldCapacity=res.capacity();
        }
    }
}

Ausgabe

Ok, gcc verdoppelt immer (ungefähr) bei +=.

Woher mögen die krummen Zahlen kommen?

camper

volkard schrieb:

Woher mögen die krummen Zahlen kommen?

Ausrichtung an 4kB-Seiten - free-storeverwaltungsoverhead - 1 Byte Terminator schätze ich mal. Vermutlich mag default-new Speicheranforderungen, die (fast) Vielfache von 4kB sind.

Columbo

GCC 4.9.0, basic_string.tcc

append(const basic_string& __str)
    {
      const size_type __size = __str.size();
      if (__size)
	{
	  const size_type __len = __size + this->size();
	  if (__len > this->capacity() || _M_rep()->_M_is_shared())
	    this->reserve(__len);
	  _M_copy(_M_data() + this->size(), __str._M_data(), __size);
	  _M_rep()->_M_set_length_and_sharable(__len);
	}
      return *this;
    }

Wo ist hier die Verdopplung versteckt?

camper

Arcoth schrieb:

Wo ist hier die Verdopplung versteckt?

In _S_create, mit ausführlichem Kommentar.

happystudent

volkard schrieb:

Bisher wenig. Denke, Du solltest die chars in einem vector<char> erst sammeln und dann Schwuppdiwupps in den Zielstring kopieren oder erst die Zeichen zählen (endlich accumulate), den Zielstring mit dieser Zeichenanzahl anlegen und dann die Quellstrings alle reinkopieren.

edit: Mit http://www.cplusplus.com/reference/string/string/reserve/ vorher genug Platz reservieren, dann ist die Laufzeit von join/accumulate/schleife optimal.

Beim String steht nämlich nicht http://www.cplusplus.com/reference/vector/vector/push_back/

std::string schrieb:

Complexity
Constant (amortized time, reallocation may happen).

If a reallocation happens, the reallocation is itself up to linear in the entire size.

Moment, das geht mir gerade etwas zu schnell.

Also die Wörter sammel ich jetzt in einem vector<string>, das passt nehme ich an? Diesen konvertiere ich dann bei Bedarf mittels join in eine Form die die dll akzeptiert.

Also geht es momentan nur um die Implementierung der join Funktion, das prinzipielle Vorgehen ist so ok, hab ich das richtig verstanden?

Dann weiter: Dass ich mittels string::reserve genug Platz reserviere macht Sinn, aber wenn ich davor die Zeichen mit accumulate zählen muss, muss ich selbiges doch wieder verwenden, was wie ich dachte quadratische Laufzeit hat?

EDIT:

Hab noch folgendes Snippet beim googlen gefunden:

string join(const vector<string> & vec,const string & sep)
{
    if(vec.size()==0)
        return "";
    string::size_type size=sep.length()*vec.size();
    for(unsigned int i=0;i<vec.size();i++)
    {
        size+=vec[i].size();
    }

    string tmp;
    tmp.reserve(size);
    tmp=vec[0];
    for(unsigned int i=1;i<vec.size();i++)
    {
        tmp=tmp+sep+vec[i];
    }
    return tmp;
}

Ist das besser als meins?

knivil

von std::string den Speicher bei += geometrisch wachsen läßt.

Warum sollte es anders als bei std::vector sein? Ich dachte du meinst, die Anzahl der Kopieroperationen/kopierten Zeichen.

volkard

happystudent schrieb:

Dann weiter: Dass ich mittels string::reserve genug Platz reserviere macht Sinn, aber wenn ich davor die Zeichen mit accumulate zählen muss, muss ich selbiges doch wieder verwenden, was wie ich dachte quadratische Laufzeit hat?

accumulate selber ist linear mit der anzahl der zu summierenden objekte. aber wenn das += des strings auch linear zur länge des ergebnisstrings ist, wird das zusammen quadratisch. also accumulate auf string ist sünde. accumulate auf size_t ist klasse.
wübei die sünde halb so wild wohl ist. gcc rechnet damit, daß gesündigt wird und bleibt schnell. wenn ms auch damit rechnet, dann ist das schon ein quasistandard und.

volkard

knivil schrieb:

von std::string den Speicher bei += geometrisch wachsen läßt.

Warum sollte es anders als bei std::vector sein?

Damit ich als Benutzer nicht so gequält werde. vector benutze ich fast immer mit push_back, da ist das geometrische Wachstum gut (sorg für amortisiert lineare Wachstumskosten). Und ich bin so frei, das reserve vorher sogar wegzulassen, was hier im Forum anscheinend leider zu sowas wie einer Pflichtübung geworden ist. Bei string sieht das ganz anders aus. Da baue ich mal eine sql-query zusammen oder einen vector/set/map von Dateinamen.
Wir sind uns hoffentlich einig, daß die Schnittstelle der DLL komisch ist, eine saulange Stringliste als EINEN riesigen leerzeichengetrennten String haben zu wollen. Für was braucht man sonst schnelles += auf riesige Strings? Also ich nicht. Da bin ich dann Fan von Speichersparen.