char array mit Seperator alphabetisch sortieren

Columbo

- Wörter bestehen aus Buchstaben (klein und groß), Zahlen und underscore.
- Wörter können nur mit Buchstaben oder underscore anfangen.

Das ist sehr wichtig.

Außerdem: Wie möchtest du bspw. die Rangfolge von _ und a und A haben? _ zuerst? Denn wenn ich mit der angepassten Version dein Beispiel kompiliere, dann kommt folgende Sortierung heraus:

_cT68est aaa xyz abc_79d A_bcd usw8 bWort
=>
A_bcd _cT68est aaa abc_79d bWort usw8 xyz

Das heißt, ein einfacher Vergleich der ASCII-Werte ist ggf. zu primitiv.

knivil

Das ist sehr wichtig.

Nicht wirklich, wichtiger ist die Ordnungsrelation, also lexikographisch, alphabetisch, ... whatever.

struct sidx
{
    char const* pos;
    unsigned int len;
};

void split_idx(std::string const& words, std::vector<sidx>& indices)
{
    indices.clear();
    if (words.length() == 0) return;

    sidx idx = { 0, 0 };
    char const* p = &words[0];
    char const* pend = p + words.length();
    bool inword = false;
    while(p != pend)
    {
        bool change = ((bool)std::isalnum(*p)) != inword;
        if (change)
        {
            if (inword)
            {
                idx.len = p - idx.pos;
                indices.push_back(idx);
            }
            else
            {
                idx.pos = p;
            }
            inword = !inword;
        }
        ++p;
    };

    // close open word indexes
    if (inword)
    {
        idx.len = p - idx.pos;
        indices.push_back(idx);
    }
}

Hier meine split-Funktion, den Rest, also combine, gibt es ja schon. Das klassische RLE halt. std::alnum kann gern durch ein anderes Kriterium ersetzt werden.

Es gibt da einige kleine Anmerkungen von mir:

else 
                 ++vec.back().len;

Nun, das habe ich mir gespart.

if(last_char) 
             last_char = false;

Also wenn last_char == true -> last_char = false, ansonsten bleibe einfach false ... warum nicht einfach:

last_char = false

happystudent

Wow, das ist ja endlich mal ein richtig aktives Forum

Also die Reihenfolge sollte sein:

- Ersteinmal unabhänig von der Groß/Kleinschreibung, aber bei gleichen Buchstaben zuerst Kleinbuchstaben, dann Großbuchstaben
- Underscore als letztes

Also das Beispiel:

_cT68est aaa xyz abc_79d A_bcd usw8 bWort

Sollte sortiert so aussehen:

aaa abc_79d A_bcd bWort usw8 xyz _cT68est

knivil

- Ersteinmal unabhänig von der Groß/Kleinschreibung, aber bei gleichen Buchstaben zuerst Kleinbuchstaben, dann Großbuchstaben
- Underscore als letztes

Kannste alleine machen, indem das Sortierkritierium angepasst wird.

happystudent

Jo, werd ich machen. Das war eh schon mehr Hilfe als ich mir erhofft hatte

volkard

struct myLess{
    static int f(char x){
        return (((x&31))<<1)-(x>>5);
    }
    bool operator()(char a,char b){
        return f(a)<f(b);
    }
};
…
std::sort( std::begin(vec), std::end(vec), [](wordInformation const& p1,
wordInformation const& p2)
{ return std::lexicographical_compare(p1.pos, p1.pos + p1.len,
p2.pos, p2.pos + p2.len,myLess()); } );

SeppJ

happystudent schrieb:

Danke schonmal dafür. Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Sofern das Ding ein const char* will, passt da auch ein std::string. Falls das Ding da wirklich reinschreibt, dann eigentlich auch, wenn du den String vorher passend groß machst. 100k Zeichen auf dem Stack klingen nämlich nicht nach so einer tollen Idee.

Werner Salomon

happystudent schrieb:

Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Ist diese Funktion der Input oder der Output? und wie sieht die jeweils andere Seite aus?

happystudent

