[C++] String compare met een andere String

[Verwijderd]

Hallo, ben nu een tijdje met C++ bezig en loop tegen een probleempje aan. Heb al lopen zoeken, ook hier op GoT, maar niet kunnen vinden wat ik zoek.

Een gebruiker typt een zin (String) en er is een String array met bepaalde woorden (ook Strings dus). Nu wil ik dat gecheckt wordt of een woord uit de array ook voorkomt in de zin.

voorbeeld:

String text = "Dit is de text die de gebruiker typt";
String woorden[] = {"test", "gebruiker", "hallo"};

Bij bovenstaande 'compare' moet er dus een soort van true gereturned worden want het woord "gebruiker" komt in beide strings voor.

In java had ik zoiets gedaan (ter verduidelijking, en het boeit ff niet of deze java code beter of netter oid kan):

Java:

String[] woorden  = {"test", "gebruiker", "hallo"};
String text = "Dit is de text die de gebruiker typt";
boolean matchFound = false;

for(int i = 0; i < woorden.length; i++)
{
      if((text.toLowerCase()).indexOf(woorden[i]) > -1)
      {
            matchFound = true;
            break;
      }
}

if(matchFound)
{
    //doe iets
}

Hoe gaat dit in C++?

[mOrPhie]

Het array-verhaal en het string-verhaal ligt wat anders in C++ dan in Java. Wat dat betreft is er een enorme berg aan tutorials en references te vinden.

Zoals deze string-compare:
http://www.cplusplus.com/ref/cstring/strcmp.html

[ Voor 4% gewijzigd door mOrPhie op 08-03-2004 22:20 ]

[Verwijderd]

mOrPhie schreef op 08 maart 2004 @ 22:19:
Het array-verhaal en het string-verhaal ligt wat anders in C++ dan in Java. Wat dat betreft is er een enorme berg aan tutorials en references te vinden.

Zoals deze string-compare:
http://www.cplusplus.com/ref/cstring/strcmp.html

Tja, maar dan moet je nog elke getypte zin gaat opsplitsen in losse woorden. In java kan dat mooi met een StringTokenizer, maar die heeft C++ niet. strcmp had ik gezien ja

[Glimi]

Verwijderd schreef op 08 maart 2004 @ 22:25:
Tja, maar dan moet je nog elke getypte zin gaat opsplitsen in losse woorden. In java kan dat mooi met een StringTokenizer, maar die heeft C++ niet. strcmp had ik gezien ja

In Java kun je opzich ook http://java.sun.com/j2se/...matches(java.lang.String) gebruiken en matchen dmv een regex.

In C++ zou je http://www.dinkumware.com...2.html#basic_string::find kunnen gebruiken om je huidige javamanier te implementeren. Ik zal nog even bij Boost kijken of daar een goede regexmanier is
Boosts regex lib heeft idd ook een stringmatcher : http://www.boost.org/libs/regex/doc/regex_match.html

[ Voor 8% gewijzigd door Glimi op 08-03-2004 23:31 ]

[Soultaker]

Wat is String voor type? Is dat zo'n MFC string of nog weer wat anders? Kan die eenvoudig als array van characters geïnterpreteerd worden?

String matching is vrij lastig, zeker als je meerdere strings tegelijk wil vergelijken. Als je echter niet zo geïnteresseerd bent in efficiëntie, is het vrij eenvoudig: gebruik de functie strstr() (in de cstring header):

char *
strstr(const char *big, const char *little);

DESCRIPTION
The strstr() function locates the first occurrence of the null-terminated
string little in the null-terminated string big.

RETURN VALUES
If little is an empty string, big is returned; if little occurs nowhere
in big, NULL is returned; otherwise a pointer to the first character of
the first occurrence of little is returned.

Aangezien je nu een functie hebt die je kunt gebruiken ter vervanging van indexOf in Java, kun je de implementatie in C++ analoog aan die in Java schrijven.

[Verwijderd]

je moet gewoon de functie strcmp() gebruiken....

deze staat in string.h en windows.h, dus take your pick


http://msdn.microsoft.com.../erlrfstrcmpcmawcscmp.asp

dit is een beschrijving van deze functie, dus misschien dat je er wat aan hebt (het is microsoft, maar je weet maar nooit

[MSalters]

strcmp is dus niet wat je nodig hebt, want 1) het is C, geen C++ en 2) het vindt (terecht) dat "A" ongelijk is aan "A B C".
Wat wel C++ is:

C++:

