سریع ترین روش برای جستجوی یک رشته در vector

Question

سلام.

اگر بخایم رشته ورودی را  در یک vector of struct جستجو کنیم شما چه روشی را پیشنهاد میدید؟

struct Person{
   string name;
   int id;
};

using Persons = vector<Person>;

 

Comments

می‌شه یه اپراتور تساوی تعریف کرد و از find(vector.begin(), vector.end(), item)!=vector.end()‎
استفاده کرد.

---

find خطی جست و جو می کنه که زیاد مناسب نیست ( O(n
برای این مدل جست و جو ها hash table سرعت بالاتری داره  hash table مرتبه تقریبی ( O(1 داره

Answer 1

همانطوری که دوستان توضیح دادن از hash استفاده کنید به صورت زیر:

#include <vector>
#include <iostream>
#include <unordered_set>

using namespace std;
struct Person{
	Person(string _name, int _id) :name(_name), id(_id){}
	Person(string _name) :name(_name), id(0){}
	string name;
	int id;
	bool operator== (const Person &person) const {
		return name == person.name;
	}

};
struct Hash {
	size_t operator() (const Person &person) const {
		return std::hash<std::string>()(person.name);
	}
};
int _tmain(int argc, _TCHAR* argv[])
{
	std::unordered_set<Person,Hash> persons;
	persons.reserve(5);
	persons.insert(Person("7",0));
	persons.insert(Person("khat",1));
	persons.insert(Person("code",2));
	persons.insert(Person(".", 3));
	persons.insert(Person("com", 4));

	auto pos = persons.find(Person("khat"));
	if (pos != persons.end())
		cout << "yes";
	else  cout << "no";
	return 0;
}