valgrind is a great tool, combined with gdb. I also use electric fence, as it's a lot faster and it tends to pick up the same stuff as valgrind without giving me as much spurious junk about builtins that there's no helping.
Don't forget to turn on debugging symbols (-g) and turn off optimizations when compiling for any debugger. The flags I usually use for quality control are
-Wall -Wextra -Wshadow -pedantic -g3 -O0 -lefence
-O0 implies -fno-inline, which makes the call stack explicit to avoid a bit of potential confusion looking at traces.
edit: gprof is also pretty great for profiling, just compile with -pg (and without -lefence), run the executable to generate statistics and use gprof <executable name> to get the breakdown. Unfortunately for C++ you almost have to use a post-processor because you will find yourself looking at pages and pages of template crap. Something like kprof truncates that stuff and organizes everything usefully.
Also in the way of C[++] dev tools there's mudflap for hunting down overflow violations, but I haven't really bothered with it because the documentation is poor and I can't figure out how to suppress the many pages of spurious errors having to do with things like <vector> internals it reports for even simple programs.