3

为什么 Vector back() 方法是用迭代器来实现的

reference back()
{   // return last element of mutable sequence
    return (*(end() - 1));
}

而不是像...

return (*(_Myfirst + size()));

这个问题的背景：

我最近一直在优化一些遗留代码（分配器实现），并注意到大量时间都花在std::vector::back(). 所以我使用不同的集合（Vector vs List vs Deque）做了一些实验，因为back()基本上是检索集合中的最后一个元素，所以我也比较vector::back()了vector[size()-1]

这是我用来测试的代码：

#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <boost/timer/timer.hpp>

int RandomNumber () { return (rand()%100); }



void doVector( std::vector<int>& test_vec )
{
    std::cout << "vect back() = " << test_vec.back() << std::endl;
    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_vec.back();
    }
}

void doVector2( std::vector<int>& test_vec )
{
    std::cout << "vect [size()-1] = " << test_vec[test_vec.size()-1] << std::endl;
    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_vec[test_vec.size()-1];
    }

}


void doList( std::vector<int>& test_vec )
{
    std::list<int> test_list(test_vec.begin(),test_vec.end());
    std::cout << "list back() = " << test_list.back() << std::endl;

    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_list.back();
    }

}

void doDeque( std::vector<int>& test_vec )
{
    std::deque<int> test_deq(test_vec.begin(),test_vec.end());
    std::cout << "Deque back() = " << test_deq.back() << std::endl;

    {
        boost::timer::auto_cpu_timer t;
        for (int i = 0; i < 100000000; i++ )
            test_deq.back();
    }

}


int _tmain(int argc, _TCHAR* argv[])
{
    std::vector<int> test_vec(100);
    std::generate(test_vec.begin(), test_vec.end(), RandomNumber );

    doVector(test_vec);
    doVector2(test_vec);
    doList(test_vec);
    doDeque(test_vec);
}

结果是：

删除了结果，因为我打开了调试/关闭了发布时间的优化，以秒为单位 - 我应该已经看到了

显然，我会从使用 vect[size() - 1] 中获得显着收益，此外，我还将通过在 front() 上使用 vect[0] 获得更多收益。我意识到我将自己与矢量联系在一起，但在短期内这是我选择的方向（快速获胜）。但是，这让我想到 - 为什么 front() 和 back() 的向量实现在底层使用效率较低的实现？

vect back() = 41 0.183862s 墙，0.171601s 用户 + 0.000000s 系统 = 0.171601s CPU (93.3%)

vect [size()-1] = 41 0.416969s 墙，0.421203s 用户 + 0.000000s 系统 = 0.421203s CPU (101.0%)

list back() = 41 0.079119s 墙，0.078001s 用户 + 0.000000s 系统 = 0.078001s CPU (98.6%)

Deque back() = 41 0.186574s 墙，0.187201s 用户 + 0.000000s 系统 = 0.187201s CPU (100.3%)

很明显，当我进行分析时，我看到了错误的结果——因为这完全支持了实现的选择。向在此编辑之前查看此内容的人道歉......

4

2 回答 2

4

C++ 规范定义了语义而不是实现。如果它对std::vector<T, A>::back()使用不同于规范建议的实现的实现很重要，那么实现应该做正确的事情！显然，它仍然需要提供正确的语义。

指定它的基本原因可能来自原始实现：迭代器类型std::vector<T, A>只是 a T*（尽管由于各种原因已经过时，但它仍然是一个有效的实现）。现代std::vector<T, A>实现倾向于使用简单的指针包装器。

话虽如此，您看到的开销实际上应该进行优化，因为对于体面的编译器：您使用了哪些优化标志？

于 2012-10-28T19:09:34.547 回答
1

根据您的问题_Myfirst + size()，我猜您正在使用MSVC具有iterator调试功能，您确定您正在使用release构建进行测试，因为在debug构建iterator调试中需要一些额外的时间，但在release模式下它们都需要相同的时间（至少在我的机器上使用MSVC 2010）

于 2012-10-28T19:13:22.743 回答