3 perldsc - Manipulating Complex Data Structures in Perl
7 The single feature most sorely lacking in the Perl programming language
8 prior to its 5.0 release was complex data structures. Even without direct
9 language support, some valiant programmers did manage to emulate them, but
10 it was hard work and not for the faint of heart. You could occasionally
11 get away with the C<$m{$LoL,$b}> notation borrowed from I<awk> in which the
12 keys are actually more like a single concatenated string C<"$LoL$b">, but
13 traversal and sorting were difficult. More desperate programmers even
14 hacked Perl's internal symbol table directly, a strategy that proved hard
15 to develop and maintain--to put it mildly.
17 The 5.0 release of Perl let us have complex data structures. You
18 may now write something like this and all of a sudden, you'd have a array
19 with three dimensions!
30 Alas, however simple this may appear, underneath it's a much more
31 elaborate construct than meets the eye!
33 How do you print it out? Why can't you just say C<print @LoL>? How do
34 you sort it? How can you pass it to a function or get one of these back
35 from a function? Is is an object? Can you save it to disk to read
36 back later? How do you access whole rows or columns of that matrix? Do
37 all the values have to be numeric?
39 As you see, it's quite easy to become confused. While some small portion
40 of the blame for this can be attributed to the reference-based
41 implementation, it's really more due to a lack of existing documentation with
42 examples designed for the beginner.
44 This document is meant to be a detailed but understandable treatment of
45 the many different sorts of data structures you might want to develop. It should
46 also serve as a cookbook of examples. That way, when you need to create one of these
47 complex data structures, you can just pinch, pilfer, or purloin
48 a drop-in example from here.
50 Let's look at each of these possible constructs in detail. There are separate
51 documents on each of the following:
55 =item * arrays of arrays
57 =item * hashes of arrays
59 =item * arrays of hashes
61 =item * hashes of hashes
63 =item * more elaborate constructs
65 =item * recursive and self-referential data structures
71 But for now, let's look at some of the general issues common to all
72 of these types of data structures.
76 The most important thing to understand about all data structures in Perl
77 -- including multidimensional arrays--is that even though they might
78 appear otherwise, Perl C<@ARRAY>s and C<%HASH>es are all internally
79 one-dimensional. They can only hold scalar values (meaning a string,
80 number, or a reference). They cannot directly contain other arrays or
81 hashes, but instead contain I<references> to other arrays or hashes.
83 You can't use a reference to a array or hash in quite the same way that
84 you would a real array or hash. For C or C++ programmers unused to distinguishing
85 between arrays and pointers to the same, this can be confusing. If so,
86 just think of it as the difference between a structure and a pointer to a
89 You can (and should) read more about references in the perlref(1) man
90 page. Briefly, references are rather like pointers that know what they
91 point to. (Objects are also a kind of reference, but we won't be needing
92 them right away--if ever.) That means that when you have something that
93 looks to you like an access to two-or-more-dimensional array and/or hash,
94 that what's really going on is that in all these cases, the base type is
95 merely a one-dimensional entity that contains references to the next
96 level. It's just that you can I<use> it as though it were a
97 two-dimensional one. This is actually the way almost all C
98 multidimensional arrays work as well.
100 $list[7][12] # array of arrays
101 $list[7]{string} # array of hashes
102 $hash{string}[7] # hash of arrays
103 $hash{string}{'another string'} # hash of hashes
105 Now, because the top level only contains references, if you try to print
106 out your array in with a simple print() function, you'll get something
107 that doesn't look very nice, like this:
109 @LoL = ( [2, 3], [4, 5, 7], [0] );
113 ARRAY(0x83c38)ARRAY(0x8b194)ARRAY(0x8b1d0)
116 That's because Perl doesn't (ever) implicitly dereference your variables.
117 If you want to get at the thing a reference is referring to, then you have
118 to do this yourself using either prefix typing indicators, like
119 C<${$blah}>, C<@{$blah}>, C<@{$blah[$i]}>, or else postfix pointer arrows,
120 like C<$a-E<gt>[3]>, C<$h-E<gt>{fred}>, or even C<$ob-E<gt>method()-E<gt>[3]>.
122 =head1 COMMON MISTAKES
124 The two most common mistakes made in constructing something like
125 an array of arrays is either accidentally counting the number of
126 elements or else taking a reference to the same memory location
127 repeatedly. Here's the case where you just get the count instead
131 @list = somefunc($i);
132 $LoL[$i] = @list; # WRONG!
135 That's just the simple case of assigning a list to a scalar and getting
136 its element count. If that's what you really and truly want, then you
137 might do well to consider being a tad more explicit about it, like this:
140 @list = somefunc($i);
141 $counts[$i] = scalar @list;
144 Here's the case of taking a reference to the same memory location
148 @list = somefunc($i);
149 $LoL[$i] = \@list; # WRONG!
152 So, just what's the big problem with that? It looks right, doesn't it?
153 After all, I just told you that you need an array of references, so by
154 golly, you've made me one!
156 Unfortunately, while this is true, it's still broken. All the references
157 in @LoL refer to the I<very same place>, and they will therefore all hold
158 whatever was last in @list! It's similar to the problem demonstrated in
159 the following C program:
163 struct passwd *getpwnam(), *rp, *dp;
164 rp = getpwnam("root");
165 dp = getpwnam("daemon");
167 printf("daemon name is %s\nroot name is %s\n",
168 dp->pw_name, rp->pw_name);
173 daemon name is daemon
176 The problem is that both C<rp> and C<dp> are pointers to the same location
177 in memory! In C, you'd have to remember to malloc() yourself some new
178 memory. In Perl, you'll want to use the array constructor C<[]> or the
179 hash constructor C<{}> instead. Here's the right way to do the preceding
180 broken code fragments
183 @list = somefunc($i);
184 $LoL[$i] = [ @list ];
187 The square brackets make a reference to a new array with a I<copy>
188 of what's in @list at the time of the assignment. This is what
191 Note that this will produce something similar, but it's
199 Is it the same? Well, maybe so--and maybe not. The subtle difference
200 is that when you assign something in square brackets, you know for sure
201 it's always a brand new reference with a new I<copy> of the data.
202 Something else could be going on in this new case with the C<@{$LoL[$i]}}>
203 dereference on the left-hand-side of the assignment. It all depends on
204 whether C<$LoL[$i]> had been undefined to start with, or whether it
205 already contained a reference. If you had already populated @LoL with
208 $LoL[3] = \@another_list;
210 Then the assignment with the indirection on the left-hand-side would
211 use the existing reference that was already there:
215 Of course, this I<would> have the "interesting" effect of clobbering
216 @another_list. (Have you ever noticed how when a programmer says
217 something is "interesting", that rather than meaning "intriguing",
218 they're disturbingly more apt to mean that it's "annoying",
219 "difficult", or both? :-)
221 So just remember to always use the array or hash constructors with C<[]>
222 or C<{}>, and you'll be fine, although it's not always optimally
225 Surprisingly, the following dangerous-looking construct will
226 actually work out fine:
229 my @list = somefunc($i);
233 That's because my() is more of a run-time statement than it is a
234 compile-time declaration I<per se>. This means that the my() variable is
235 remade afresh each time through the loop. So even though it I<looks> as
236 though you stored the same variable reference each time, you actually did
237 not! This is a subtle distinction that can produce more efficient code at
238 the risk of misleading all but the most experienced of programmers. So I
239 usually advise against teaching it to beginners. In fact, except for
240 passing arguments to functions, I seldom like to see the gimme-a-reference
241 operator (backslash) used much at all in code. Instead, I advise
242 beginners that they (and most of the rest of us) should try to use the
243 much more easily understood constructors C<[]> and C<{}> instead of
244 relying upon lexical (or dynamic) scoping and hidden reference-counting to
245 do the right thing behind the scenes.
249 $LoL[$i] = [ @list ]; # usually best
250 $LoL[$i] = \@list; # perilous; just how my() was that list?
251 @{ $LoL[$i] } = @list; # way too tricky for most programmers
254 =head1 CAVEAT ON PRECEDENCE
256 Speaking of things like C<@{$LoL[$i]}>, the following are actually the
259 $listref->[2][2] # clear
260 $$listref[2][2] # confusing
262 That's because Perl's precedence rules on its five prefix dereferencers
263 (which look like someone swearing: C<$ @ * % &>) make them bind more
264 tightly than the postfix subscripting brackets or braces! This will no
265 doubt come as a great shock to the C or C++ programmer, who is quite
266 accustomed to using C<*a[i]> to mean what's pointed to by the I<i'th>
267 element of C<a>. That is, they first take the subscript, and only then
268 dereference the thing at that subscript. That's fine in C, but this isn't C.
270 The seemingly equivalent construct in Perl, C<$$listref[$i]> first does
271 the deref of C<$listref>, making it take $listref as a reference to an
272 array, and then dereference that, and finally tell you the I<i'th> value
273 of the array pointed to by $LoL. If you wanted the C notion, you'd have to
274 write C<${$LoL[$i]}> to force the C<$LoL[$i]> to get evaluated first
275 before the leading C<$> dereferencer.
277 =head1 WHY YOU SHOULD ALWAYS C<use strict>
279 If this is starting to sound scarier than it's worth, relax. Perl has
280 some features to help you avoid its most common pitfalls. The best
281 way to avoid getting confused is to start every program like this:
286 This way, you'll be forced to declare all your variables with my() and
287 also disallow accidental "symbolic dereferencing". Therefore if you'd done
291 [ "fred", "barney", "pebbles", "bambam", "dino", ],
292 [ "homer", "bart", "marge", "maggie", ],
293 [ "george", "jane", "alroy", "judy", ],
296 print $listref[2][2];
298 The compiler would immediately flag that as an error I<at compile time>,
299 because you were accidentally accessing C<@listref>, an undeclared
300 variable, and it would thereby remind you to instead write:
302 print $listref->[2][2]
306 The standard Perl debugger in 5.001 doesn't do a very nice job of
307 printing out complex data structures. However, the perl5db that
308 Ilya Zakharevich E<lt>F<ilya@math.ohio-state.edu>E<gt>
309 wrote, which is accessible at
311 ftp://ftp.perl.com/pub/perl/ext/perl5db-kit-0.9.tar.gz
313 has several new features, including command line editing as well
314 as the C<x> command to dump out complex data structures. For example,
315 given the assignment to $LoL above, here's the debugger output:
318 $LoL = ARRAY(0x13b5a0)
336 There's also a lower-case B<x> command which is nearly the same.
340 perlref(1), perldata(1)
344 Tom Christiansen E<lt>F<tchrist@perl.com>E<gt>
347 Sat Oct 7 22:41:09 MDT 1995