如何避免std :: vector <>初始化其所有元素？

Question

编辑:我编辑了问题及其标题更精确.

考虑以下源代码:

#include <vector>
struct xyz {
    xyz() { } // empty constructor, but the compiler doesn't care
    xyz(const xyz& o): v(o.v) { } 
    xyz& operator=(const xyz& o) { v=o.v; return *this; }
    int v; // <will be initialized to int(), which means 0
};

std::vector<xyz> test() {
    return std::vector<xyz>(1024); // will do a memset() :-(
}

...我怎么能避免vector <>分配的内存用它的第一个元素的副本进行初始化,这是一个O(n)操作我宁愿为了速度而跳过,因为我的默认构造函数什么都不做？

如果不存在通用的解决方案,那么g ++特定的解决方案就可以做到(但我找不到任何属性来执行此操作).

编辑:生成的代码如下(命令行:arm-elf-g ++ - 4.5 -O3 -S -fno-verbose-asm -o-test.cpp | arm-elf-c ++ filt | grep -vE'^ [[: space:]] + [.@].*$')

test():
    mov r3, #0
    stmfd   sp!, {r4, lr}
    mov r4, r0
    str r3, [r0, #0]
    str r3, [r0, #4]
    str r3, [r0, #8]
    mov r0, #4096
    bl  operator new(unsigned long)
    add r1, r0, #4096
    add r2, r0, #4080
    str r0, [r4, #0]
    stmib   r4, {r0, r1}
    add r2, r2, #12
    b       .L4          @
.L8:                     @
    add     r0, r0, #4   @
.L4:                     @
    cmp     r0, #0       @  fill the memory
    movne   r3, #0       @
    strne   r3, [r0, #0] @
    cmp     r0, r2       @
    bne     .L8          @
    str r1, [r4, #4]
    mov r0, r4
    ldmfd   sp!, {r4, pc}

编辑:为了完整性,这里是x86_64的程序集:

.globl test()
test():
LFB450:
    pushq   %rbp
LCFI0:
    movq    %rsp, %rbp
LCFI1:
    pushq   %rbx
LCFI2:
    movq    %rdi, %rbx
    subq    $8, %rsp
LCFI3:
    movq    $0, (%rdi)
    movq    $0, 8(%rdi)
    movq    $0, 16(%rdi)
    movl    $4096, %edi
    call    operator new(unsigned long)
    leaq    4096(%rax), %rcx
    movq    %rax, (%rbx)
    movq    %rax, 8(%rbx)
    leaq    4092(%rax), %rdx
    movq    %rcx, 16(%rbx)
    jmp     L4          @
L8:                     @
    addq    $4, %rax    @
L4:                     @
    testq   %rax, %rax  @ memory-filling loop
    je      L2          @
    movl    $0, (%rax)  @
L2:                     @
    cmpq    %rdx, %rax  @
    jne     L8          @
    movq    %rcx, 8(%rbx)
    movq    %rbx, %rax
    addq    $8, %rsp
    popq    %rbx
    leave
LCFI4:
    ret
LFE450:
EH_frame1:
LSCIE1:
LECIE1:
LSFDE1:
LASFDE1:
LEFDE1:

编辑:我认为结论是std::vector<>当你想避免不必要的初始化时不使用.我最终展开了我自己的模板化容器,它表现得更好(并且具有适用于neon和armv7的专用版本).

Answer 1

分配的元素的初始化由Allocator模板参数控制,如果您需要自定义,则自定义它.但请记住,在脏黑客的情况下,这很容易结束,因此请谨慎使用.例如,这是一个非常脏的解决方案.它将避免初始化,但它很可能会在性能上更差,但出于演示的缘故(因为人们已经说过这是不可能的!......不可能不是C++程序员的词汇!):

template <typename T>
class switch_init_allocator : public std::allocator< T > {
  private:
    bool* should_init;
  public:
    template <typename U>
    struct rebind {
      typedef switch_init_allocator<U> other;
    };

    //provide the required no-throw constructors / destructors:
    switch_init_allocator(bool* aShouldInit = NULL) throw() : std::allocator<T>(), should_init(aShouldInit) { };
    switch_init_allocator(const switch_init_allocator<T>& rhs) throw() : std::allocator<T>(rhs), should_init(rhs.should_init) { };
    template <typename U>
    switch_init_allocator(const switch_init_allocator<U>& rhs, bool* aShouldInit = NULL) throw() : std::allocator<T>(rhs), should_init(aShouldInit) { };
    ~switch_init_allocator() throw() { };

    //import the required typedefs:
    typedef typename std::allocator<T>::value_type value_type;
    typedef typename std::allocator<T>::pointer pointer;
    typedef typename std::allocator<T>::reference reference;
    typedef typename std::allocator<T>::const_pointer const_pointer;
    typedef typename std::allocator<T>::const_reference const_reference;
    typedef typename std::allocator<T>::size_type size_type;
    typedef typename std::allocator<T>::difference_type difference_type;

    //redefine the construct function (hiding the base-class version):
    void construct( pointer p, const_reference cr) {
      if((should_init) && (*should_init))
        new ((void*)p) T ( cr );
      //else, do nothing.
    };
};

template <typename T>
class my_vector : public std::vector<T, switch_init_allocator<T> > {
  public:
    typedef std::vector<T, switch_init_allocator<T> > base_type;
    typedef switch_init_allocator<T> allocator_type;
    typedef std::vector<T, allocator_type > vector_type;
    typedef typename base_type::size_type size_type;
  private:
    bool switch_flag; //the order here is very important!!
    vector_type vec;
  public:  
    my_vector(size_type aCount) : switch_flag(false), vec(aCount, allocator_type(&switch_flag)) { };
    //... and the rest of this wrapper class...
    vector_type& get_vector() { return vec; };
    const vector_type& get_vector() const { return vec; };
    void set_switch(bool value) { switch_flag = value; };
};

class xyz{};

int main(){
  my_vector<xyz> v(1024); //this won't initialize the memory at all.
  v.set_switch(true); //set back to true to turn initialization back on (needed for resizing and such)
}

当然,上面的内容很笨拙而且不推荐,当然也不会比实际让内存充满第一个元素的副本更好(特别是因为使用这个标志检查会妨碍每个元素构造) .但是,当想要优化STL容器中元素的分配和初始化时,这是一个探索的途径,所以我想展示它.关键是,你可以注入代码的唯一地方是阻止std :: vector容器调用copy-constructor来初始化你的元素,这是在vector的allocator对象的construct函数中.

此外,您可以取消"切换"并简单地执行"no-init-allocator",但是,您还可以关闭在调整大小期间复制数据所需的复制构造(这将使此向量类更多不太有用).

Answer 2

这是一个奇怪的角落vector.问题不在于你的元素是值初始化的......而是第一个原型元素中的随机内容被复制到向量中的所有其他元素.(此行为随C++ 11而改变,该值初始化每个元素).

这是(/ was)完成的原因:考虑一些引用计数对象...如果你构造一个vector初始化为这样一个对象的1000个元素的请求,你显然想要一个引用计数为1000的对象,而不是1000独立的"克隆".我说"显然"是因为首先计算了对象引用意味着非常需要.

无论如何,你几乎没有运气.实际上,vector确保所有元素都是相同的,即使它同步的内容恰好是未初始化的垃圾.

在非标准g ++特定的快乐黑客的领域,我们可以利用vector界面中的任何公共模板化成员函数作为后门来简单地通过专门化某些新类型的模板来更改私有成员数据.

警告:不仅仅是为了这个"解决方案",而是为了避免默认构造的整个努力... 不要对具有重要不变量的类型执行此操作 - 您打破封装并且可以轻松地拥有vector自己或您尝试调用的某些操作operator=(),复制构造函数和/或析构函数,其中*this/左侧和/或右侧参数不遵守这些不变量.例如,避免使用您希望为NULL的指针的值类型或有效对象,引用计数器,资源句柄等.

#include <iostream>
#include <vector>

struct Uninitialised_Resize
{
    explicit Uninitialised_Resize(int n) : n_(n) { }
    explicit Uninitialised_Resize() { }
    int n_;
};

namespace std
{
    template <>
    template <>
    void vector<int>::assign(Uninitialised_Resize ur, Uninitialised_Resize)
    {
        this->_M_impl._M_finish = this->_M_impl._M_start + ur.n_;

        // note: a simpler alternative (doesn't need "n_") is to set...
        //   this->_M_impl._M_finish = this->_M_impl._M_end_of_storage;
        // ...which means size() will become capacity(), which may be more
        // you reserved() (due to rounding; good) or have data for
        // (bad if you have to track in-use elements elsewhere,
        //  which makes the situation equivalent to just reserve()),
        // but if you can somehow use the extra elements then all's good.
    }
}

int main()
{
    {
        // try to get some non-0 values on heap ready for recycling...
        std::vector<int> x(10000);
        for (int i = 0; i < x.size(); ++i)
            x[i] = i;
    }

    std::vector<int> x;
    x.reserve(10000);
    for (int i = 1; i < x.capacity(); ++i)
        if (x[0] != x[i])
        {
            std::cout << "lucky\n";
            break;
        }
    x.assign(Uninitialised_Resize(1000), Uninitialised_Resize());

    for (int i = 1; i < x.size(); ++i)
        if (x[0] != x[i])
        {
            std::cout << "success [0] " << x[0] << " != [" << i << "] "
                << x[i] << '\n';
            break;
        }
}

我的输出:

lucky
success [0] 0 != [1] 1

这表明新的vector重新分配了第一个向量在超出范围时释放的堆,并显示值没有被赋值所破坏.当然,没有办法知道其他一些重要的类不变量是否在没有vector仔细检查来源的情况下失效,私人成员的确切名称/导入可能随时变化....