I highly recommend Thinking in C++, even for complete beginners. I had to skip everything about the C-style stash and stack stuff that popped up throughout the book, but as far as introducing new C++ concepts it did a great job.
Also, even if it's hard to understand, The C++ Programming Language has great exercises for a relative beginner (the only experience I have so far is Thinking in C++ Volume 1 and a bunch of exercises). I'm at Chapter 6 (expressions and statements), and I'm finding exercises that can be very challenging but have definitely made me more proficient with the STL. It also has taught me some stuff I didn't know about the basics.