#include <algorithm>
std::string pattern = "gebruiker";
std::string input = "Dit is de text die de gebruiker typt";
bool found = ( std::search(
  input.begin(),input.end(),
  pattern.begin(),pattern.end() )
  != input.end() );

Het loopje voor een array van pattern strings is triviaal.

[ Voor 8% gewijzigd door MSalters op 09-03-2004 19:02 ]

[Soultaker]

MSalters: je gaat nu voorbij aan het feit dat de topic starter geen std::string maar String (wat dat ook moge zijn) gebruikt. Het is maar de vraag of daar geschikte iterators op te verkrijgen zijn.

[MSalters]

Anders heeft hij een klein oefeningetje, zelf iterators maken. Voor elke string class is dat hooguit 2 uur werk.

[Glimi]

Zou een regex-match niet sneller zijn (bij een significante aantal verschillende woorden)?

Stel je hebt m verschillende woorden, en ik neem aan dat een std::search/strstr in O(n) tijd werkt (lineaire scan). Dan zal de loop O( m*n ) tijd in beslag nemen, worst case.
Ik neem aan dat een regex wel wat sneller kan werken door het bijhouden van look-ahead sets, of zie ik dat verkeerd?

[Macros]

In Java zou ik het zo doen:
Split de gegeven string in tokens (split op spatie). Maak een hashmap (van begin grootte ongeveer 50 ofzo, ligt aan de string lengte). Doen dan in een loopje voor elke token:
Kijk of token in map zit (als key).
Zo ja, verhoog de value met 1.
Zo nee, doe in map en zet value op 1.

Dan aan het einde check je of het woord dat je zoekt in de map zit of niet en dan weet je meteen hoevaak.
Maar ja, dit is C++, en dat is gaar

[.oisyn]

Macros schreef op 10 maart 2004 @ 00:52:
Maar ja, dit is C++, en dat is gaar

Door de onhandige casts die je in Java nodig hebt gaat het in C++ een stuk gemakkelijker, met een std::map<std::string, int>

C++:

// str is hier de opgegeven string en is een std::string

std::map<std::string, int> map;
std::istringstream in (str);
std::string token;

while (in >> token)
    map[token]++;

En kom jij nou eens met de java-code hiervan

[ Voor 36% gewijzigd door .oisyn op 10-03-2004 01:00 ]

[Glimi]

Macros schreef op 10 maart 2004 @ 00:52:
In Java zou ik het zo doen:
Split de gegeven string in tokens (split op spatie). Maak een hashmap (van begin grootte ongeveer 50 ofzo, ligt aan de string lengte). Doen dan in een loopje voor elke token:
Kijk of token in map zit (als key).
Zo ja, verhoog de value met 1.
Zo nee, doe in map en zet value op 1.
(...)

C++ kan dat net zo hard, zelfs mooier . Alleen die counter moet je niet bijhouden in Java. Dat heeft toch geen nut, plus dat het jou nu telkens het aanmaken van één object kost (Integer), en dan nog de kosten van het verhogen

Stel nu dat je string gemiddeld uit woorden bestaat van 4 tekens lang en je string is n lang. Dan kost dit je 1/5 * n O(1) operaties (inserten) en daarna m maal het woord checken dmv een O(1) operaties.
Dan is dat opzich nog O(n + m) , wat me een leuke verbetering lijkt.
(Alleen je geheugengebruik is wel stukken groter )

[Macros]

.oisyn schreef op 10 maart 2004 @ 00:55:
[...]



Door de onhandige casts die je in Java nodig hebt gaat het in C++ een stuk gemakkelijker, met een std::map<std::string, int>

C++:

// str is hier de opgegeven string en is een std::string

std::map<std::string, int> map;
std::istringstream in (str);
std::string token;

while (in >> token)
    map[token]++;

En kom jij nou eens met de java-code hiervan

Java:

Map<String, Integer> m = new HashMap<String, Integer>();
StringTokenizer st = new StringTokenizer(str);
while (st.hasMoreTokens()){
     Integer freq = m.get(st.nextToken());
     m.put(word, (freq == null ? 1 : freq + 1));
}
// en voor de sier:
System.out.println(m);

Ik tel evenveel regels, helaas zijn de namen van de functies en dergelijke in C++ korter. (Oh ja, dit is Java 1.5 met Generics en Autoboxing).

[ Voor 4% gewijzigd door Macros op 10-03-2004 01:15 ]

[.oisyn]

Macros schreef op 10 maart 2004 @ 01:09:
(Oh ja, dit is Java 1.5 met Generics en Autoboxing).

