Archived

This topic is now archived and is closed to further replies.

Are Map, Hash, not the done thing in C++? If so, why?

This topic is 5369 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

My strongest language is C++ and in my experience, using hashes and maps are 'not the done thing.' However, in other languages (python, perl, lisp, et al) hashes are much more common. I don't normally see maps often. I am curious why this has become the way things are done. Is this a case of 'C++ is chosen to do tasks that don't normally involve hashing, while Perl, et al are chosen for those tasks' or is it a culture of the language issue? [edited by - flangazor on March 27, 2003 8:48:12 AM]

Share this post


Link to post
Share on other sites
In languages such as Python hashes are comparatively more efficient, so elegant solutions that would have been ignored in C++ can be used.

Much of the power of ''scripting'' languages is personified in something like Ruby''s hash or Python''s dictionary - storage of multiple types, lots of useful operations, and pretty good efficiency.

Doing complex AI in C++ is no fun - I find Ruby far more expressive, partly because of this expressiveness.

I''d agree on the ''choice of tasks'' issue - often scripting languages are used for tasks that are easier with dictionaries.
Indeed:

Task needs a dictionary -> do it in a scripting language
Doing it in a scripting language -> probably use a dictionary anyway

So it goes both ways!

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
My strongest language is C++ and in my experience, using hashes and maps are ''not the done thing.'' However, in other languages (python, perl, lisp, et al) hashes are much more common. I don''t normally see maps often.

Hashes and maps, as you use them, refer to the same thing. Some literature also refer to them as associative arrays while others call them dictionaries (particularly Python-oriented lit.) Hashing or hashes do exist and are fairly common in C++ applications at a certain level; note the popularity of hash_map and hash_set even though they''re not properly part of the C++ Standard Library.

Recall that C++ has medium-strength, static typing (dynamic typing is only mildly introduced via RTTI mechanisms) while languages like Perl, Python, PHP and Ruby have inherent strong, dynamic typing. This allows them to pack different types together in associative arrays, making dictionaries so much more powerful in those languages. The lack of memory management also makes type-agnostic associative containers so much easier to use in "scripting" languages. Given the language restrictions of C++, associative containers can only store related types (types that can be cast to each other or are derived from the same base class, via a base class pointer). All other methods of coercing containers into storing multiple types offload the responsibility for maintaining type mechanisms onto the programmer, for which you might as well have used embedded Python.

quote:
Is this a case of ''C++ is chosen to do tasks that don''t normally involve hashing, while Perl, et al are chosen for those tasks'' or is it a culture of the language issue?

I think it''s a much more comprehensive valuation, considering a wide variety of language properties and features. But yes, something along those lines - in several instances.

Share this post


Link to post
Share on other sites
quote:
Original post by petewood
the problem is your experience.


petewood, you are usually more helpful than that.

Re: cgoat, what sort of applications do you use? When I think of a problem, I immediately start thinking in terms of lists/vectors/trees. Where I work, its all lists and vectors and trees as well.

I want to break out of my rut (hence, I brought up the topic).

Oluseyi, thanks.

What are some problems where hashes and maps make work easier? I can think of the induction example in ANSI Common Lisp's 15th chapter. Apart from that, I am struggling to think of any examples.

[edited by - flangazor on March 26, 2003 11:11:51 AM]

Share this post


Link to post
Share on other sites
Sorry flangazor, that was short of me.

I find it frustrating when people make broad statements about something which they can''t possibly have experience of. The title of your post was a statement rather than a question - slightly tabloid too.

Whether or not other people use maps a lot in c++ isn''t important is it? If using maps helps you solve your problem then they''re a good solution, if they don''t then they''re not.

Saying they''re ''not the done thing'' gives the impression that there is a culture of resistance to using them which is encouraged and maintained in some way.

Share this post


Link to post
Share on other sites
To be honest, I was under the suspicion that hashes were not very common in the C++ code I have read by other people for very specific reasons. There must have been a reason why ISO said "hashes are not right for the C++ standard library". If it was soley based on the type reasons that Oluseyi cited or based on the fact that hashes have a significant O in their O(1) lookup time, then ok.

If it was something I was not familiar with, I was curious if it was a ''cultural'' reason that was maintained by C++ gurus (Herb Sutter, or Scott Meyers maybe) that hashes are wrong for C++.


--
Can I edit topic titles to add a question mark (?) and remove the tabloid-ness?
--

Share this post


