That's because the programming language
is C++.
Do I have news for you. Stop using the crappy Arduino IDE! Start using Atmel Studios.
http://www.atmel.com/microsite/atmel_studio6/
Visual Studio based, sooo much easier to manage multi-file projects.
As far as I was aware, you could create template classes. I haven't ever had a reason to try it as of yet, though.
Also, it's not that it doesn't support dynamic memory allocation, it just uses the C way to do it, malloc and free.
But you can define the new and delete operators. Someone made a really nice header for all of the C++ memory allocation functions. You can throw these in your arduino library folder, include them in your project, and then you can use new and delete operators. Although, you have to be careful when dynamically allocated memory because you only have 1kb.
New.h -
http://pastebin.com/04UyLiWE
New.cpp -
http://pastebin.com/Kg2JPfzR
As for STL, there is a light version of the STL build for AVR chips that includes the ability to use algorithm, limits, map, queue, set, deque, pair, vectors, and several other STL containers. I can't remember where I originally found it, but i've uploaded it to my mediafire here:
http://www.mediafire.com/?rchypr265b2nl62
And the Atmega328p is a very basic chip. It operates at 16MHz, it's not meant to be a powerhouse. That, and they're dirt cheap. 32K of flash memory, and 1Kb RAM is wayyy more than i'll ever use for any project i'll do with an arduino. If you want to do heavy operations you should check out ARM microcontrollers. (those are the ones used in several different android smartphones)
Anyway, using the avr-stil, i made a nice system for my RFID locks. It stores up to 10 RFID tags in EEPROM, and you can erase/add new cards with a master key. It doesn't sound like much but the code is actually pretty intense, and it only uses 10834 bytes of the program flash (33%), and 407 bytes of memory (19.9%). So I either did an awesome job at reserving memory, or 32kb is plenty for arduino related projects.
EDIT:
You updated your post while i was typing this one, haha.
Next you want to buy an LCD screen and make a text based adventure with your buttons as the controller!