welke nog niet released is

Vooral

C++:

map[token]++;

vs.

Java:

Integer freq = m.get(word);
m.put(word, (freq == null ? 1 : freq + 1));

vind ik een mooi stukje

[ Voor 32% gewijzigd door .oisyn op 10-03-2004 01:14 ]

[Macros]

Wel leuk dat als je HashMap in TreeMap veranderd, dan sorteerd hij het nog voor je ook (wordt het wel O(NlogN) van)

[Macros]

.oisyn schreef op 10 maart 2004 @ 01:11:
[...]

welke nog niet released is

Vooral

C++:

map[token]++;

vs.

Java:

Integer freq = m.get(word);
m.put(word, (freq == null ? 1 : freq + 1));

vind ik een mooi stukje

Beta is al wel een tijdje uit. Heb net mijn stukje code gecompiled en werkt oke:

Java:

import java.util.*;

class Map{
    public static void main(String[] arg){
    TreeMap<String, Integer> m = new TreeMap<String, Integer>();
    for (String word : arg) {
            Integer freq = m.get(word);
            m.put(word, (freq == null ? 1 : freq + 1));
        }
        System.out.println(m);
    }
}

Eigenlijk zou 'null' geautoboxed moeten worden naar 0, helaas hebben ze gekozen om gewoon null pointer exceptions op te gooien en hebben wij Java coders geen keus. Ook wordt nu gebruik gemaakt van de nieuwe for-loop.

[.oisyn]

Macros schreef op 10 maart 2004 @ 01:22:
Wel leuk dat als je HashMap in TreeMap veranderd, dan sorteerd hij het nog voor je ook (wordt het wel O(NlogN) van)

Oh dat geldt voor dat stukje C++ code ook, maar dan net andersom: nu gebruikt ie gewoon een zoekboom, als je een stdext::hash_map gebruikt gebruikt ie een hashtable. Hoewel stdext::hash_map geen standaard C++ klasse is, kent vziw elke zichzelf respecterende implementatie 'm wel. Hij zit waarschijnlijk ook gewoon bij de volgende standard update

[Macros]

Maar eeh ehhh, het is cross platform zonder recompile....
Crap, laat maar zitten

[farlane]

Macros schreef op 10 maart 2004 @ 01:33:
Maar eeh ehhh, het is cross platform zonder recompile....
Crap, laat maar zitten

Haha, begon idd al een beetje een wedstrijdje verpissen te worden

[Macros]

En toen kwam er een Haskel dude die het in 2 regels kon en maar 10 keer trager...

[Glimi]

Macros schreef op 10 maart 2004 @ 01:09:
Ik tel evenveel regels, helaas zijn de namen van de functies en dergelijke in C++ korter. (Oh ja, dit is Java 1.5 met Generics en Autoboxing).

Ja maar waarom toch die int? Waar heb je hem in godesnaam voor nodig? Doe gewoon een Map<String, String> waarbij je het woord zowel als key/value opslaat.
Dan heb je 1) geen autoboxing nodig, wat traag kan worden door het aanmaken van objecten
2) Geen gezeur met incrementen

Macros schreef op 10 maart 2004 @ 01:26:
Eigenlijk zou 'null' geautoboxed moeten worden naar 0, helaas hebben ze gekozen om gewoon null pointer exceptions op te gooien en hebben wij Java coders geen keus. Ook wordt nu gebruik gemaakt van de nieuwe for-loop.

NEE NEE NEE! Geen null autoboxen naar iets! Null is niets en al helemaal geen 0. 0 is geen andere waarde dan normale integers, terwijl null dat wel is tov een reference!
Straks krijg je nog de C++ problemen van impliciete conversies

Macros schreef op 10 maart 2004 @ 09:55:
En toen kwam er een Haskel dude die het in 2 regels kon en maar 10 keer trager...

Zeg, we gaan niet overdrijven met je twee regels he:

Haskell:

module Main where

srchWrds        :: [String]
srchWrds        = [ "test" 
                  , "gebruiker"
                  , "hallo"
                  ]
                  
srchStr         :: String
srchStr         = "Dit is de text die de gebruiker typt"

test            :: [String] -> String -> Bool
test wrds str   = any (`elem` (words str)) wrds
-- call with test srchWrds srchStr

In beschouwing gelaten dat jullie ook geen method def's hebben vermeld en de str defs ook weggelaten hebben kom ik uit op één regel code
Het zal ongeveer even snel zijn als het loopen over de string.

