inheriting from the STL

1) Generally it's a bad idea because these classes were not designed to be used polymorphically. So yeah, you can get away with it if you absolutely under no circumstances use your derived type polymorphically, but that's an awfully easily overlooked constraint... just a matter of time before another programmer comes along and screws up your once-working code.

2) Implementation specific.

3) In general, use generic algorithms to extend the functionality of an STL container. In this case, there already is one: http://www.sgi.com/tech/stl/find.html

Add to the above the fact, that you can expect from every new programmer your company hires to know the STL, but you certainly cannot expect from them to know you cutom-build list class. Thus any new person will have a harder time reading your code and start working productive.

Another thing: If searching is so important, std::list might be the wrong data structure to use in the first place.

Another thing: If searching is so important, std::list might be the wrong data structure to use in the first place.

Well, the main goal is to track lists of strings associated with a pointer to something else.

There would be several (less than 100) of these in a list and they would need to be pulled out and updated at random.

something like:

typedef struct TagIdList
{
string Id;
void* object;
}TIdList;

std::list<TIdList> MyList;

What other types might we need to look at?

Thanks,
Kendall

You can use std::map<string, void*>.

I did look at other types besides std::list, but it seemed like std::list was the best option given our requirements.

Some of the requirements were to be able to easily delete and add elements anywhere in the list and to be able to search the list quickly.

There are a few issues Id like to comment on:

1) string comparisons are quite expensive, maybe you can use an int as ID and avoid string comparisons.
2) Pointers to void are unsafe since you lose all type information, you might consider building a class hierachy and store pointers to the common base class.
3) Who owns the objects pointed at by IdList? Maybe you can use boost::shared_ptr to transfer ownership to the IdList and get rid of possible memory leaks.
4) There are some non-standard containers like hash_map which didnt make it into the standard, but are commonly used and may perform better than std::map.

1 & 2 are required. It is likely that the pointer will be pointing to a structure of POD types, but they want it to be flexible to be able to point to anything.
In general, This code is based on code written in another language and that is basically how it is done there. They want to keep the code the same, even though the language is changing.

Thanks,
Kendall

It depends on your design. Who frees the objects on the heap when you dont need them any more? As long there is no automatic mechanism which does it for you and you free them manually when you dont need them anymore youre fine. But consider the following scenario:

struct MyStruct
{
char *pszString;
};

MyStruct obj;

obj.pszString = strdup( "Hello World" );

vector<MyStruct> v;

v.push_back( obj );

free( obj.pszString );

It can be even getting worse:

struct MyStruct
{
char *pszString;

MyStruct() : pszString( NULL )
{
}

~MyStruct()
{
if( pszString )
{
free( pszString );
}
}
};

vector<MyStruct> v;

void add()
{
MyStruct obj;

obj.pszString = strdup( "Hello World" );
v.push_back( obj );
}

When you can make sure that none of these scenarios happen youre safe.

Although hash_map is O(1) and std::map is O(log N), you have to beware of saying that this proves hash_map is faster.

constant doesn't always mean small. Not only because if you don't have a good hashing algorithm (which has to be good for your actual data) then your data might not be evenly distributed but also the simple fact that:

- The time taken to hash can be fairly expensive. Could be more expensive than several comparisons. If your map has, say, 1024 entries, then it could be that 10 comparisons are cheaper than the constant hash. (hash is constant but it could be a big constant).

- You have to decide in advance the size of your hash-table and re-hashing if you grow the table is expensive. Rebalancing the tree is usually constant. But let's assume for now that it's a load-once, lookup many times table.

- Iterating through a hash-map is slow

- It is fairly easy to write a hash_map in C++ using vector and map.

template < typename K, typename V, typename H >
class hash_map
{
private:
H m_hasher;
size_t m_size;

typedef std::map< K, V > map_type;
typedef typename map_type::const_iterator map_const_iterator;
typedef typename map_type::iterator map_iterator;

std::vector< map_type > m_table;

public:
hash_map( H hasher, size_t sz )
: m_hasher( hasher ), m_size( sz ), m_table( sz )
{
}

bool insert( const K & key, const V & value, bool overwrite )
{
size_t hash_value = m_hasher( key ) % m_size;
map_type & mapToUse = m_table[ hash_value ];
std::pair < map_iterator, bool > res = mapToUse.insert( std::make_pair( key, value ) );
if ( res.second || !overwrite )
{
return res.second;
}
else
{
res.first.second = value;
return false;
}


bool lookup( const K & key, V & value ) const
{
size_t hash_value = m_hasher( key ) % m_size;
const map_type & mapToUse = m_table[ hash_value ];
const_iterator iter = mapToUse.find( key );
if ( key != mapToUse.end() )
{
value = iter->second;
return true;
}
else
{
return false;
}
};

That will give you the basic functionality although you might want to improve insert and make it like map insert, and you might want to have operator[] as well. (In std::map, insert never overwrites, operator[] does).

1. Yes
2. Yes
3. No
4. No
5. No, it does not contain type information - just an arbitrary name provided by the user.
6. No

Kendall

Can you clarify this statement further?

1)Do you need to insert new and erase existing elements at arbitrary positions in the container?

2) Do you frequently require random access (i.e. is accessing this container for reading/adding/erasing/modifying data a core part of this application)?

3) Are the items required to be sorted?

4) Do you require that existing elements in the container do not move address when elements are inserted or erased?

5) Would I be correct in assuming that the string in a TagIdList struct element contains type information about the object being pointed to by the void* pointer?

6) Is the highest possible processing speed the underlying aim?