关于std::list元素地址、效率及内存等问题的技术咨询

先看你的代码里有个关键问题：你把栈上临时变量local的地址存入了ptr，但local在每次循环迭代结束后就会被销毁，所以ptr里的都是野指针，访问这些指针会导致未定义行为（比如输出乱码或者程序崩溃）。这是因为std::list::push_back会复制local的内容到list的节点内存中，list里的元素和local是完全不同的对象，地址自然不一样。

接下来逐个解答你的问题：

std::list的元素存储在链表节点中，元素的地址在其生命周期内是不会改变的（除非元素被从list中删除）。要获取list中元素的地址，你需要先拿到该元素的迭代器，然后通过&*it的方式取地址：

比如在你的循环中，正确的做法是在push_back之后，获取刚添加元素的迭代器，再取地址存入ptr：

for (auto i = 0; i != 20; ++i) {
    Astruct local;
    local.x[0] = 1.1;
    local.x[1] = 1.2;
    local.rank = i;
    ants.push_back(local);
    // 获取刚添加的元素的迭代器
    auto elem_it = --ants.end();
    // 取list中元素的真实地址存入vector
    if (elem_it->rank % 2 == 0) {
        ptr.push_back(&*elem_it);
    }
}

或者更高效的方式是用emplace_back直接在list中构造元素，同时拿到迭代器（C++11及以后支持）：

for (auto i = 0; i != 20; ++i) {
    // 直接在list节点中构造Astruct，返回指向该元素的迭代器
    auto elem_it = ants.emplace_back();
    elem_it->x[0] = 1.1;
    elem_it->x[1] = 1.2;
    elem_it->rank = i;
    if (elem_it->rank % 2 == 0) {
        ptr.push_back(&*elem_it);
    }
}

你当前的方式是先在栈上构造local，再通过push_back复制到list中，这会触发一次拷贝构造函数调用。对于简单结构体来说开销不大，但如果结构体复杂（比如包含大数组或其他容器），拷贝的开销会很明显。

更高效的方式是使用std::list::emplace_back，它可以直接在list的节点内存中构造元素，避免额外的拷贝操作：

• 如果你的Astruct有自定义构造函数，可以直接传递参数构造：

struct Astruct{ 
    double x[2]; 
    int rank; 
    // 自定义构造函数
    Astruct(double x0, double x1, int r) : x{x0, x1}, rank(r) {}
};

// 循环中直接构造
for (auto i = 0; i != 20; ++i) {
    auto elem_it = ants.emplace_back(1.1, 1.2, i);
    if (elem_it->rank % 2 == 0) {
        ptr.push_back(&*elem_it);
    }
}

这种方式完全避免了栈上临时对象的构造和拷贝，效率更高。

你当前的遍历方法时间复杂度是O(n)，当vector元素较多时效率很低。根据你的使用场景，有两种更优的方案：

方案一：排序+二分查找（O(logn)查询时间） #

如果vector不需要保持插入顺序，可以先对ptr排序，之后每次查询用std::binary_search：

// 排序只需要做一次，比如在所有元素插入完成后
std::sort(ptr.begin(), ptr.end());

// 查询时
std::list<Astruct>::iterator it = ants.begin();
std::advance(it, 2);
if (std::binary_search(ptr.begin(), ptr.end(), &*it)) {
    std::cout << "exists in vector\n";
}

排序的时间是O(nlogn)，之后每次查询都是O(logn)，适合查询次数较多的场景。

方案二：使用std::unordered_set（O(1)平均查询时间） #

如果查询非常频繁，且不需要维护顺序，可以用std::unordered_set<Astruct*>代替vector：

#include <unordered_set>

// 替换vector为unordered_set
std::unordered_set<Astruct*> ptr_set;

// 插入时
ptr_set.insert(&*elem_it);

// 查询时
if (ptr_set.count(&*it)) {
    std::cout << "exists in vector\n";
}

unordered_set的插入和查询平均时间复杂度都是O(1)，比二分查找更高效，但它的内存开销略大，且元素是无序的。

你已经在使用sizeof运算符，这是正确的方式，但需要明确sizeof的作用范围：

• sizeof(Astruct)：返回结构体Astruct本身的大小，包含所有成员变量的大小加上编译器为内存对齐添加的填充字节。比如你的结构体中，两个double（共16字节）+一个int（4字节），默认对齐规则下（比如64位系统对齐到8字节），总大小会是24字节（16+4=20，填充4字节到24）。
• sizeof(ants)：返回std::list对象本身的大小，而不是容器中所有元素的总大小。std::list通常是一个链表的控制结构（比如头指针、尾指针、大小计数器），64位系统下一般是24字节（3个8字节指针）。如果要计算list中元素的总内存占用，应该用ants.size() * sizeof(Astruct)。
• sizeof(ptr)：返回std::vector对象本身的大小，同样不是元素的总大小。std::vector通常包含三个指针（数据起始、数据末尾、容量末尾），64位系统下是24字节。元素总内存占用是ptr.size() * sizeof(Astruct*)。

最后，修正后的完整示例代码：

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <unordered_set>

struct Astruct{ 
    double x[2]; 
    int rank; 
    Astruct(double x0, double x1, int r) : x{x0, x1}, rank(r) {}
};

int main(int argc, char *argv[]) {
    std::list<Astruct> ants;
    std::vector<Astruct*> ptr;
    // 或者用unordered_set：std::unordered_set<Astruct*> ptr_set;

    for (auto i = 0; i != 20; ++i) {
        auto elem_it = ants.emplace_back(1.1, 1.2, i);
        if (elem_it->rank % 2 == 0) {
            ptr.push_back(&*elem_it);
            // ptr_set.insert(&*elem_it);
        }
    }

    // 打印选中元素（现在是合法的地址）
    for(auto p : ptr){
        std::cout << " rank " << p->rank << "\n";
    }

    // 排序后二分查找示例
    std::sort(ptr.begin(), ptr.end());
    std::list<Astruct>::iterator it = ants.begin();
    std::advance(it, 2);
    if(std::binary_search(ptr.begin(), ptr.end(), &*it)){
        std::cout << " exists in vector \n ";
    }

    // 打印内存大小
    std::cout << " sizeof Astruct " << sizeof(Astruct) << "\n";
    std::cout << " sizeof ants (list object) " << sizeof(ants) << "\n";
    std::cout << " total memory of ants elements: " << ants.size() * sizeof(Astruct) << "\n";
    std::cout << " sizeof ptr (vector object) " << sizeof(ptr) << "\n";
    std::cout << " total memory of ptr elements: " << ptr.size() * sizeof(Astruct*) << "\n";

    return 0;
}

内容的提问来源于stack exchange，提问作者dhairyashil