Linked Lists or Hash Tables

[complete]

What is best, linked lists or hash tables?

I am not too experienced with the standard template library (STL) in C++. I am more experienced with Visual C++ and the Microsoft Foundation Class Library (MFC). I have heard some good things about STL. Is it ture that there is a ready-to-use linked list? Is there also a hash table?

What advantages would there be to writing one from scratch?

If I do go with MFC, what advantages are there?

[Aradon]

So, my knowledge of the C++ libraries are limited. But I have a friend who does constant programming in C++ and is presently doing some game engine development.

He states that the Linked List and Hashtables that are available through either the STL or various other libraries are basically horrible. He broke down and wrote both himself (not that hard of a task considering).

Which is best? That depends what you are doing. If you're creating a list of an indeterminate size, then a Linked List would obviously be better. If you're just keeping track of several things and need quick access, a hash table would be better.

In any case, I'll let the real C++ developers answer the part about the libraries ;)

[Spookster]

You can also implement a hash table with a linked list. Eliminates possible collisions but you still want to have a decent hashing function to get an even spread across the buckets.

[oracleguy]

He states that the Linked List and Hashtables that are available through either the STL or various other libraries are basically horrible. He broke down and wrote both himself (not that hard of a task considering).

That is what I thought for a while as well but actually the reason is that the STL classes available (at least in Microsoft Visual Studio) run horribly slow but only when you compile in debug mode. If you compile for release there is a very significant speed increase.

However that being said I still have my own templated double linked list, array, queue, stack and a non-templated string class that I like to use.

[ralph l mayo]

You're almost certainly not going to be able to write a faster general algorithm than is available in the STL, but with specific knowledge about the way your program uses data you can likely write a faster specific implementation. The STL isn't able to make some assumptions about the data or their usage patterns even if they're usually safe and beneficial if they involve degradation of performance in less-common cases. With your own libraries of course you can optimize however you see fit. You shouldn't rewrite anything you can get out of the STL until benchmarking tells you you must, imo.

I don't deal with the MFC because it's not portable.

Regarding the hashtable, there isn't one required in the STL by the current standard AFAIK. There's the <map> header which provides the same functionality but is not a legitimate hashtable underneath the hood, and there's a <hash_map> that's provided by some vendors (eg, Microsoft) as a STL extension.

[complete]

OK, I am going to use the STL list. I want to have each node have two strings. Here is how far I have gotten:


#include <list> // list class-template definition

using namespace std;

class Node
{
CString string1;
CString string2;
}



list<Node> MyList;

I would I put nodes into this list?