Link to post
Share on other sites
The reason I don''t use hashes or maps much in C++ is mostly because I just don''t think about it. C was my first language and I used static/dynamic arrays for everything (and I didn''t know anything about data structures at all, so using a linked list or a binary tree never entered my mind). Now that the STL has all kinds of data structures, I still find myself using arrays most of the time, though I do use vectors when I need a dynamic array used for anything but a char buffer (when I need a char buffer I usually use the str and mem functions from the C library on it, and they take char pointers and afaik there isnt a way to get to the underlying dynamic array of an stl::vector). I think in terms of arrays when using C++ and only rarely do I think of a solution more easily implemented using a map or hash.

When programming in other languages (like PHP), I have a different mindset (and I don''t usually care about speed), and I''ll use associative arrays more often. In fact, just about every PHP script I''ve ever written uses associative arrays for something.

I think its just a psychological thing. People have different mindsets when using different languages.

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
the fact that hashes have a significant O in their O(1) lookup time
What "fact" is that? And compared to what? And why would a large constant affect, as hashes are clearly the fastest way of doing some things?

I remember reading from an interview with the original STL designer that he just didn''t have enough time to implement proper hash maps to C++ so he decided to leave them out. And I also recall reading from C++0x plans that they''re going to incorporate hash_map and hash_set to the next standard.

Share this post


Link to post
Share on other sites
It might just be because I worked at the wrong places but the reason why I almost never saw vectors/map/hash etc at my job or in university was simply because ppl did not know how to use the STL. Maybe it looks scary or something but classes involving C/C++ were always funny since the assignements were made simple because it assumed the student had to do a linked list to solve the question.

Or more often then not, ppl knew how to use the basic functions of STL and associative containers but never ever user all the nice search/sort etc algorythms that go with them.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Hashes and maps are useful for all sorts of things:

Mapping names to functions in a compiler or interpreter.

Caching loaded resources by filename, to avoid loading the same one twice.

Finding previously examined states in boardgame-style AI. (minimax etc.)

and many more.

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
Re: cgoat, what sort of applications do you use? When I think of a problem, I immediately start thinking in terms of lists/vectors/trees. Where I work, its all lists and vectors and trees as well.


Well the way I use maps most often is for loading configuration options from a file. A loader class that uses a specified format config file reads the files and stores the name/value pairs in a map.

Also, like the AP said, mapping names from a file to an actual function pointer, although I''ve yet to use it.

Another usage was to allow a set of environment name/value pairs to be passed to a function that creates a new process.

Basically, I use it a lot to associate a string with something else.

Share this post


Link to post
Share on other sites
Hi,

I use hashmaps quite often, maybe this is because in my job and previous jobs we use MFC. I often find myself the need to associate a string with an object - aka CMapStringToOb, this seems the obvious way to do it ?

Regards,
Steve

Share this post


Link to post
Share on other sites
quote:
Original post by civguy
] What "fact" is that? And compared to what? And why would a large constant affect, as hashes are clearly the fastest way of doing some things?


Compared to associative lists, hashes have a larger O in their big-O. Its implementation specific, but in Allegro CLisp, an associative list of 24 items breaks even with a hash of 24 items in terms of access speed.
Hash speed vs. associative list

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
Can I edit topic titles to add a question mark (?) and remove the tabloid-ness?

Yes. Edit your first post.

I used std::map to implement a runtime-modifiable message map for Win32 windows (the article is here on GDNet). Since I hardly handled more than a few messages, I simply ran a linear find on the map to locate the message handler, but someone with more demanding uses could conceivably modify the Window class to use a hashed map for quicker lookup times.

Any situation where you wish to associate collections of data of one type with collections of data of another type - or even of the same type - is a situation where a map could come in useful. Model-View-Controller, Abstract Factory and "Manager" designs come to mind.

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
To be honest, I was under the suspicion that hashes were not very common in the C++ code I have read by other people for very specific reasons. There must have been a reason why ISO said "hashes are not right for the C++ standard library".

What makes you think they said that? The reason that hashed containers don''t exist in the C++ Standard is the same that slist doesn''t exist - the ISO Committee had to deliver a standard and didn''t have time for everything. Hashed containers and slist will almost certainly be in C++0x.

Share this post


Link to post
Share on other sites
quote:
Original post by SabreMan
What makes you think they said that? The reason that hashed containers don''t exist in the C++ Standard is the same that slist doesn''t exist - the ISO Committee had to deliver a standard and didn''t have time for everything. Hashed containers and slist will almost certainly be in C++0x.


I thought it was a specification design rather than language desicion. It was not based on any actual information. Merely speculations and assumptions.

Oddly, I thought std::list was by default an slist (and some imaginary std::dlist was a doubley linked list). Upon further research, I realize this is not the case!

I suppose I shouldn''t have admitted that. ;-P

Share this post


Link to post
Share on other sites