Re: Perl and C++/STL

std::map is required by the ANSI C++ standard to be implemented as a red-black tree, which has logarithmic lookup time. Hash tables have roughly constant lookup time, so it's not surprising that for largish n the hash will outperform the tree. Unfortunately, the STL in the current standard doesn't provide for a hash-based associative container type, so you can't really compare apples to apples here. The SGI STL implementation does contain a non-standard hash_map template; that would be a more appropriate comparison.

The moral of the story is that once your problem becomes large enough, asymptotic algorithm performance dominates the constant factors separating a "slow" language from a "fast" one.

Update:

As for your pre-allocation concerns with std::vector, there's good news. You will indeed get segfaults using the square-bracket notation for entries that don't exist (vector<int> a(1); cout << a[3];), but the .at() accessor performs the equivalent function after doing a bounds check (it throws an exception if you violate the bounds instead of segfaulting). And if you find yourself needing to increase the size of the vector, the .resize() method does just that for whatever size you need.

Comment on Re: Perl and C++/STL Select or Download Code

Replies are listed 'Best First'.
Re^2: Perl and C++/STL by rg0now (Chaplain) on Mar 11, 2005 at 11:08 UTC
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. rg0now	[reply] [d/l]

Replies are listed 'Best First'.

Re^2: Perl and C++/STL
by rg0now (Chaplain) on Mar 11, 2005 at 11:08 UTC

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]

rg0now

[reply]
[d/l]