Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid

Re: What do you like in a Collection class?

by Aristotle (Chancellor)
on Jul 09, 2002 at 22:31 UTC ( #180638=note: print w/ replies, xml ) Need Help??

in reply to What do you like in a Collection class?

Probably because arrays in Perl do pretty much everything you would use a linked list or collection for in a different language. What specific advantage over using a simple array do you want to implement in your module?

Makeshifts last the longest.

Comment on Re: What do you like in a Collection class?
Re: Re: What do you like in a Collection class?
by Anonymous Monk on Jul 09, 2002 at 22:44 UTC
    No, perl's arrays handle stack and queue operations, but not iteration in general. With an array you can iterate over the whole thing at once with for but be careful about inserting or deleting elements while doing so. For anything more complex you have to maintain an index variable. There is Tie::Array::Iterable, but that still doesn't give you all the niceties of next(), prev(), first(), and last().
Re: Re: What do you like in a Collection class?
by ariels (Curate) on Jul 10, 2002 at 07:55 UTC
    (This also applies to VSarkiss' reply below; Aristotle just came first...)

    Arrays do not support all common operations on collections (and hashes don't support all common operations on maps, either). That's why e.g. C++, (which does have support for Perl-like arrays as part of the standard language, VSarkiss; vector<T> is defined in the standard!), also supports other data structures.

    One thing array can't support is constant-time insertion (and extraction) of one or more elements. With a linked list, it's easy, but Perl's splice operation is quite expensive. Think of splice on a linked list: it works in constant time!

    Same thing for hashes and balanced trees. C++ has the latter (as map<T>); the lack of the former is a known deficiency (most STL implementations support some hash_map<T>, but it is not standard, so precise semantics may change). Why do you need both data structures?

    Easy. Hashes give you excellent expected time behaviour. But their worst case behaviour can be appalling (unless you store a balanced tree at each big bucket, in which case you're back to climbing trees). Hashes also don't support range operations ("return all values with keys between ariels and aristotle"). Some times you need the one, other times the other. This is why we have more than one type of data structure.

    Perl provides some data structures. This helps make it a Swiss army chainsaw. But don't let's kid ourselves we don't need what Perl doesn't have...

      Splicing on a list only works in constant time if you happen to have a pointer near the part you want to delete. But in general, splicing on an array and on a linked list will take linear time - it's linear on the array because of all the movement of the elements that's needed, and it's linear on a linked list because you first need to get to the part that needs to be deleted. The deletion itself takes time linear to size of the part that needs to be deleted - unless you also have to happen a pointer at the end of the part that needs to be deleted.


      I wasn't saying we don't need what we don't have, just offering an explanation.

      There are times when one needs things that Perl's arrays and hashes cannot provide, but that doesn't happen often. Even when it does, it is usually possible to shoehorn Perl's builtin data structures into the job at the expense of extra code complexity, or to rearrange the task in a less convenient way such that arrays or hashes will suffice (which is really the same thing as the former).

      That doesn't mean it can always be done. It just means that a rare itch will likely get ignored rather than scratched, hence the lack of modules, and that is all I was saying.

      Update in reply to dragonchild: if the need is so seldom and a prior art does not exist, the incentive to invest the effort of writing a generalized solution is low. It's a case of weighing hubris (create CPAN module) vs impatience (just write some code)..

      Makeshifts last the longest.

        "Extra Code Complexity" ... doesn't that just scream to be refactored into a module?

        We are the carpenters and bricklayers of the Information Age.

        Don't go borrowing trouble. For programmers, this means Worry only about what you need to implement.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://180638]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (11)
As of 2014-08-27 18:00 GMT
Find Nodes?
    Voting Booth?

    The best computer themed movie is:

    Results (248 votes), past polls