2 X<data structure> X<complex data structure> X<struct>
4 perldsc - Perl Data Structures Cookbook
8 Perl lets us have complex data structures. You can write something like
9 this and all of a sudden, you'd have an array with three dimensions!
20 Alas, however simple this may appear, underneath it's a much more
21 elaborate construct than meets the eye!
23 How do you print it out? Why can't you say just C<print @AoA>? How do
24 you sort it? How can you pass it to a function or get one of these back
25 from a function? Is it an object? Can you save it to disk to read
26 back later? How do you access whole rows or columns of that matrix? Do
27 all the values have to be numeric?
29 As you see, it's quite easy to become confused. While some small portion
30 of the blame for this can be attributed to the reference-based
31 implementation, it's really more due to a lack of existing documentation with
32 examples designed for the beginner.
34 This document is meant to be a detailed but understandable treatment of the
35 many different sorts of data structures you might want to develop. It
36 should also serve as a cookbook of examples. That way, when you need to
37 create one of these complex data structures, you can just pinch, pilfer, or
38 purloin a drop-in example from here.
40 Let's look at each of these possible constructs in detail. There are separate
41 sections on each of the following:
45 =item * arrays of arrays
47 =item * hashes of arrays
49 =item * arrays of hashes
51 =item * hashes of hashes
53 =item * more elaborate constructs
57 But for now, let's look at general issues common to all
58 these types of data structures.
61 X<reference> X<dereference> X<dereferencing> X<pointer>
63 The most important thing to understand about all data structures in
64 Perl--including multidimensional arrays--is that even though they might
65 appear otherwise, Perl C<@ARRAY>s and C<%HASH>es are all internally
66 one-dimensional. They can hold only scalar values (meaning a string,
67 number, or a reference). They cannot directly contain other arrays or
68 hashes, but instead contain I<references> to other arrays or hashes.
69 X<multidimensional array> X<array, multidimensional>
71 You can't use a reference to an array or hash in quite the same way that you
72 would a real array or hash. For C or C++ programmers unused to
73 distinguishing between arrays and pointers to the same, this can be
74 confusing. If so, just think of it as the difference between a structure
75 and a pointer to a structure.
77 You can (and should) read more about references in L<perlref>.
78 Briefly, references are rather like pointers that know what they
79 point to. (Objects are also a kind of reference, but we won't be needing
80 them right away--if ever.) This means that when you have something which
81 looks to you like an access to a two-or-more-dimensional array and/or hash,
82 what's really going on is that the base type is
83 merely a one-dimensional entity that contains references to the next
84 level. It's just that you can I<use> it as though it were a
85 two-dimensional one. This is actually the way almost all C
86 multidimensional arrays work as well.
88 $array[7][12] # array of arrays
89 $array[7]{string} # array of hashes
90 $hash{string}[7] # hash of arrays
91 $hash{string}{'another string'} # hash of hashes
93 Now, because the top level contains only references, if you try to print
94 out your array in with a simple print() function, you'll get something
95 that doesn't look very nice, like this:
97 @AoA = ( [2, 3], [4, 5, 7], [0] );
101 ARRAY(0x83c38)ARRAY(0x8b194)ARRAY(0x8b1d0)
104 That's because Perl doesn't (ever) implicitly dereference your variables.
105 If you want to get at the thing a reference is referring to, then you have
106 to do this yourself using either prefix typing indicators, like
107 C<${$blah}>, C<@{$blah}>, C<@{$blah[$i]}>, or else postfix pointer arrows,
108 like C<$a-E<gt>[3]>, C<$h-E<gt>{fred}>, or even C<$ob-E<gt>method()-E<gt>[3]>.
110 =head1 COMMON MISTAKES
112 The two most common mistakes made in constructing something like
113 an array of arrays is either accidentally counting the number of
114 elements or else taking a reference to the same memory location
115 repeatedly. Here's the case where you just get the count instead
119 @array = somefunc($i);
120 $AoA[$i] = @array; # WRONG!
123 That's just the simple case of assigning an array to a scalar and getting
124 its element count. If that's what you really and truly want, then you
125 might do well to consider being a tad more explicit about it, like this:
128 @array = somefunc($i);
129 $counts[$i] = scalar @array;
132 Here's the case of taking a reference to the same memory location
136 @array = somefunc($i);
137 $AoA[$i] = \@array; # WRONG!
140 So, what's the big problem with that? It looks right, doesn't it?
141 After all, I just told you that you need an array of references, so by
142 golly, you've made me one!
144 Unfortunately, while this is true, it's still broken. All the references
145 in @AoA refer to the I<very same place>, and they will therefore all hold
146 whatever was last in @array! It's similar to the problem demonstrated in
147 the following C program:
151 struct passwd *getpwnam(), *rp, *dp;
152 rp = getpwnam("root");
153 dp = getpwnam("daemon");
155 printf("daemon name is %s\nroot name is %s\n",
156 dp->pw_name, rp->pw_name);
161 daemon name is daemon
164 The problem is that both C<rp> and C<dp> are pointers to the same location
165 in memory! In C, you'd have to remember to malloc() yourself some new
166 memory. In Perl, you'll want to use the array constructor C<[]> or the
167 hash constructor C<{}> instead. Here's the right way to do the preceding
168 broken code fragments:
172 @array = somefunc($i);
173 $AoA[$i] = [ @array ];
176 The square brackets make a reference to a new array with a I<copy>
177 of what's in @array at the time of the assignment. This is what
180 Note that this will produce something similar, but it's
185 @{$AoA[$i]} = @array;
188 Is it the same? Well, maybe so--and maybe not. The subtle difference
189 is that when you assign something in square brackets, you know for sure
190 it's always a brand new reference with a new I<copy> of the data.
191 Something else could be going on in this new case with the C<@{$AoA[$i]}>
192 dereference on the left-hand-side of the assignment. It all depends on
193 whether C<$AoA[$i]> had been undefined to start with, or whether it
194 already contained a reference. If you had already populated @AoA with
197 $AoA[3] = \@another_array;
199 Then the assignment with the indirection on the left-hand-side would
200 use the existing reference that was already there:
204 Of course, this I<would> have the "interesting" effect of clobbering
205 @another_array. (Have you ever noticed how when a programmer says
206 something is "interesting", that rather than meaning "intriguing",
207 they're disturbingly more apt to mean that it's "annoying",
208 "difficult", or both? :-)
210 So just remember always to use the array or hash constructors with C<[]>
211 or C<{}>, and you'll be fine, although it's not always optimally
214 Surprisingly, the following dangerous-looking construct will
215 actually work out fine:
218 my @array = somefunc($i);
222 That's because my() is more of a run-time statement than it is a
223 compile-time declaration I<per se>. This means that the my() variable is
224 remade afresh each time through the loop. So even though it I<looks> as
225 though you stored the same variable reference each time, you actually did
226 not! This is a subtle distinction that can produce more efficient code at
227 the risk of misleading all but the most experienced of programmers. So I
228 usually advise against teaching it to beginners. In fact, except for
229 passing arguments to functions, I seldom like to see the gimme-a-reference
230 operator (backslash) used much at all in code. Instead, I advise
231 beginners that they (and most of the rest of us) should try to use the
232 much more easily understood constructors C<[]> and C<{}> instead of
233 relying upon lexical (or dynamic) scoping and hidden reference-counting to
234 do the right thing behind the scenes.
238 $AoA[$i] = [ @array ]; # usually best
239 $AoA[$i] = \@array; # perilous; just how my() was that array?
240 @{ $AoA[$i] } = @array; # way too tricky for most programmers
243 =head1 CAVEAT ON PRECEDENCE
244 X<dereference, precedence> X<dereferencing, precedence>
246 Speaking of things like C<@{$AoA[$i]}>, the following are actually the
250 $aref->[2][2] # clear
251 $$aref[2][2] # confusing
253 That's because Perl's precedence rules on its five prefix dereferencers
254 (which look like someone swearing: C<$ @ * % &>) make them bind more
255 tightly than the postfix subscripting brackets or braces! This will no
256 doubt come as a great shock to the C or C++ programmer, who is quite
257 accustomed to using C<*a[i]> to mean what's pointed to by the I<i'th>
258 element of C<a>. That is, they first take the subscript, and only then
259 dereference the thing at that subscript. That's fine in C, but this isn't C.
261 The seemingly equivalent construct in Perl, C<$$aref[$i]> first does
262 the deref of $aref, making it take $aref as a reference to an
263 array, and then dereference that, and finally tell you the I<i'th> value
264 of the array pointed to by $AoA. If you wanted the C notion, you'd have to
265 write C<${$AoA[$i]}> to force the C<$AoA[$i]> to get evaluated first
266 before the leading C<$> dereferencer.
268 =head1 WHY YOU SHOULD ALWAYS C<use strict>
270 If this is starting to sound scarier than it's worth, relax. Perl has
271 some features to help you avoid its most common pitfalls. The best
272 way to avoid getting confused is to start every program like this:
277 This way, you'll be forced to declare all your variables with my() and
278 also disallow accidental "symbolic dereferencing". Therefore if you'd done
282 [ "fred", "barney", "pebbles", "bambam", "dino", ],
283 [ "homer", "bart", "marge", "maggie", ],
284 [ "george", "jane", "elroy", "judy", ],
289 The compiler would immediately flag that as an error I<at compile time>,
290 because you were accidentally accessing C<@aref>, an undeclared
291 variable, and it would thereby remind you to write instead:
296 X<data structure, debugging> X<complex data structure, debugging>
297 X<AoA, debugging> X<HoA, debugging> X<AoH, debugging> X<HoH, debugging>
298 X<array of arrays, debugging> X<hash of arrays, debugging>
299 X<array of hashes, debugging> X<hash of hashes, debugging>
301 You can use the debugger's C<x> command to dump out complex data structures.
302 For example, given the assignment to $AoA above, here's the debugger output:
305 $AoA = ARRAY(0x13b5a0)
325 Presented with little comment (these will get their own manpages someday)
326 here are short code examples illustrating access of various
327 types of data structures.
329 =head1 ARRAYS OF ARRAYS
330 X<array of arrays> X<AoA>
332 =head2 Declaration of an ARRAY OF ARRAYS
335 [ "fred", "barney" ],
336 [ "george", "jane", "elroy" ],
337 [ "homer", "marge", "bart" ],
340 =head2 Generation of an ARRAY OF ARRAYS
344 push @AoA, [ split ];
349 $AoA[$i] = [ somefunc($i) ];
358 # add to an existing row
359 push @{ $AoA[0] }, "wilma", "betty";
361 =head2 Access and Printing of an ARRAY OF ARRAYS
367 $AoA[1][1] =~ s/(\w)/\u$1/;
369 # print the whole thing with refs
371 print "\t [ @$aref ],\n";
374 # print the whole thing with indices
375 for $i ( 0 .. $#AoA ) {
376 print "\t [ @{$AoA[$i]} ],\n";
379 # print the whole thing one at a time
380 for $i ( 0 .. $#AoA ) {
381 for $j ( 0 .. $#{ $AoA[$i] } ) {
382 print "elt $i $j is $AoA[$i][$j]\n";
386 =head1 HASHES OF ARRAYS
387 X<hash of arrays> X<HoA>
389 =head2 Declaration of a HASH OF ARRAYS
392 flintstones => [ "fred", "barney" ],
393 jetsons => [ "george", "jane", "elroy" ],
394 simpsons => [ "homer", "marge", "bart" ],
397 =head2 Generation of a HASH OF ARRAYS
400 # flintstones: fred barney wilma dino
402 next unless s/^(.*?):\s*//;
403 $HoA{$1} = [ split ];
406 # reading from file; more temps
407 # flintstones: fred barney wilma dino
408 while ( $line = <> ) {
409 ($who, $rest) = split /:\s*/, $line, 2;
410 @fields = split ' ', $rest;
411 $HoA{$who} = [ @fields ];
414 # calling a function that returns a list
415 for $group ( "simpsons", "jetsons", "flintstones" ) {
416 $HoA{$group} = [ get_family($group) ];
419 # likewise, but using temps
420 for $group ( "simpsons", "jetsons", "flintstones" ) {
421 @members = get_family($group);
422 $HoA{$group} = [ @members ];
425 # append new members to an existing family
426 push @{ $HoA{"flintstones"} }, "wilma", "betty";
428 =head2 Access and Printing of a HASH OF ARRAYS
431 $HoA{flintstones}[0] = "Fred";
434 $HoA{simpsons}[1] =~ s/(\w)/\u$1/;
436 # print the whole thing
437 foreach $family ( keys %HoA ) {
438 print "$family: @{ $HoA{$family} }\n"
441 # print the whole thing with indices
442 foreach $family ( keys %HoA ) {
444 foreach $i ( 0 .. $#{ $HoA{$family} } ) {
445 print " $i = $HoA{$family}[$i]";
450 # print the whole thing sorted by number of members
451 foreach $family ( sort { @{$HoA{$b}} <=> @{$HoA{$a}} } keys %HoA ) {
452 print "$family: @{ $HoA{$family} }\n"
455 # print the whole thing sorted by number of members and name
456 foreach $family ( sort {
457 @{$HoA{$b}} <=> @{$HoA{$a}}
462 print "$family: ", join(", ", sort @{ $HoA{$family} }), "\n";
465 =head1 ARRAYS OF HASHES
466 X<array of hashes> X<AoH>
468 =head2 Declaration of an ARRAY OF HASHES
487 =head2 Generation of an ARRAY OF HASHES
490 # format: LEAD=fred FRIEND=barney
493 for $field ( split ) {
494 ($key, $value) = split /=/, $field;
495 $rec->{$key} = $value;
502 # format: LEAD=fred FRIEND=barney
505 push @AoH, { split /[\s+=]/ };
508 # calling a function that returns a key/value pair list, like
509 # "lead","fred","daughter","pebbles"
510 while ( %fields = getnextpairset() ) {
511 push @AoH, { %fields };
514 # likewise, but using no temp vars
516 push @AoH, { parsepairs($_) };
519 # add key/value to an element
520 $AoH[0]{pet} = "dino";
521 $AoH[2]{pet} = "santa's little helper";
523 =head2 Access and Printing of an ARRAY OF HASHES
526 $AoH[0]{lead} = "fred";
529 $AoH[1]{lead} =~ s/(\w)/\u$1/;
531 # print the whole thing with refs
534 for $role ( keys %$href ) {
535 print "$role=$href->{$role} ";
540 # print the whole thing with indices
541 for $i ( 0 .. $#AoH ) {
543 for $role ( keys %{ $AoH[$i] } ) {
544 print "$role=$AoH[$i]{$role} ";
549 # print the whole thing one at a time
550 for $i ( 0 .. $#AoH ) {
551 for $role ( keys %{ $AoH[$i] } ) {
552 print "elt $i $role is $AoH[$i]{$role}\n";
556 =head1 HASHES OF HASHES
557 X<hash of hashes> X<HoH>
559 =head2 Declaration of a HASH OF HASHES
569 "his boy" => "elroy",
578 =head2 Generation of a HASH OF HASHES
581 # flintstones: lead=fred pal=barney wife=wilma pet=dino
583 next unless s/^(.*?):\s*//;
585 for $field ( split ) {
586 ($key, $value) = split /=/, $field;
587 $HoH{$who}{$key} = $value;
591 # reading from file; more temps
593 next unless s/^(.*?):\s*//;
597 for $field ( split ) {
598 ($key, $value) = split /=/, $field;
599 $rec->{$key} = $value;
603 # calling a function that returns a key,value hash
604 for $group ( "simpsons", "jetsons", "flintstones" ) {
605 $HoH{$group} = { get_family($group) };
608 # likewise, but using temps
609 for $group ( "simpsons", "jetsons", "flintstones" ) {
610 %members = get_family($group);
611 $HoH{$group} = { %members };
614 # append new members to an existing family
620 for $what (keys %new_folks) {
621 $HoH{flintstones}{$what} = $new_folks{$what};
624 =head2 Access and Printing of a HASH OF HASHES
627 $HoH{flintstones}{wife} = "wilma";
630 $HoH{simpsons}{lead} =~ s/(\w)/\u$1/;
632 # print the whole thing
633 foreach $family ( keys %HoH ) {
635 for $role ( keys %{ $HoH{$family} } ) {
636 print "$role=$HoH{$family}{$role} ";
641 # print the whole thing somewhat sorted
642 foreach $family ( sort keys %HoH ) {
644 for $role ( sort keys %{ $HoH{$family} } ) {
645 print "$role=$HoH{$family}{$role} ";
651 # print the whole thing sorted by number of members
652 foreach $family ( sort { keys %{$HoH{$b}} <=> keys %{$HoH{$a}} } keys %HoH ) {
654 for $role ( sort keys %{ $HoH{$family} } ) {
655 print "$role=$HoH{$family}{$role} ";
660 # establish a sort order (rank) for each role
662 for ( qw(lead wife son daughter pal pet) ) { $rank{$_} = ++$i }
664 # now print the whole thing sorted by number of members
665 foreach $family ( sort { keys %{ $HoH{$b} } <=> keys %{ $HoH{$a} } } keys %HoH ) {
667 # and print these according to rank order
668 for $role ( sort { $rank{$a} <=> $rank{$b} } keys %{ $HoH{$family} } ) {
669 print "$role=$HoH{$family}{$role} ";
675 =head1 MORE ELABORATE RECORDS
676 X<record> X<structure> X<struct>
678 =head2 Declaration of MORE ELABORATE RECORDS
680 Here's a sample showing how to create and use a record whose fields are of
681 many different sorts:
685 SEQUENCE => [ @old_values ],
686 LOOKUP => { %some_table },
687 THATCODE => \&some_function,
688 THISCODE => sub { $_[0] ** $_[1] },
694 print $rec->{SEQUENCE}[0];
695 $last = pop @ { $rec->{SEQUENCE} };
697 print $rec->{LOOKUP}{"key"};
698 ($first_k, $first_v) = each %{ $rec->{LOOKUP} };
700 $answer = $rec->{THATCODE}->($arg);
701 $answer = $rec->{THISCODE}->($arg1, $arg2);
703 # careful of extra block braces on fh ref
704 print { $rec->{HANDLE} } "a string\n";
707 $rec->{HANDLE}->autoflush(1);
708 $rec->{HANDLE}->print(" a string\n");
710 =head2 Declaration of a HASH OF COMPLEX RECORDS
714 series => "flintstones",
715 nights => [ qw(monday thursday friday) ],
717 { name => "fred", role => "lead", age => 36, },
718 { name => "wilma", role => "wife", age => 31, },
719 { name => "pebbles", role => "kid", age => 4, },
725 nights => [ qw(wednesday saturday) ],
727 { name => "george", role => "lead", age => 41, },
728 { name => "jane", role => "wife", age => 39, },
729 { name => "elroy", role => "kid", age => 9, },
734 series => "simpsons",
735 nights => [ qw(monday) ],
737 { name => "homer", role => "lead", age => 34, },
738 { name => "marge", role => "wife", age => 37, },
739 { name => "bart", role => "kid", age => 11, },
744 =head2 Generation of a HASH OF COMPLEX RECORDS
747 # this is most easily done by having the file itself be
748 # in the raw data format as shown above. perl is happy
749 # to parse complex data structures if declared as data, so
750 # sometimes it's easiest to do that
752 # here's a piece by piece build up
754 $rec->{series} = "flintstones";
755 $rec->{nights} = [ find_days() ];
758 # assume this file in field=value syntax
760 %fields = split /[\s=]+/;
761 push @members, { %fields };
763 $rec->{members} = [ @members ];
765 # now remember the whole thing
766 $TV{ $rec->{series} } = $rec;
768 ###########################################################
769 # now, you might want to make interesting extra fields that
770 # include pointers back into the same data structure so if
771 # change one piece, it changes everywhere, like for example
772 # if you wanted a {kids} field that was a reference
773 # to an array of the kids' records without having duplicate
774 # records and thus update problems.
775 ###########################################################
776 foreach $family (keys %TV) {
777 $rec = $TV{$family}; # temp pointer
779 for $person ( @{ $rec->{members} } ) {
780 if ($person->{role} =~ /kid|son|daughter/) {
784 # REMEMBER: $rec and $TV{$family} point to same data!!
785 $rec->{kids} = [ @kids ];
788 # you copied the array, but the array itself contains pointers
789 # to uncopied objects. this means that if you make bart get
792 $TV{simpsons}{kids}[0]{age}++;
794 # then this would also change in
795 print $TV{simpsons}{members}[2]{age};
797 # because $TV{simpsons}{kids}[0] and $TV{simpsons}{members}[2]
798 # both point to the same underlying anonymous hash table
800 # print the whole thing
801 foreach $family ( keys %TV ) {
803 print " is on during @{ $TV{$family}{nights} }\n";
804 print "its members are:\n";
805 for $who ( @{ $TV{$family}{members} } ) {
806 print " $who->{name} ($who->{role}), age $who->{age}\n";
808 print "it turns out that $TV{$family}{lead} has ";
809 print scalar ( @{ $TV{$family}{kids} } ), " kids named ";
810 print join (", ", map { $_->{name} } @{ $TV{$family}{kids} } );
816 You cannot easily tie a multilevel data structure (such as a hash of
817 hashes) to a dbm file. The first problem is that all but GDBM and
818 Berkeley DB have size limitations, but beyond that, you also have problems
819 with how references are to be represented on disk. One experimental
820 module that does partially attempt to address this need is the MLDBM
821 module. Check your nearest CPAN site as described in L<perlmodlib> for
822 source code to MLDBM.
826 L<perlref>, L<perllol>, L<perldata>, L<perlobj>
830 Tom Christiansen <F<tchrist@perl.com>>