Hm ja, also eigentlich will die dll Funktion ein const char * als Parameter, die wird an dem Ding also nichts verändern.

Ich muss aber ein nicht-konstantes char array nehmen, weil ich vor und nach dem dll Aufruf selbiges schon verändere (also mein Programm führt die Veränderungen durch, nicht die dll).

EDIT:

Werner Salomon schrieb:

happystudent schrieb:

Also ich brauche ein char array weil ich eine Funktion von einer dll verwende, welche ein char array als Parameter haben will.

Ist diese Funktion der Input oder der Output? und wie sieht die jeweils andere Seite aus?

Äh, also die Funktion sorgt letztendlich für einen Output. Input ist das char array.

Werner Salomon

happystudent schrieb:

Äh, also die Funktion sorgt letztendlich für einen Output. Input ist das char array.

.. und wie kommen die Zeichen in das char array? (wordList s.o.)

happystudent

Also die werden in einer ziemlich fetten include Datei beim Programmstart zugewiesen (das Programm beginnt immer mit dem gleichen char array).

Also das sieht etwa so aus (Phantasiewörter):

char wordList[] = "aaa bzcc xpy wgggh iooo"
                  "kjl arhz wwwo plmg tttt"
                  "lalaa gggk fffr ccoe gd"
                  /* usw usw */

Werner Salomon

happystudent schrieb:

Also die werden in einer ziemlich fetten include Datei beim Programmstart zugewiesen (das Programm beginnt immer mit dem gleichen char array).

Also das sieht etwa so aus (Phantasiewörter):
char wordList[] = "aaa bzcc xpy wgggh iooo"
                  "kjl arhz wwwo plmg tttt"
                  "lalaa gggk fffr ccoe gd"
                  /* usw usw */

.. und wie erklärt sich dann die Anforderung, dass da mehrere dieser wordList's pro Sekunde sortiert werden sollen. Das ist doch erst mal nur eine?

knivil

Ja und sie braucht auch nur einmal sortiert warden.

SeppJ

Werner Salomon schrieb:

.. und wie erklärt sich dann die Anforderung, dass da mehrere dieser wordList's pro Sekunde sortiert werden sollen. Das ist doch erst mal nur eine?

Oder das überhaupt sortiert werden muss, wo man das doch schon zur Compilezeit haben könnte?

Klingt so, als wäre hier noch sehr viel Optimierungspotential durch Benutzung passenderer Datenstrukturen. Selbst, wenn es nur std::string ist.

happystudent

Ja schon, die Start-Liste müsste theoretisch nur einmal bzw. gar nicht sortiert werden, da es immer die selbe ist und man diese vorab sortieren könnte.

Warum ich das (bis jetzt) nicht gemacht habe:

Während dem Programmablauf wird die Wortliste dynamisch und nicht vorhersehbar erweitert/reduziert und das sehr oft. Hier muss die Wortliste sowieso ständig sortiert werden, da immer eine sortierte Version davon verfügbar sein muss.

Die Liste vorab zu sortieren hab ich deswegen nicht gemacht da der eine Sortiervorgang eh nicht ins Gewicht fällt und weil ich so schnell und einfach überprüfen kann ob der Sortieralgorithmus so funktioniert wie er soll.

SeppJ schrieb:

Werner Salomon schrieb:

Klingt so, als wäre hier noch sehr viel Optimierungspotential durch Benutzung passenderer Datenstrukturen. Selbst, wenn es nur std::string ist.

Ist std::string schneller als ein char array?? Ich dachte immer recht viel schneller gehts nicht...

SeppJ

happystudent schrieb:

Während dem Programmablauf wird die Wortliste dynamisch und nicht vorhersehbar erweitert/reduziert und das sehr oft. Hier muss die Wortliste sowieso ständig sortiert werden, da immer eine sortierte Version davon verfügbar sein muss.

Wie machst du das denn bei einem char-Array? Wo kommen diese Änderungen her? Wo kommen die Daten her?

Ist std::string schneller als ein char array?? Ich dachte immer recht viel schneller gehts nicht...

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?

happystudent

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

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.