相关疑难解决方法(0)

在我写自己之前,我会问你们所有人.

我正在寻找一个几乎完全像STL向量的C++类,但是将数据存储到堆栈中的数组中.某种类型的STL分配器类也可以工作,但我试图避免任何类型的堆,甚至是静态分配的每线程堆(尽管其中一个是我的第二选择).堆栈效率更高.

它需要几乎替代使用向量的当前代码.

对于我自己要写的东西,我在考虑这样的事情:

char buffer[4096];
stack_vector<match_item> matches(buffer, sizeof(buffer));

或者类可以在内部分配缓冲区空间.然后它看起来像:

stack_vector<match_item, 256> matches;

我认为如果空间不足,它会抛出std :: bad_alloc,尽管这不应该发生.

更新

使用Chromium的stack_container.h效果很好!

我之所以没想过这样做的原因是我总是忽略了STL集合构造函数的allocator对象参数.我已经使用了几次模板参数来做静态池,但是我从未见过代码或编写任何实际使用过对象参数的代码.我学到了新东西.很酷!

代码有点乱,由于某种原因,GCC强迫我将分配器声明为实际项而不是将其构造为vector的allocator参数.它来自这样的事情:

typedef std::pair< const char *, const char * > comp_list_item;
typedef std::vector< comp_list_item > comp_list_type;

comp_list_type match_list;
match_list.reserve(32);

对此:

static const size_t comp_list_alloc_size = 128;
typedef std::pair< const char *, const char * > comp_list_item;
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type;
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type;

comp_list_alloc_type::Source match_list_buffer;
comp_list_alloc_type match_list_alloc( &match_list_buffer );
comp_list_type match_list( match_list_alloc );
match_list.reserve( comp_list_alloc_size ); …

我正在移植一些C99代码,这些代码大量使用可变长度数组(VLA)到C++.

我用一个在堆上分配内存的数组类替换了VLA(堆栈分配).业绩受到巨大影响,放缓了3.2倍(见下面的基准). 我可以在C++中使用什么快速的VLA替换？我的目标是在重写C++代码时尽量减少性能损失.

向我建议的一个想法是编写一个数组类,其中包含类中的固定大小的存储(即可以是堆栈分配)并将其用于小型数组,并自动切换到更大数组的堆分配.我的实现是在帖子的最后.它工作得相当好,但我仍然无法达到原始C99代码的性能.为了接近它,我必须将这个固定大小的存储空间(MSL下面)增加到我不熟悉的尺寸.即使对于许多不需要它的小型数组,我也不想在堆栈上分配太大的数组,因为我担心它会触发堆栈溢出.C99 VLA实际上不太容易发生这种情况,因为它永远不会使用比所需更多的存储空间.

我遇到了std::dynarray,但我的理解是它没有被标准接受(但是？).

我知道clang和gcc在C++中支持VLA,但我也需要它与MSVC一起工作.事实上,更好的可移植性是重写为C++的主要目标之一(另一个目标是将程序(最初是命令行工具)转换为可重用的库).

基准

MSL指的是我在其上切换到堆分配的数组大小.我对1D和2D数组使用不同的值.

原始C99代码:115秒.
MSL = 0(即堆分配):367秒(3.2x).
1D-MSL = 50,2D-MSL = 1000:187秒(1.63x).
1D-MSL = 200,2D-MSL = 4000:143秒(1.24x).
1D-MSL = 1000,2D-MSL = 20000:131(1.14x).

增加MSL进一步提高性能,但最终程序将开始返回错误的结果(我假设由于堆栈溢出).

这些基准测试是在OS X上使用clang 3.7,但是gcc 5显示了非常相似的结果.

码

这是我使用的当前"小向量"实现.我需要1D和2D矢量.我切换到大小超过堆分配MSL.

