9

因为 list 比 forward_list 多了一个指针（前一个指针），所以如果它们都持有相同数量的元素，即 1<<30，list 将使用几乎 1/3 的内存。对？

然后，如果我重复调用 resize 越来越大，forward_list 必须能够调整大小比 list 大得多。

测试代码：

#include<forward_list>
#include<list>
#include<iostream>
int main(){
    using namespace std;
    typedef list<char> list_t;
    //typedef forward_list<char> list_t;
    list_t l;
    list_t::size_type i = 0;
    try{
        while(1){
            l.resize(i += (1<<20));
            cerr<<i<<" ";
        }
    }
    catch(...){
        cerr<<endl;
    }
    return 0;
}

令我惊讶的是，当进程被终止时，它们的大小几乎相同......任何人都可以解释它吗？

4

2 回答 2

9

您应该发现，通过更好的记忆嗅探，您最初假设 astd::list<T>将消耗三倍的能量是正确的。在我的 Windows 机器上，我使用GetProcessMemoryInfo快速创建了一个内存使用程序

这是我的程序的核心：

int main()
{
    size_t initMemory = MemoryUsage();
    std::list<unsigned char> linkedList;

    for (int i = 0; i < ITERATIONS; i++)
        linkedList.push_back(i % 256);
    size_t linkedListMemoryUsage = MemoryUsage() - initMemory;

    std::forward_list<unsigned char> forwardList;
    for (int i = 0; i < ITERATIONS; i++)
        forwardList.push_front(i % 256);
    size_t forwardListMemoryUsage = MemoryUsage() - linkedListMemoryUsage - initMemory;

    std::cout << "Bytes used by Linked List: " << linkedListMemoryUsage << std::endl;
    std::cout << "Bytes used by Forward List: " << forwardListMemoryUsage << std::endl;

    return 0;
}

在发布版本下运行它时的结果：

#define ITERATIONS 128
Bytes used by Linked List: 24576
Bytes used by Forward List: 8192
8192 * 3 = 24576

这是来自cplusplus.com的引述，它甚至说两个容器之间应该存在明显的内存差异。

forward_list 容器和 list 容器之间的主要设计区别在于，第一个容器在内部只保留一个到下一个元素的链接，而后者每个元素保留两个链接：一个指向下一个元素，一个指向前一个元素，允许高效双向迭代，但每个元素消耗额外的存储空间，并且插入和删除元素的时间开销稍高。forward_list 对象因此比列表对象更有效，尽管它们只能向前迭代。

使用列表上的 resize 函数，就像您在发布的代码中所做的那样，内存差异更加明显，std::list<T>消耗的内存是原来的四倍。

于 2012-07-19T15:06:29.747 回答
9

我知道这个问题已经 4 岁了，但接受的答案没有意义（正如贾斯汀雷蒙德指出的那样）。

Nick Babcock 的方法不精确，因为元素的数量太少；堆上总是有一些开销，你也会测量。

为了展示这一点，我使用了更大的数据类型和更多的元素 (4096)：On g++ 6.2.1and linux x64 sizeof(void*) = 8and sizeof (bigDataType_t) = 800( bigData_tis long[100])。

那么我们期待什么呢？每种类型的列表都必须在堆上存储实际数据；std::list每个链接存储 2 个指针（向后和向前），std::forward_list只有一个（向前）。

预期内存std::list： 4096 x 800 + 2 x 8 x 4096 = 3,342,336 bytes

的实际内存std::list：3,415,040 bytes

预期内存std::forward_list： 4096 x 800 + 1 x 8 x 4096 = 3,309,568 bytes

的实际内存std::forward_list：3,382,272 bytes

我使用Massif来获取程序的堆使用情况。

正如我们所看到的，这些数字非常吻合。使用大数据类型时，额外指针的内存没有太大区别！

当使用charas 数据类型（作为 OP）时，预期和实际的内存占用不太合适，很可能是因为一些开销。但是，内存消耗没有因子 3。

std::list: Expected 69,632 bytes, actual: 171,008 bytes

std::forward_list: Expected 36,864 bytes, actual: 138,240 bytes

我的代码：

#include <list>
#include <forward_list>

struct bigData_t {
    long foo[100];
};
typedef bigData_t myType_t;
// typedef char myType_t;

int main()
{
#ifdef USE_FORWARD_LIST
    std::forward_list<myType_t> linkedList;
#else
    std::list<myType_t> linkedList;
#endif
    for (int i = 0; i < 4096; i++) {
        myType_t bigData;
        linkedList.push_front(bigData);
    }
    return 0;
}
于 2016-11-05T23:22:09.097 回答