One of the features of C++ that sets it apart from C is the addition of Simula-style virtual functions. A virtual function can be overridden in a subclass, so it must be called via an indirection layer.
If you come from Objective-C, you probably understand how this works, because Objective-C exposes some of these implementation details to the programmer. Every Objective-C object has an isa pointer as its first instance variable, which points to the class and is used when looking up methods.
In C++, classes (and namespaces) are only a compile-time construct. Unlike objects, they don't exist at runtime. If a C++ object belongs to a class that declares virtual functions, it contains a pointer to a virtual function table (vtable). This table is the reason why simply rearranging things in a header file breaks binary compatibility in C++. The vtable is nothing more than an array of function pointers. When you call a virtual function, the equivalent C code is something like this:
// C++ object->foo(argument); // C object->vtable(object, argument);
The index in the vtable is determined by the order in which the virtual functions appear in the class definition. If you rearrange them, the order changes, but there's no runtime checking.
The vtable itself is emitted in the compilation unit containing the first non-inline virtual function declared in the class. This rule is required because C++ class declarations typically go into headers, and the methods can be split over several files. Some strange side effects can occur if you add some new methods and then forget to recompile all of the files that provide the implementations.
Again, the vtable layout isn't described by the language, although it's typically part of the platform's C++ ABI specification (if one exists). The vtable often contains things like runtime type information, as well as some extra offset calculation data that is required when dealing with things like virtual base classes.
One somewhat difficult issue with C++ is estimating the cost of virtual function calls. In the simplest case, the difference between a virtual and a non-virtual call is that the virtual call goes via another layer of indirection. This costs a cache line and an extra jump, but that's about all. In fact, it can be faster than a "direct" call, because direct calls are often nothing of the kind.
When you call a function in a shared library, you typically have to call it via a relocation table in that library, which may involve two or three memory accesses. In contrast, a virtual function call is just a jump via a vtable, and therefore may involve better cache usage and even fewer jumps.
Unfortunately, that's not the end of the story. It's much harder for a compiler to inline calls to virtual functions, so even in situations where they're faster in the general case, they may be significantly slower in some common cases.