The SGI STL implementation does contain a non-standard hash_map template; that would be a more appropriate comparison.

This made me think a bit further. Although I myself have never felt that the array implementation of Perl stands in my way (and I have never heard of anyone, who has ever done so, so it seems a one-fits-all solution), it would be pretty nice to be able to choose the type of your arrays in runtime. This way, you could choose the most appropriate data structure for your specific needs.

But, with the advent of Perl 6, you can do it. I imagine something along the lines of:

  role List_a_la_STL_vector {
     ...
     multi method Num postcircumfix:<<[]>>(
         Num @self is constant : Num $index){
           # return the $index element
        }
     ...
   }

  role List_a_la_STL_deque {
     ...
     multi method Num postcircumfix:<<[]>>(
         Num @self is constant : Num $index){
           # return the $index element
        }
     ...
   }

   ...

   # use vector just like an STL vector
   my  @vector does List_a_la_STL_vector;
   ...
   # use vector just like an STL deque
   my  @deque does List_a_la_STL_deque;
[download]

This is a really perlish solution. You are not forced to step into the realms of computer science and be intimate with storage requirements and complexity of the underlying data stuctures, but if you do, you can be much more efficient.