17

我可以假设对于任何类型T,该类型std::list<T>将具有相同的恒定大小吗?为了清楚起见,我的意思是“主要”类型本身的大小,而不是它分配的内存的大小。

对我来说,假设它T本身的大小应该只影响使用分配器分配的列表节点的大小,这似乎是合乎逻辑的。

但是,有两件事可能会导致sizeof(std::list<T>)我能想到的变化:

  1. 一个标准 C++ 库试图std::list通过将一些T实例放入std::list<T>自身来“优化”类型。这对我来说似乎是个坏主意,它可能违反了标准提出的“恒定时间”要求;
  2. 一种标准 C++,具有std::list<T>某些类型的库特化,这些特化具有不同的大小。

我想不出(1)或(2)的任何用途,但我可能错了。

我正在考虑实现的是使用std::list<T>内部模板类使用固定大小的切片分配器。


注意:这是关于不同类型的差异T,而不是不同分配器的差异。我将对所有实例化进行显式控制,并且它们都将使用std::allocator.

4

3 回答 3

8

的,它可以。

list<T>据我所知,该标准并未精确保证对象的大小。不过,还有其他保证。


让我们揭穿一些事情:

一个标准 C++ 库试图std::list通过将一些T实例放入std::list<T>自身来“优化”类型。这对我来说似乎是个坏主意,它可能违反了标准提出的“恒定时间”要求;

只要这个数字是有界的,它就不会以任何方式打破“恒定时间”的要求,因为 O(5) 是 O(1)。但是,在splice操作期间,节点应该从一个列表移动到另一个列表,而不需要在内存中移动。因此禁止本地存储。

一种标准 C++,具有std::list<T>某些类型的库特化,这些特化具有不同的大小。

由于我们已经排除了本地存储的可能性,因此很难想象基本std::list<T>类型本身的任何其他变体。


让我们担心什么是重要的:

a 分配的内存std::list<T>由它的第二个模板参数提供:分配器。大多数分配器(包括std::allocator<T>默认分配器)使用简单的指针类型:T*...但是分配器应该可以随意更改这种类型。

因此,通过更改allocator参数(更准确地说,它的指针类型),自然会std::list在我所见过的所有实现中更改容器的大小。

请注意,分配器本身可以专门用于某些类型,但是使用重新绑定魔法有点难以实现。

于 2012-08-03T11:21:22.860 回答
4

Chapter 23 of the C++11 standard (Containers) does not say anything about their sizes, so technically you cannot assume that the size will be constant. Implementors could (in theory) specialize some container for a specific primitive in a way that affects its footprint.

In practice, you could use a static assertion that sizeof(list<T>) == sizeof(list<int>) and use sizeof(list<int>) as the "fixed" size. Worst thing that can happen is a compile-time error.

于 2012-08-03T11:19:14.060 回答
0

类使用std::list<T>的固定大小的切片分配器几乎没有意义,除非您还为列表本身使用固定大小的切片分配器,列表项的分配可能比列表标题的分配更多。

现在您当然可以使用列表的第二个模板参数分配器为列表提供您自己的固定大小的切片分配器。然而有一个转折:你不知道切片应该有多大。Alist<T>接受allocator<T>,但它真正需要的是allocator<U>其中 U 是一个包含 prev/next 指针和 T 的结构。为了得到它,它调用rebind了具有签名的方法template <typename T> template <typename T> allocator<U> allocator<T>::rebind<U>()

因为我实际上需要这样做一次,所以我所做的是创建一个对象,该对象包含多个切片大小的分配器集合。分配器本身拥有一个指向 this 的共享指针和一个指向分配器的共享指针,以获取其参数的大小。在重新绑定时,我从集合中提取了适当的分配器,或者如果它不存在则创建一个。如果这样做,它将作为副作用解决列表的分配,因为如果有多个大小,它将为每个大小创建单独的池。而且不会有很多不同的大小,因为对象不会很大。

于 2012-08-03T11:33:53.493 回答