У меня есть отсортированный list<int>, и я добавлю в него элемент с таким индексом, чтобы список сохранял сортировку:
list<int> l;
list<int>::iterator upper;
for(int i = 0; i < n; i++) l.push_back(i);
int x = 15;
upper = upper_bound (l.begin(), l.end(), x);
l.insert(up, aux);
cout<<"Added "<<x<<" at index "<<(upper - l.begin())<<endl;
Разница между итераторами в cout не работает для списков, так как я могу быстро найти этот индекс?
Игнорируя for, я хочу, чтобы эта полная операция была O (lg (n)), что является временем двоичного поиска.
Если бы я мог получить этот индекс в постоянное время, было бы здорово. Использование vector не вариант.