为何将vector替换为list后，迭代器相减操作编译失败？

Question #

I originally had a working code using vector:

#include<vector> 
#include<algorithm> 
#include<iostream> 
using namespace std; 
int main() { 
    vector<int> v1; 
    vector<int>::iterator it, low, up; 
    for (int i=1; i<=10; i++) v1.push_back(i); 
    cout << "elements are- \n"; 
    for(it=v1.begin(); it!=v1.end(); it++) cout << *it << " "; 
    sort(v1.begin(), v1.end()); 
    low = lower_bound(v1.begin(), v1.end(), 3); 
    up = upper_bound(v1.begin(), v1.end(), 6); 
    cout << "\npos of low- " << (low-v1.begin()) << "\n"; 
    cout << "pos of up- " << (up-v1.begin()) << endl; 
    return 0; 
}

But when I changed the container type to list, the compilation failed with this error:

In function 'int main()': 20:35: error: no match for 'operator-' (operand types are 'std::list<int>::iterator {aka std::_List_iterator<int>}' and 'std::list<int>::iterator {aka std::_List_iterator<int>}')

I'm wondering why the iterator subtraction line fails after switching to list.

Answer #

The root cause here lies in the different iterator categories supported by vector and list, which dictate what operations the iterators can perform:

• vector uses random-access iterators: Since vector stores elements in a contiguous block of memory (like a dynamic array), its iterators support arithmetic operations like +, -, +=, and -=. This is why low - v1.begin() works in your original code—it directly calculates the index offset between two iterators using pointer arithmetic.

• list uses bidirectional iterators: A list is a doubly linked list, meaning elements are scattered in memory and only connected via pointers to the previous/next node. Bidirectional iterators only support ++ and -- to move one step at a time. They don't support arithmetic operations like subtraction, because there's no way to compute the distance between two iterators without traversing every node in between.

Fix for list #

If you need to calculate the distance between two list iterators, use the standard library function std::distance (include the <iterator> header). It automatically adapts to the iterator type:

• For random-access iterators (like vector), it uses direct subtraction for maximum efficiency.
• For bidirectional iterators (like list), it traverses the nodes between the two iterators to count the distance.

Here's the corrected list version of your code (note we also use list's built-in sort method, since std::sort requires random-access iterators):

#include<list> 
#include<algorithm> 
#include<iostream>
#include<iterator> // Required for std::distance
using namespace std; 
int main() { 
    list<int> v1; 
    list<int>::iterator it, low, up; 
    for (int i=1; i<=10; i++) v1.push_back(i); 
    cout << "elements are- \n"; 
    for(it=v1.begin(); it!=v1.end(); it++) cout << *it << " "; 
    v1.sort(); // Use list's own sort method instead of std::sort
    low = lower_bound(v1.begin(), v1.end(), 3); 
    up = upper_bound(v1.begin(), v1.end(), 6); 
    cout << "\npos of low- " << distance(v1.begin(), low) << "\n"; 
    cout << "pos of up- " << distance(v1.begin(), up) << endl; 
    return 0; 
}

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