C++ list迭代器使用begin()+整数偏移时报错的问题排查

问题场景 #

求解LeetCode题目 Queue Reconstruction by Height（根据身高重建队列） 时，编写了如下C++代码：

vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {  
    list<vector<int>> dyn;
        
    sort(people.begin(), people.end(), [](vector<int> a, vector<int> b) {
        if (a[0] > b[0]) return true;
        else if (a[0] == b[0] && a[1]<b[1]) return true;
        return false;
    });
            
    for (auto p: people) 
        cout << p[0] << " " << p[1] << endl;
        
    for (int i = 0; i != people.size(); i++) {
        auto it = dyn.begin() + people[i][1];
        dyn.insert(it, people[i]);
    }
        
    vector<vector<int>> ans(dyn.begin(), dyn.end());
        
    return ans;    
}

本次使用的测试用例为：

people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

代码编译阶段在如下行抛出错误，已手动推演逻辑确认不存在越界访问：

auto it = dyn.begin() + people[i][1];

对应编译错误信息：

Line 17: Char 35: error: invalid operands to binary expression ('std::__cxx11::list<std::vector<int, std::allocator<int>>, std::allocator<std::vector<int, std::allocator<int>>>>::iterator' (aka '_List_iterator<std::vector<int, std::allocator<int>>>') and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' (aka 'int'))
            auto it = dyn.begin() + people[i][1];
                      ~~~~~~~~~~~ ^ ~~~~~~~~~~~~
/usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_bvector.h:303:3: note: candidate function not viable: no known conversion from 'std::__cxx11::list<std::vector<int>, std::allocator<std::vector<int>>>::iterator' (aka '_List_iterator<std::vector<int, std::allocator<int>>>') to 'std::ptrdiff_t' (aka 'long') for 1st argument
  operator+(ptrdiff_t __n, const _Bit_iterator& __x)
  ^

报错根本原因 #

• C++ STL迭代器按支持的操作能力分为多个类别，std::list底层是双向链表实现，其迭代器属于双向迭代器，仅支持前置/后置自增（++）、自减（--）、解引用、相等/不等比较操作，不支持直接通过+/-运算符做随机位置偏移。只有随机访问迭代器（比如std::vector、std::deque的迭代器）才原生支持it + n这种直接跳转n个位置的写法。
• 代码中dyn.begin() + people[i][1]的写法，试图对不支持算术偏移的list迭代器做加法运算，编译器找不到对应的运算符重载实现，因此抛出操作数不匹配的编译错误。

修复方案 #

• 如果要保留std::list（该场景下list中间插入时间复杂度为O(1)，性能更优），使用标准库的std::advance函数移动迭代器即可，将报错行替换为如下代码：

auto it = dyn.begin();
std::advance(it, people[i][1]);

• 如果不需要考虑插入性能，也可以直接将list<vector<int>> dyn替换为vector<vector<int>> dyn，vector的迭代器是随机访问迭代器，原生支持+偏移操作，原有写法可以直接运行。

内容的提问来源于stack exchange，提问作者mr.loop