c++ - std::vector 中 back() 的实现

Question

为什么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] 中获益匪浅，此外，我还将通过使用 vect[0] 而不是 front() 获益匪浅。我意识到我将自己束缚在 vector 上，但在短期内这是我选择的方向(快速获胜)。但是，这让我思考 - 为什么 front() 和 back() 的 vector 实现在幕后使用效率较低的实现？

---

vector 返回() = 410.183862s 墙，0.171601s 用户 + 0.000000s 系统 = 0.171601s CPU (93.3%)

vector [大小()-1] = 410.416969s 墙，0.421203s 用户 + 0.000000s 系统 = 0.421203s CPU (101.0%)

列表返回() = 410.079119s 墙，0.078001s 用户 + 0.000000s 系统 = 0.078001s CPU (98.6%)

双端队列返回() = 410.186574s 墙，0.187201s 用户 + 0.000000s 系统 = 0.187201s CPU (100.3%)

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

Answer 1

C++ 规范定义语义而不是实现。如果这对 std::vector<T, A>::back() 的实现很重要使用与规范建议不同的实现来实现，一个实现应该只做正确的事!显然，它仍然需要传递正确的语义。

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

总而言之，您看到的开销实际上应该进行优化，因为对于体面的编译器:您使用了哪些优化标志？