From b524eca827b182b0a51952557e36c945c779f848 Mon Sep 17 00:00:00 2001 From: Jérémy Zurcher Date: Sun, 13 Nov 2016 22:22:51 +0100 Subject: Algorithms : complete 02-data_structures 03-hash_tables --- .../03-hash_tables/02-hash_chains/hash_chains.cpp | 26 +++++++++++++--------- 1 file changed, 15 insertions(+), 11 deletions(-) (limited to '02-data_structures/03-hash_tables/02-hash_chains') diff --git a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp index 8af47d2..64a1975 100644 --- a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp +++ b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp @@ -15,7 +15,7 @@ struct Query { class QueryProcessor { int bucket_count; // store all strings in one vector - vector elems; + vector> elems; size_t hash_func(const string& s) const { static const size_t multiplier = 263; static const size_t prime = 1000000007; @@ -26,7 +26,9 @@ class QueryProcessor { } public: - explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {} + explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) { + elems.reserve(bucket_count); + } Query readQuery() const { Query query; @@ -45,20 +47,22 @@ public: void processQuery(const Query& query) { if (query.type == "check") { // use reverse order, because we append strings to the end - for (int i = static_cast(elems.size()) - 1; i >= 0; --i) - if (hash_func(elems[i]) == query.ind) - std::cout << elems[i] << " "; + vector *list = &elems[query.ind]; + for (int i = static_cast(list->size()) - 1; i >= 0; --i) + std::cout << (*list)[i] << " "; std::cout << "\n"; } else { - vector::iterator it = std::find(elems.begin(), elems.end(), query.s); + size_t h = hash_func(query.s); + vector *list = &elems[h]; + vector::iterator it = std::find(list->begin(), list->end(), query.s); if (query.type == "find") - writeSearchResult(it != elems.end()); + writeSearchResult(it != list->end()); else if (query.type == "add") { - if (it == elems.end()) - elems.push_back(query.s); + if (it == list->end()) + list->push_back(query.s); } else if (query.type == "del") { - if (it != elems.end()) - elems.erase(it); + if (it != list->end()) + list->erase(it); } } } -- cgit v1.2.3