Тесты проводились на VC++7.0 конфигурация Release /Ob2. Celeron 1000 256M WinXP.
Следовательно сделаные выводы касаются только его и его родного STL.

for_all vec             0.114540
for_all_ref vec         0.133207
for_all lst             0.395151
for_all_ref lst         0.395573
vec[i].Hi()             0.115812
arr[i].Hi()             0.025971

for_all vecp            0.672557
for_all_ptr vecp        0.671437
for_all lstp            0.661827
for_all_ptr lstp        0.660183
vecp[i]->Hi()           0.668313
arrp[i]->Hi()           0.684243

Выводы:
Контейнеры обьектов проигрывают обычным массивам причем сильно по сему использование их в критичных по скорости местах не рекомендую.(На не полиморфных обьектах отставание меньше.)
Но при использовании полиморфных контейнеров скорость примерно одинаковая. Особенно меня порадовал std::list который какимто чудом всех сделал(не сильно но сделал). А если учесть что вставка/удаление происходят за константное время то ИМХО для полиморфных контейнеров без альтернатив.

---

Если изменить параметры так(только не забудте сказать линкеру что метр под стек это мало)

    enum
    {
        ArrSize=1000000,
        IterCount=10,
    };

то

for_all vec             0.132461
for_all_ref vec         0.133806
for_all lst             0.388159
for_all_ref lst         0.385950
vec[i].Hi()             0.131733
arr[i].Hi()             0.128936

for_all vecp            0.672520
for_all_ptr vecp        0.671783
for_all lstp            0.650277
for_all_ptr lstp        0.649454
vecp[i]->Hi()           0.673344
arrp[i]->Hi()           0.672832

На длинных дистанциях у массивов начинаются проблемы... А на полиморфных обьектах std::list сделал всех еще сильнее.

---

    enum
    {
        ArrSize=100,
        IterCount=100000,
    };

for_all vec             0.113320
for_all_ref vec         0.115010
for_all lst             0.139346
for_all_ref lst         0.124963
vec[i].Hi()             0.110228
arr[i].Hi()             0.026199

for_all vecp            0.131513
for_all_ptr vecp        0.127315
for_all lstp            0.129233
for_all_ptr lstp        0.132465
vecp[i]->Hi()           0.127523
arrp[i]->Hi()           0.129062

А на коротких дистанциях полиморфные контейнеры почти не отстают.

---

Код:

#define WIN32_LEAN_AND_MEAN
#include <stdio.h>
#include <tchar.h>
#include <windows.h>
#include <vector>
#include <list>
#include <functional>
#include <memory>
unsigned int s;
struct TestBase
{
    virtual void Hi()=0;
    virtual ~TestBase(){}
};
struct Test:TestBase
{
    int g;//Начинка для того чтобы компилятор не соптимизировал циклы в ничто.
    void Hi()
    {
        static int x;
        x+=x+325;
        s+=x;
        g+=s;
    }
};
template<class T, class F>//Просто болие удобная замена for_each если надо перебрать ВСЕ элементы
inline F for_all(T& t, F f)
{
    for(T::iterator i=t.begin(), e=t.end();i!=e;++i)
        (f)(*i);
    return f;
}
template<class T, class F>
inline F for_all_ref(T& t, F f)
{
    for(T::iterator i=t.begin(), e=t.end();i!=e;++i)
        ((*i).*f)();
    return f;
}
template<class T, class F>
inline F for_all_ptr(T& t, F f)
{
    for(T::iterator i=t.begin(), e=t.end();i!=e;++i)
        ((**i).*f)();
    return f;
}
template<class T>//Эмуляция умного указателя
struct SmartPtr//В реальных проектах рекомендую boost::shared_ptr.(boost'а под рукой не было)
{
    T* p_;
    SmartPtr()
        :p_(0)
    {}
    SmartPtr(T* p)
        :p_(p)
    {}
    operator T*()
    {
        return p_;
    }
    T* operator ->()
    {
        return p_;
    }
};
int _tmain(int argc, _TCHAR* argv[])
{
    enum
    {
        ArrSize=10000,
        IterCount=1000,
    };
    Test arr[ArrSize];
    std::auto_ptr<TestBase> arrp[ArrSize];
    unsigned __int64 freq, begin, end;
    QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
    s=0;
    std::vector<Test> vec;
    vec.resize(ArrSize);
    std::list<Test> lst;
    lst.resize(ArrSize);
    std::vector<SmartPtr<TestBase> > vecp;
    std::list<SmartPtr<TestBase> > lstp;
    for(int i=0;i<ArrSize;++i)
    {
        std::auto_ptr<Test> p(new Test());
        arrp[i]=p;
        vecp.push_back(&*arrp[i]);
        lstp.push_back(&*arrp[i]);
    }
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all(vec, std::mem_fun_ref(&Test::Hi));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all vec \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all_ref(vec, &Test::Hi);
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all_ref vec \t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all(lst, std::mem_fun_ref(&Test::Hi));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all lst \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all_ref(lst, &Test::Hi);
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all_ref lst \t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for(int i=0;i<ArrSize;++i)
            vec[i].Hi();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("vec[i].Hi() \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for(int i=0;i<ArrSize;++i)
            arr[i].Hi();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("arr[i].Hi() \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
    printf("\n");
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all(vecp, std::mem_fun(&TestBase::Hi));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all vecp \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all_ptr(vecp, &TestBase::Hi);
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all_ptr vecp \t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all(lstp, std::mem_fun(&TestBase::Hi));
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all lstp \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for_all_ptr(lstp, &TestBase::Hi);
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("for_all_ptr lstp \t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for(int i=0;i<ArrSize;++i)
            vecp[i]->Hi();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("vecp[i]->Hi() \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////
    QueryPerformanceCounter((LARGE_INTEGER*)&begin);
    for(int c=0;c<IterCount;++c)
        for(int i=0;i<ArrSize;++i)
            arrp[i]->Hi();
    QueryPerformanceCounter((LARGE_INTEGER*)&end);
    printf("arrp[i]->Hi() \t\t%f\n", (float(end-begin))/freq);
////////////////////////////////////////////////////////////////////////
    return s;
}