template<typename T, size_t MSL=50>
class lad_vector {
    const size_t len;
    T sdata[MSL];
    T *data;
public:
    explicit lad_vector(size_t len_) : len(len_) {
        if (len <= MSL)
            data = &sdata[0];
        else
            data = new …

我可以检查给定指针是否指向由其边界指定的数组中的对象？

template <typename T>
bool points_within_array(T* p, T* begin, T* end)
{
    return begin <= p && p < end;
}

或者,如果p指向数组范围之外的点,指针比较是否会调用未定义的行为？在那种情况下,我该如何解决这个问题？它是否适用于void指针？还是不可能解决？

灵感来自这个关于动态演员的答案void*:

...
bool eqdc(B* b1, B *b2) {
    return dynamic_cast<void*>(b1) == dynamic_cast<void*>(b2);
}
...
int main() {
    DD *dd = new DD();
    D1 *d1 = dynamic_cast<D1*>(dd);
    D2 *d2 = dynamic_cast<D2*>(dd);
    ... eqdc(d1, d2) ...

Run Code Online (Sandbox Code Playgroud)

如果完全定义使用C++的行为(根据03或11个标准),以我想知道比较的(中)相等对两个空指针指向有效的,但不同的对象.

更一般地说,但可能不那么相关,是比较(==或!=)两个void*总是定义的类型的值,还是要求它们持有指向有效对象/存储区域的指针？

我有两个问题:

1)是否可以实现使用alloca在堆栈上分配内存的分配器,否则符合C++ STL？

如果那里有代码,只需将我指向URL即可让我高兴.:-)如果那里没有代码,也许你可以草拟函数allocate和deallocate？

2)如果对上述问题的回答为"是",我想了解如何为类成员在堆栈上分配内存.举个例子,考虑一下

std::vector<int, AllocaAllocator<int> > 

并且假设对该向量的成员函数'resize'的调用首先调用'deallocate'然后'分配'分配器.

调用allocate的范围是成员函数resize的范围.这是不是意味着在该函数调用结束时从堆栈中删除了已分配的内存？

亲切的问候,Bjoern

我试图将Howard stack_allocHinnant 's 与boost rtrees 一起使用，如以下示例所示：

#include "stack_alloc.h"
#include <boost/geometry/index/rtree.hpp>

using NodePoint = boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian>;
using Linear = boost::geometry::index::linear<8, 2>;
using RTree =
    boost::geometry::index::rtree<NodePoint, Linear, boost::geometry::index::indexable<NodePoint>,
                                  boost::geometry::index::equal_to<NodePoint>,
                                  stack_alloc<NodePoint, 100>>;

int main()
{
    RTree my_tree{};

    return 0;
}

无法使用相当大的模板错误堆栈进行编译。我认为问题的核心是：

/usr/local/include/boost/geometry/index/detail/rtree/node/variant_static.hpp:26:7：错误：无效使用了不完整的类型'class boost :: geometry :: index :: detail :: rtree： ：allocators，100>，boost :: geometry :: model :: point，boost :: geometry :: index :: linear <8，2>，boost :: geometry :: model :: box>，boost :: geometry： ：index :: detail :: rtree :: node_variant_static_tag>'

这是带有完整错误的 …

对基于堆栈的分配器的任何建议？(除了建议使用私人/公共成员的课程)

struct Heap
{
    void* heap_start;
    void* heap_end;
    size_t max_end;

    Heap(size_t size)
    {
        heap_start = malloc(size);
        heap_end = heap_start;
        max_end = size + (size_t) heap_start;
    }

    ~Heap()
    {
        ::free(heap_start);
    }

    void* allocate(size_t bytes)
    {

        size_t new_end = ((size_t) heap_end) + bytes;

        if( new_end > max_end )
            throw std::bad_alloc();

        void* output = heap_end;
        heap_end = (void*) new_end;
        return output;
    }

}

#include <iostream>
#include <malloc.h>

void print_vals(int n)
{
    int *arr = (int *)alloca(n);

    for (int i = 0; i < n; i++)
        arr[i] = i;

    for (int i = 0; i < n; i++)
        std::cout << arr[i] << ' ';

    std::cout << '\n';
}

int main()
{
    print_vals(5);
    print_vals(10);
}

当我运行此代码时，每次调用都会收到此错误：

Run-Time Check Failure #4 - Stack area around _alloca memory reserved by this function is corrupted

我使用的是 Visual C++ 2019，stdc++14 和 stdc++17 都会产生相同的错误。

这段代码有什么问题？