View source for Talk:Associative array/Iteration

Hmm, associative array is not defined ordered. It is an unordered map. For example, it can have keys of complex numbers or images etc, which are unordered. Whether and if an associative array has some internal indices, different from the unordered keys, of full or partial order making indexation better than O(''n'') is an implementation detail. I tempted to suggest renaming to ''iteration over an'' '''ordered''' ''map'', but looking at the implementations, I realized that it is rather an ordered view of some unordered map using an alternative ordered key. Any container can have such alternative views. It is not special to associative array, or better to say has nothing to do with them. --[[User:Dmitry-kazakov|Dmitry-kazakov]] 08:23, 3 August 2009 (UTC)

:Hi Dmitry, iterating over all the members of an associative array is quite a common practice in Python. The keys/values may not appear in any particular order, but you must be guaranteed to go over each and every key/value only once. Python has the added assurance that if the associative array is unchanged, iterating over all keys , then iterating over all values will give the values in corresponding order to their keys; but that is not called for in this task.  --[[User:Paddy3118|Paddy3118]] 09:32, 3 August 2009 (UTC)

::Hi! Yes this is IMO the problem with this task. An associative array is not required to provide a conversion to an ordered set of pairs (key, value), which technically is what you described. Yes, it can, but so can any container on any finite machine. You can always order any finite set. The question whether any unordered map shall provide such conversion (in place (a view) or physical (a copy)) is another issue. There can be arguments for and against it. But it is not a programming task, it is a question of a container library design. Phyton's library took one choice, other libraries could do another. --[[User:Dmitry-kazakov|Dmitry-kazakov]] 10:05, 3 August 2009 (UTC)

::: Dmitry, it's sufficient that many programmers using many different mappings will want to iterate over all items or keys in the the mapping (with that guarantees that every item will be visited once and only once).  Regardless of whether that iteration conforms to any particular ordering it's clearly a suitable basis for comparison among different languages.  If my work requires me to deal with some Java code using their HashMap collections then I'm very likely to need info on the closest equivalent to Python ''.keys()'' or ''.items()'' dictionary methods.  Some mapping libraries, classes or types in some languages don't support this then it should absolutely be documented here (so that the programmer adopting such a language and learning about it here will KNOW that he or she must maintain a separate list of the valid keys).

:::: Maybe I was not clear enough. 1) It is not a language comparison task. It is comparison of container libraries. 2) The task name is misleading, because associative arrays are in general not iteratable. 3) A data structure that uses multiple indices is not an associative array, hash map. AFAIK, the technical term for that is '''relation''', and the relational algebra is there to build <nowiki>[</nowiki>sub<nowiki>]</nowiki>sets ordered according to this or that criterion (like SELECT in [[SQL]]). --[[User:Dmitry-kazakov|Dmitry-kazakov]] 12:24, 3 August 2009 (UTC)

::::: But if languages have built-in "container libraries", then it is a comparison task; C, Ada (I suppose) and others may be ruled out (if not using extern "container libraries" that may or may not provide the requested utility... a thing to be noted then!), but Python, Perl, PHP, Tcl, Smalltalk and others may not (and in fact they have a way of iterate over keys-values pair). Associative arrays should be always iterable I think. --[[User:ShinTakezou|ShinTakezou]] 12:51, 3 August 2009 (UTC)

:::::: Why do you think so? There might be no efficient or safe way to iterate an associative array. Consider an implementation that stores the array in an external storage. An implementation may deliberately disallow iteration for performance reasons, like a lock-free associative array could do, for instance. But I see that now the task is so diffusely stated, that anything would fit it! (:-)) --[[User:Dmitry-kazakov|Dmitry-kazakov]] 10:04, 5 August 2009 (UTC)

::::::: I think so since every language I know provides a way of iterating an "associative array", by pairs or giving back an array of keys and since it is often implemented because it's something one may need, often enough (and in fact, a lot of people use iteration over associative arrays alot in everyday programming). Currently I am using the [[:Category:Judy]] library to associate a data structure with a "symbol"; I am not interested in a way of iterating over the associations since the only intention is just to retrieve the data given the symbol, and this library itself does not provide a way of doing such an iteration over the associations. But if I were writing a language, I would implement for sure a way of iterating over it (it can be just extra memory, no killing performance too much: just another operation to keep track of the created "symbols"/keys). It does not mean that every language has it of course, but it's my opinion that if a language has associative arrays, it must give a way of iterating over them, since, as said, it's often useful. And my current knowledge of (high level) languages confirm this. --[[User:ShinTakezou|ShinTakezou]] 13:52, 5 August 2009 (UTC)

:::::::: Addendum: indeed Judy library too allow to iterate over key-value pairs! --[[User:ShinTakezou|ShinTakezou]] 12:20, 11 August 2009 (UTC)

::::::: Sometimes I think you're being really obstructive. While yes, it's possible that a particular implementation of an associative map might not allow iteration, the majority of implementations do (whether or not they're thread-safe, which might or might not be something of note to be mentioned, depending on the respective languages' norms) and I'm not aware offhand of any language that provides only uniterable associative maps; those that don't provide iterable maps tend to not provide maps at all. Iteration over a map — even given that it's a possibly slow thing to do — is just too useful in practice. (And for in-memory implementations where a single thread “owns” the map, it's actually fairly fast; usually straight linear in the number of elements.) —[[User:Dkf|Donal Fellows]] 14:20, 5 August 2009 (UTC)