为何std::vector的distance返回值大于size()？求因及修复方案

嘿，这个问题的核心其实是std::vector的迭代器失效机制，你换成vector后踩了一个很常见的容器使用坑：

当你调用currentSet.push_back()时，如果vector当前的容量（capacity）不足以容纳新元素，它会自动重新分配一块更大的内存空间，把原有元素全部复制/移动过去，然后释放旧内存。这时候，所有指向旧内存的迭代器（包括你循环里的iterator变量）都会变成野指针——它们指向的内存已经被释放，完全无效。

这时候你再用distance(iterator, currentSet.end())，本质是在计算一个野指针到新vector末尾的距离，结果完全是随机的（比如你看到的6），没有任何意义。接下来的++iterator操作更是直接访问野指针，必然导致程序崩溃。

而你之前用std::set时没问题，是因为set的底层是红黑树结构，插入/删除操作不会导致其他迭代器失效（只有被删除的那个迭代器会失效），所以原来的逻辑能正常工作。

这里有几种靠谱的修复方式，按推荐程度排序：

1. 改用索引遍历代替迭代器 #

索引不会因为vector扩容而失效，是最稳妥的方式：

vector<pair<int,int>> currentSet;
currentSet.push_back( *(myFields.begin()) );
myFields.erase( myFields.begin() );

// 用索引循环代替迭代器
for (size_t idx = 0; idx < currentSet.size(); ++idx) {
    auto& currentElem = currentSet[idx];
    // 注意：这里你原来的i和j应该是currentElem的first和second吧？
    set<pair<int,int>>::iterator topright = myFields.find( pair<int,int>( currentElem.first, currentElem.second + 1 ) );
    if (topright != myFields.end()) {
        cout << "size " << currentSet.size() << endl;
        cout << "dist to end " << currentSet.size() - idx << endl; // 用索引计算距离
        UniqueInsertion(currentSet, *topright, myFields );
        cout << "size " << currentSet.size() << endl;
        cout << "dist to end " << currentSet.size() - idx << endl;
    }
}

这样即使vector扩容，索引idx依然有效，循环条件idx < currentSet.size()也会实时判断当前元素数量，不会越界。

2. 提前预留足够的容量 #

如果你能预估currentSet最终的最大元素数量，可以在初始化时调用reserve()提前分配足够内存，这样push_back就不会触发扩容，迭代器也就不会失效：

vector<pair<int,int>> currentSet;
currentSet.reserve(100); // 假设最多不会超过100个元素
currentSet.push_back( *(myFields.begin()) );
myFields.erase( myFields.begin() );

// 原来的迭代器循环可以保留
for ( auto iterator=currentSet.begin(); iterator != currentSet.end(); ++iterator ) {
    // ... 原有逻辑
}

但这个方法的局限性是你必须知道大致的最大容量，不然还是可能触发扩容。

3. 优化UniqueInsertion的性能（可选） #

另外提一句：你现在的UniqueInsertion里用std::find遍历vector判断元素是否存在，时间复杂度是O(n)，如果元素多的话效率会很低。原来用set时find是O(logn)，如果性能有要求，可以额外维护一个std::unordered_set<pair<int,int>>来跟踪currentSet里的元素，这样判断唯一性的操作可以降到O(1)：

// 新增一个unordered_set来跟踪currentSet的元素，需要自定义哈希函数
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);
        // 组合哈希值，避免冲突
        return h1 ^ (h2 << 1);
    }
};

unordered_set<pair<int,int>, PairHash> currentSetTracker;

void UniqueInsertion(vector<pair<int,int>> &vect, const pair<int,int> &elem, set<pair<int,int>> &fields, unordered_set<pair<int,int>, PairHash>& tracker) {
    if(tracker.find(elem) == tracker.end()) {
        vect.push_back(elem);
        tracker.insert(elem);
        fields.erase(elem);
    }
}

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