Zum 100. Mal: Einen String durchsuchen

virtuell Realisticer

Ich glaube ich habe dir grad mist erzaehlt. Bin mir nicht 100% sicher, aber ich
glaub string::npos kann auch negativ sein, weshalb hier size_t falsch waere,
da size_t == unsigned int. Du kannst hier auch einfach ein 'int' nehmen.

Wie gesagt, da bin ich mir grad nicht 100% sicher.

mfg
v R

Mr. B

Also ich merk zwischen int und unsigned int keinen Unterschied - beides klappt prima!

Shlo

virtuell Realisticer schrieb:

Ich glaube ich habe dir grad mist erzaehlt. Bin mir nicht 100% sicher, aber ich
glaub string::npos kann auch negativ sein, weshalb hier size_t falsch waere,
da size_t == unsigned int. Du kannst hier auch einfach ein 'int' nehmen.

Wie gesagt, da bin ich mir grad nicht 100% sicher.

mfg
v R

string::find gibt string::size_type zurück, was normalerweise ein std::size_t typedef ist, genauso ist es bei string::npos.

virtuell Realisticer

Shlo schrieb:

virtuell Realisticer schrieb:

Ich glaube ich habe dir grad mist erzaehlt. Bin mir nicht 100% sicher, aber ich
glaub string::npos kann auch negativ sein, weshalb hier size_t falsch waere,
da size_t == unsigned int. Du kannst hier auch einfach ein 'int' nehmen.

Wie gesagt, da bin ich mir grad nicht 100% sicher.

mfg
v R

string::find gibt string::size_type zurück, was normalerweise ein std::size_t typedef ist, genauso ist es bei string::npos.

Gut, dann kann ich mir ab jetzt wieder sicher sein

mfg
v R

walterfrier

Ist wirklich immer size_t == unsigned int?
Wozu braucht man dann size_t?

Ich finde leider keine richtige Erklärung, nur Sachen wie
"man nimmt size_t für längen Angaben und nicht int! " aber warum ...?

Danke!

Hallo,

weiterlesen hier:

http://www.c-plusplus.net/forum/viewtopic.php?t=81754&postdays=0&postorder=asc&start=10

MfG

otze

npos kann je nach implementation wirklich -1 sein, habs grad nochmal in der bcb hilfe nachgelesen, da dort npos wirklich -1 ist
vielleicht erwartet man ja auch keinen so langen string

virtuell Realisticer

otze schrieb:

npos kann je nach implementation wirklich -1 sein, habs grad nochmal in der bcb hilfe nachgelesen, da dort npos wirklich -1 ist
vielleicht erwartet man ja auch keinen so langen string

Ah, jetzt weiss ich wieder, wo ich das her hatte. Danke fuer den Denkanstoss

mfg
v R

HumeSikkins

otze schrieb:

npos kann je nach implementation wirklich -1 sein

Kann nicht nur, sondern soll es sogar. 21.3/p6 definiert npos als:

static const size_type npos = -1;

size_type ist per Definition aber ein unsigned-Typ. Also ist npos niemals negativ.

volkard

Mr. B schrieb:

Soweit ich gelesen habe, gibt es zwei Möglichkeiten, das zu bewerkstelligen.

stimmt. man kann nur boyer-moore und abwandlungen nehmen oder endliche automaten. funktionen aus <algrithm> oder <cstring> funktionieren nicht. regexps auch nicht. inline-assembler mit repne-befehlen oder kleine selbergebaute schleifen sind zu einfach und schleifen om strcpy oder memcpy sind zu schmuddelig. hashen gilt als fahrlässig und wurde bei der letzten welteliteprogrammiererkonferenz sogar verboten.
und da du von nem großen zu durchsuchenden string sprichst, liegt ja eh boyer-moore nahe. am liebsten mag ich die abwandlung, die neulich in der c't stand. (neulich so um mitte 2000).

#ifndef VHLIB_TEXTSEARCH_H
#define VHLIB_TEXTSEARCH_H
#pragma once

// Verfahren aus einer c't übernommen

class TextSearch
{
private:
        int shift[256];
        int look_at;
        char *pattern;
        int patternlen;
        char *end;
        char *pos;

        char *find(char *text);
public:
        TextSearch(char *p,int m);
        ~TextSearch();
        char *findFirst(char *text,int size);
        char *findNext();
};

#endif

#include "TextSearch.h"
#include <string.h>

TextSearch::TextSearch(char *p,int m)
{
        patternlen=m;
        pattern=new char[m];
        memcpy(pattern,p,m);

        int i;
        for(i=0;i<256;++i)
                shift[i]=m+1;
        for(i=0;i<m;i++)
                shift[(unsigned char)pattern[i]]=m-i;
        look_at=0;
        while(look_at<m-1) 
        {
                if(p[m-1]==p[m-(look_at+2)]) break;
                ++look_at;
        };
};

TextSearch::~TextSearch()
{
        delete[] pattern;
};

char *TextSearch::findFirst(char *text,int size)
{
        end=text+size;
        return pos=find(text);
};

char *TextSearch::findNext()
{
        return pos=find(pos+1);
};

char *TextSearch::find(char *text)
{
        int i;
        char *t=text;
        for(;;) 
        {
                i=patternlen-1;
                if(t+i>=end) return 0;
                while(t[i]!=pattern[i]) 
                {
                        t+=shift[(unsigned char)t[patternlen]];
                        if(t+i>=end) return 0;
                }
                --i;
                while(t[i]==pattern[i]) 
                {
                        if(--i<0) return t;
                }
                t+=look_at+shift[(unsigned char)t[patternlen+look_at]];
        }
}