Re: c-style string vs std::string
BGB <cr88192@hotmail.com> wrote:
if people know what they are doing, and performance matters some, the
usual (fairly straightforward) solution is to throw a hash-table at the
problem (not difficult to implement).
Actually implementing a good hash table is not trivial, for two reasons.
Firstly, the decision of which kind of hash table. Unlike eg. red-black
trees, there are many different possible hash table implementations, and
there's no one single that would be optimal. What type of hash table is
best may actually depend on what kind of data is inserted into it.
Secondly, a naive hashing function may have hidden surprises. It might
seem to work like a charm in all testcases... but then there may be some
pathological input (which is not even necessarily deliberately chosen to
break the hash table, but could be natural input from somewhere) that will
trigger the weakness in the hashing function (which usually presents itself
by the vast majority of the elements ending up in only a fraction of the
hash table positions, in other words, many elements having the same hash
values). This pathological situation might not be discovered in testing,
only when a client somewhere uses it with some unexpected input.
The major inefficiency in std::set and std::map is the memory allocation
that happens with each element. However, this inefficiency can be greatly
alleviated by using a fast memory allocator (which all STL containers
support). Such an allocator can make those containers faster by even an
order of magnitude or so.
Of course using a ready-made implementation of a data container (be it
std::set, std::map or their unordered variants in the new standard) also
reduces the amount of bug-hunting in the program, which is always a great
asset.