Wie String in Liste suchen und erweitern?

kernel64

Hallo, ich habe mehrere Strings in einer List gespeichert wie z.B.

Auto
Amsterdam
Haus
Hallo
Test
Windows
Warum

Nun habe ich ein string Input der eingegeben wird aber nicht vollständig ist, dieser muss nun anhand der angefangenen Buchstaben mit der in der Liste verglichen werden und dann erweitert werden.
Wenn man z.B. Ha eingibt, muss nun zwischen Hallo oder Haus aus der Liste entschieden werden.

Mann weiß wieviel Lang Input.length() ist, kann man anhand der der Länge auch die mit der ersten Strings in der Liste vergleichen?

//...
list< string > listDir;

listDir = getDirectory();

list< string >::iterator current_file = listDir.begin();
string FileObject = *current_file;
//..

wenn Input = "win" ist, dann Länge = 3, also die ersten drei Buchstaben in der Liste mit Input vergleichen und erweitern, wie soll das gehen?

thordk

die wohl einfachste variante ist, einfach ganz stupide die gesamte liste durchzugehen und die ersten n zeichen der eingabe und der liste zu vergleichen (http://cppreference.com/cppstring/substr.html).

die aufwendigere, aber bei sehr großen listen performantere ist es, deine liste in nen baum umzuformen.

kernel64

OK habs nun ausprobiert:

//...

string incompleteCommand;
								//Suche von hinten nach dem letzten Leerzeichen
								int pos = input.rfind(' ');    								
								incompleteCommand = input.substr(pos+1, input.length());	

								//Liste zum Anfang setzen
								current_file = listDir.begin();		

								do
								{	
									string ListItem = *current_file;
									string compareItems = *current_file;	
									//Erstelle neue Strings mit der gleichen Länge wie incompleteCommand
									compareItems = compareItems.substr(0, incompleteCommand.length());								

									if(incompleteCommand == compareItems)
									{	
										incompleteCommand.append(ListItem, compareItems.length(), ListItem.length());
										//cout << "[" << incompleteCommand << "]" << endl;
										input.append(incompleteCommand, pos+1, incompleteCommand.length());
										cout << input << flush;

										break;
									}
									else
										++current_file;																

								}while(current_file != listDir.end( ));

Es müsste aber noch einiges verbessert werden, ab und zu bekomme ich auch Laufzeit-Fehler in der Klasse string.cpp

_MRTIMP2 void __cdecl _String_base::_Xran()
{ // report an out_of_range error
_THROW_NCEE(out_of_range, "invalid string position");
}

Hoffe ihr könnt mir paar Verbesserungen vorschlagen da der Code bestimmt schlampig ist.

thordk

hat mich selbst mal interessiert, wie das mit nem baum funzt. ist erstaunlich fix mit ner recht großen wordlist

falls dich der code interessiert: http://nopaste.ch/d461f3d606267cc.html
ist allerdings java.

finix

Du übergibst substr die Länge des anderen Strings, ganz gleich ob die Position existiert.

Als Verbesserung schlage ich vor deinen ganzen Code raus zu schmeißen, und durch einen Funktionsaufruf zu ersetzen.

template <
  typename InIteratorT,
  typename OutIteratorT,
  typename PredicateT
>
void filter( InIteratorT first, InIteratorT last, OutIteratorT result, PredicateT pred )
{
  for ( ; first != last; ++first)
    if (pred(*first))
      *result++ = *first;
}

struct begins_with;

typedef std::list<std::string> file_list;

file_list possible_completions( file_list const& candidates, std::string const& str )
{
  file_list result;
  filter(candidates.begin(), candidates.end(), back_inserter(result), begins_with(str));
  return result;
}

// Hier kommt deine Codestelle:
string incompleteCommand = extract_command(input); // command, nicht filename?
file_list suggestions = possible_completions(listDir, incompleteCommand);

kernel64

Also zur Erläuterung, ich programmiere gerade eine Shell ähnlich wie cmd.exe
Die Funktion brauche ich für die TAB-Vervollständigung, damit angefangene Dateien/Verzeichnisse automatisch erweitert werden.

Beispiel:
Alle Möglichkeiten mit wi

:>cd wi[TAB] = cd Windows

Das mit den Reaktionen habe ich alles schon realisiert und kommt nicht hier ins Forum, bei Interesse könnte ich den Code posten.

Der Code oben wird dann aufgerufen wenn ein Zeichen bei Input.length()-1 steht, also an der letzten Stelle von input, siehe oben wi

@finix Hi, kannste mir bitte kurz erklären was die Funktionen machen, lösen die mein Problem mit dem erweitern?

Bekomme an dieser Stelle:

filter(candidates.begin(), candidates.end(), back_inserter(result), begins_with(str));

den Fehler:

error C2440: '<function-style-cast>': 'const std::string' kann nicht in 'begins_with' konvertiert werden
Quelle oder Ziel hat einen unvollständigen Typ

finix

kernel64 schrieb:

@finix Hi, kannste mir bitte kurz erklären was die Funktionen machen, lösen die mein Problem mit dem erweitern?

Die Funktion filter könntest du genauso gut copy_if nennen, das dürfte klären was sie macht. begins_with liefert eine "Funktion" die true liefert wenn das Argument mit dem übergebenen String beginnt.

struct equal_char_ci : public std::binary_function<char, char, bool>
{
  bool operator()( char lhs, char rhs ) const
  {
    return tolower(lhs) == tolower(rhs);
  }
};

class begins_with_ci : public std::unary_function<std::string, bool>
{
public:
  begins_with_ci( std::string const& str )
    : value_(str)
  { }

  bool operator()( std::string const& str ) const
  {
    return equal(value_.begin(), value_.end(), str.begin(), equal_char_ci());
  }

private:
  std::string  value_;
};

Nach dem Aufruf hast du in suggestions alle möglichen Erweiterungen.

edit: Bevor du fragst, extract_command ist natürlich noch nicht implementiert (kannst ja einfach deinen Codeschnipsel darein verfrachten)

kernel64

Habs nun gemacht, eine paar Probleme ergeben sich noch, wenn ich z.B. ein Wort anfange das nicht in der Liste ist dann bekomme ich ein Laufzeitfehler:

Expression: list iterator not derefencable

Wahrscheinlich muss ich noch was ändern:

string incompleteCommand;
								//Suche von hinten nach dem letzten Leerzeichen
								int pos = input.rfind(' ');    								
								incompleteCommand = input.substr(pos+1, input.length());	

								file_list suggestions = possible_completions(listDir, incompleteCommand);

								list< string >::iterator currentItem = suggestions.begin();

								string foundItems = *currentItem;

								do{
									cout << foundItems << endl;

								}while(currentItem != suggestions.end());

Wie kann man alle Möglichkeiten ausgeben die gefunden wurden, habs auch schon versucht doch meine Schleife findet kein ende

camper

@kernel64: deinen Iterator inkrementieren muss du natürlich, sonst trittst du auf der Stelle

@finix: Das geht auch mit Standardalgorithmen: copy_if ist nichts weiter als remove_copy_if mit negiertem Prädikat.

finix

Ja, sorry, mein Fehler. Tausch das equal einfach gegen equal_sequence aus:

template <typename Iterator1T, typename Iterator2T, typename PredicateT>
bool equal_sequence( Iterator1T first1, Iterator1T last1, Iterator2T first2, Iterator2T last2, PredicateT pred )
{
  for ( ; first1 != last1 && first2 != last2; ++first1, ++first2)
    if (!pred(*first1, *first2))
      return false;
  return first1 == last1;
}

kernel64 schrieb:

Wie kann man alle Möglichkeiten ausgeben die gefunden wurden, habs auch schon versucht doch meine Schleife findet kein ende

Vielleicht solltest du dir abgewöhnen alles in eine do ... while Schleife zwängen. Du inkrementierst den Iterator nicht.

for (list<string>::iterator sit = suggestions.begin(), send = suggestions.end();
     sit != send;
     ++sit)
{
  cout << *sit << endl;
}

// oder auch einfach

copy(suggestions.begin(), suggestions.end(), ostream_iterator<string>(cout, "\n"));

finix

camper schrieb:

@finix: Das geht auch mit Standardalgorithmen: copy_if ist nichts weiter als remove_copy_if mit negiertem Prädikat.

Ich weiss, aber ich halte filter für wesentlich deutlicher. Bei filter bzw. copy_if sieht man gleich was los ist, die Intention die dahinter steckt.

Naja, man könnte remove_copy_if(f, l, r, not1(p)) als Implementation nutzen, aber nicht anstelle von filter. Alles IMAO, natürlich.

edit: aber vielleicht hast du statt diesem leidigen equal_sequence eine bessere Lösung?

kernel64

Wenn ich es richtig verstanden hab soll ich das:

bool operator()( std::string const& str ) const
  {
    return equal(value_.begin(), value_.end(), str.begin(), equal_char_ci());
  }

in folgendes ändern:

bool operator()( std::string const& str ) const
  {
    return equal_sequence(value_.begin(), value_.end(), str.begin(), equal_char_ci());
  }

Jetzt bekomme ich ein Fehler, da die Funktion ein Parameter zu wenig übergeben bekommt:

'bool equal_sequence(Iterator1T,Iterator1T,Iterator2T,Iterator2T,PredicateT)': Erwartet 5 Argumente - 4 unterstützt

camper

equal ist ja nicht falsch, nur müssen wir zuerst schauen, dass die Länge passt:

template <typename Iterator1T, typename Iterator2T, typename PredicateT>
bool equal_sequence( Iterator1T first1, Iterator1T last1, Iterator2T first2, Iterator2T last2, PredicateT pred )
{
  return distance( first1, last1 ) <= distance( first2, last2 ) && equal( first1, last1, first2, pred );
}

wobei wir hier logischerweise einfach die Stringlängen vergleichen würden.

bool operator()( std::string const& str ) const
  {
    return value_.length() <= str.length() && equal(value_.begin(), value_.end(), str.begin(), equal_char_ci());
  }

oder auch

bool operator()( std::string const& str ) const
  {
    return str.compare(0,value_.size(),value_) == 0;
  }

kernel64

Ich hab noch eine Frage, wie kann man im folgendem Teil prüfen ob *sit ein oder mehrere Wörter gefunden hat:

for (list<string>::iterator sit = suggestions.begin(), send = suggestions.end();
     sit != send;
     ++sit)
{
  cout << *sit << endl;
}

Wenn in der Liste nur ein Element gefunden wird dann.... anonsten sollen alle ausgegeben werden.

kernel64

Ich frag nochmal, wie kann man ermitteln wieviele Möglichkeiten in der Liste gespeichert wurden? Wenn nur ein Wert in der Liste steht so wird der angefangene String vervollständigt, aber wenn mehrere Werte stehen dann sollen diese dann ausgegeben werden.

file_list suggestions = possible_completions(listDir, incompleteCommand);

								cout << endl;

								for (list<string>::iterator sit = suggestions.begin(), send = suggestions.end();
									sit != send;
									++sit)
								{
									//input = *sit;
									cout << *sit << "\t";
								}

CStoll

Und wo ist jetzt dein Problem? Du hast dir alle in Frage kommenden Fortsetzungen der Eingabe nach suggestions kopiert, jetzt kannst du damit machen, was du willst (z.B. ausgeben oder mit suggestions.size() ihre Anzahl ermitteln).