[Macros]

Glimi schreef op 10 maart 2004 @ 10:24:
[...]

Ja maar waarom toch die int? Waar heb je hem in godesnaam voor nodig? Doe gewoon een Map<String, String> waarbij je het woord zowel als key/value opslaat.
Dan heb je 1) geen autoboxing nodig, wat traag kan worden door het aanmaken van objecten
2) Geen gezeur met incrementen

[...]

Nee nee nee want dan hou je de frequentie niet meer bij. Wat jij wilt is dan een Set<String> in de vorm van HashSet of TreeSet (scheelt weer een regel code btw).

[Verwijderd]

Uhm het is heel leuk dat er allerlei performance gerichtte oplossingen verzonnen worden, maar ik wil gewoon een String compare doen met maar 6 woordjes

[Soultaker]

Mijn suggestie al geprobeerd dan?

[Verwijderd]

Soultaker schreef op 10 maart 2004 @ 14:46:
Mijn suggestie al geprobeerd dan?

Ik heb nu deze code (ben C++ n00b he):

C++:

void __fastcall TForm1::Edit1KeyPress(TObject *Sender, char &Key)
{
     if(Key == 13)
     {
         char words[] = {"gebruiker mekker blaat test hallo doei"};
         bool containsWord = false;

         char text[100];
         String myText = Edit1->Text;
         strcpy(text, myText.c_str());

         char *match = strstr(words, text);
         if(match != NULL)
         {
            containsWord = true;
         }

         if(!containsWord)
         {
               //doe iets            
         }
         else
         {
               //doe iets anders            
         }
     }
}

Maar dit werkt dus alleen als de zin van de gebruiker begint met een woord uit de woord char array. En geloof dat het ook alleen maar 1 woord mag zijn die de gebruiker dan mag typen.

vb.
Gebruiker typt: hallo ik ben een gebruiker --> false
Gebruiker typt: hallo --> true

Probleem is dus dat ik niet weet hoe je een array maakt van die woorden die nu in char words[] zitten. een strstr wil char als argumenten en geen string.

[Soultaker]

Simpel; je moet alle woorden apart vermelden en die één voor één controleren. Dat is niet echt efficiënt als het aantal woorden hoog oploopt, maar dat was niet aan de orde zei je. Zoiets wordt het dan:

C:

const char *words[] = { "gebruiker", "mekker", "blaat" };
int w;
for(w = 0; w < sizeof(words) / sizeof(*words); ++w)
    if(strstr(text, words[w]))
    {
        // whatever...
    }

[ Voor 8% gewijzigd door Soultaker op 10-03-2004 15:42 ]

[.oisyn]

Macros schreef op 10 maart 2004 @ 01:33:
Maar eeh ehhh, het is cross platform zonder recompile....

ligt er maar net aan of je JIT compiling ook als recompiling ziet

[Macros]

.oisyn schreef op 10 maart 2004 @ 16:21:
[...]


ligt er maar net aan of je JIT compiling ook als recompiling ziet

Dat zie ik niet, want het is niet verplicht

[Soultaker]

offtopic:
Je kunt ook een C-code interpreter schrijven hoor; zo bezien is recompilation van C-code ook niet verplicht.

[Macros]

Soultaker schreef op 10 maart 2004 @ 19:54:

offtopic:
Je kunt ook een C-code interpreter schrijven hoor; zo bezien is recompilation van C-code ook niet verplicht.

offtopic:
Niet dat het dan gaat werken, omdat libs meestal heel anders zijn op verschillende platforms.

[.oisyn]

Er zijn talloze libs te vinden waarvan het gebruik ervan portable is. En dat is met java precies hetzelfde verhaal

[Macros]

We gaan nu wel erg ver off-topic, niet?
En als dat zo was, dan waren alle coole c(++) progs onder Linux wel naar windows geport, helaas is dat niet het geval.

[.oisyn]

Er zijn zat "coole" linux progs naar windows geport ja, en nee, niet allemaal, omdat ze niet allemaal portable libs gebruiken

[Glimi]

Ik krijg medelijden met de topicstarter. Stelletje wijsneuzen.

[.oisyn]

Dat krijg je als je roept dat C++ gaar is zonder enige onderbouwing

[Verwijderd]

Glimi schreef op 11 maart 2004 @ 09:46:
Ik krijg medelijden met de topicstarter. Stelletje wijsneuzen.

Hehe, het is al opgelost, bedankt daarvoor. Maar het gaat idd wel erg offtopic