tags:

views:

191

answers:

6

Hi,

I am a beginner to C++. Can some one tell me a best data structure in C++ to store all words in a dictionary and find if a word is present in the dictionary. I know hash tables are the best but I dont know which data structure uses them ?

Thank you very much in advance.

+8  A: 

Your C++ implementation's standard library may have unordered_set or hash_set. They are essentially the same thing; the former is part of the forthcoming C++0x standard and is supported by some of the latest compilers, the latter is from the original SGI STL and is included in many standard library implementations.

James McNellis
Is hash_set or unordered_set part of standard library ?
brett
@brett: `hash_set`: Officially? No. But many standard library implementations (including Visual C++ and libstdc++) include it. `unordered_set`: Not yet. It will be part of the standard library when C++0x is approved sometime in 2011. Some standard library implementations (e.g., the Visual C++ 2010 library) include it.
James McNellis
Can i use it in my linux compiler ? G++? If not what is the best Data structure ?
brett
@brett: Usually, libstdc++ is used with g++, so, probably. I don't use g++ on a regular basis, so I couldn't tell you for sure. Try it and see.
James McNellis
If not what is the best Data structure ? I want my DS to work on cross platforms.
brett
@brett: The standard structure that does what you want is `std::set<t>`, which is similar to a TreeSet in Java, or a SortedSet in C#, if you are familiar with those languages. The C++ Standard Library does not (currently) provide hashtable facilities, thouch as @James says, such facilities are included with most compilers.
Billy ONeal
Oh, and +1 to @James.
Billy ONeal
@brett, as my answer points out, both GNU C++ and Microsoft Visual C++ supply `hash_map` (see the wikipedia entry I'm pointing to for more details) -- and `hash_set` too of course in case that isn't clear from my answer. If you need to run on _any_ standard-compliant C++ with no added components/libraries, then `std::map` (or `std::set` if you **exclusively** want presence/absence info, no auxiliary per-word data) is the only choice, but that's _not_ a hash map [[or set;-)][ (it's based on a red-black tree instead). There's no hash DS in the old (still current) C++ standard.
Alex Martelli
@brett: to clarify, `unordered_map` is part of the official TR1 extensions to standard C++. So it's guaranteed to be in the same place for TR1-compliant compilers, which is most of them. That's `<tr1/unordered_set>` and `tr1::unordered_set<>`. The only part not widely supported is moving it from `tr1::` to `std::`.
Potatoswatter
@Potatoswatter: Technically TR1 says that the names should just go into the standard library headers (e.g., `functional` instead of `tr1/functional`), so it _should_ be `<unordered_set>`, not `<tr1/unordered_set>` (IIRC, g++ uses the `tr1/` prefix for the TR1 headers; Visual C++ just puts all the names into the standard library headers). And, welcome back to Stack Overflow. :-P
James McNellis
+1  A: 

hash_map, if you have it in your C++'s compiler library (e.g., GNU C++ or Microsoft Visual C++). If you're using some other, less widespread compiler, I suspect you can find a decent third party implementation of hash_map anyway.

The forthcoming C++ standard calls this same data structure std::unordered_map instead.

If you don't want to associate any information at all with words in your dictionary, just record whether a word is present in it or not, you can use the _set (instead of _map) variations of the above data structure type names.

Of course, they're all templates (as all containers in the C++ standard library), so you'll need to instantiate them appropriately with typical template syntax.

Alex Martelli
But I think he will better with a set of words, not a map which is an associative key-value container.As James said, any set implementation should suffice.
Hernán
@Hernán, as I mentioned, if he only needs the presence/absence info, `hash_set` or `unordered_set` will be sufficient -- if he ever needs to record any auxiliary info, then the `..._map` variants will be better (and just as efficient).
Alex Martelli
A: 

If the only requirement is to decide whether a word is contained in a never-ever-changing dictionary, without needing any other kind of information about the word, (for example, a spell-checker) then Bloom filter is an efficient data structure for this task.

If there are other data to be associated with each word that needs to be looked up, std::map is a good, general-purpose starting point.

If auto-completion is needed (when a partial word has been entered), a Prefix tree (trie) may be used.

rwong
@rwong: A Bloom Filter is a probabilistic data structure; it cannot give you a definitive Yes/No answer. False positives are possible, but false negatives are not. The trie is a good idea though.
Billy ONeal
+1  A: 

Hashes are pretty good, but the best structure is a trie. You can get a trie from <ext/pb_ds/assoc_container.hpp> in GCC. See the online reference.

#include <ext/pb_ds/assoc_container.hpp>
#include <string>
#include <iostream>

int main() {
        pb_ds::trie< std::string, int > dict;

        dict.insert( std::make_pair( "hello", 3 ) );

        std::cerr << ( dict.find( "hello" ) != dict.end() ) << std::endl;
        std::cerr << ( dict.find( "goodbye" ) != dict.end() ) << std::endl;
}

Only map-like functionality, not a pure set, is provided. In the above sample I added a dummy int as data to map to… it shouldn't really hurt much.

What does hurt is that this won't work outside GCC.

On the other hand, a non-standard hash table (not std:: or ext:: anything) would allow you to only find approximate matches, i.e. to search among checksums of words instead of the words themselves. That would be the fastest, most compact solution. Dictionaries based on Bloom filters can contain many thousands of words in a few kilobytes.

Potatoswatter
A: 

If you're willing to roll your own solution and your dictionary is fixed, a perfect hash is a good way to go. It guarantees a constant lookup time.

Mark Ransom
I had this exact problem (generating fixed dictionaries) a year or two ago and was disappointed to find that perfect hashing practically requires a two-tier data structure and therefore multiple memory reads per lookup. It ends up being slower than a plain old hash table with chaining.
Jason Orendorff
FWIW, here's the code I ended up writing to generate the table: http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/qsgen.py#l1488 and to probe it: http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/xpcquickstubs.cpp#l70 In practice it generates a few chains 3 entries long (few lookups have to walk any chains at all though).
Jason Orendorff
+2  A: 

I would prefer using a Trie. A Trie will be a good data structure for building a memory-efficient dictionary with fast lookups, and yes, autocompletion.

Think of it as a hashtable, providing fast lookup of key-value pairs (or just lookup of keys), but unlike a hashtable it allows you to iterate over the keys in sorted order.

Please refer Trie - Wiki for further information/reference.

Prabhu Jayaraman