Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Показать сообщение отдельно
Ilot
Эксперт С++
1831 / 1189 / 342
Регистрация: 16.05.2013
Сообщений: 3,139
Записей в блоге: 5
Завершенные тесты: 1
20.03.2015, 13:08

Реализация std::list, сложность list::size()

20.03.2015, 13:08. Просмотров 1185. Ответов 13
Метки (Все метки)

Ответ

Кстати вопрос хороший.
Если посмотреть реализацию списка то увидим:
C++
1
typedef std::bidirectional_iterator_tag    iterator_category;
Однако:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    __distance(_InputIterator __first, _InputIterator __last,
               input_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
 
      typename iterator_traits<_InputIterator>::difference_type __n = 0;
      while (__first != __last)
    {
      ++__first;
      ++__n;
    }
      return __n;
    }
Так как сложность может быть линейной?
DrOffset, посмотрел по приведенной вами ссылке. Код тот же (у меня версия 4.9.0)

Вернуться к обсуждению:
Реализация std::list, сложность list::size()
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2015, 13:08
Готовые ответы и решения:

Реализация std::list<>::begin()
Вопрос строго для знатоков реализации STL. Каким образом реализована...

Вопрос по std::list
Не произойдёт ли здесь какая-нибудь ошибка после удаления элемента из списка? ...

Сортировка std::list
Есть такой фрагмент програми. Создаю функцию для сортировки list. Вроде все...

Вопросы по std::list
1. Как обменять в списке два его элемента? Желательно большое быстродействие :)...

Static std::list
Добрый день, помогите решить проблему. &quot;Каждое статическое поле должно быть...

13
Другие темы раздела
C++ Двумерный массив. Обработка элементов в выделенной области http://www.cyberforum.ru/cpp-beginners/thread1399621.html
Вот текст задачи: Дана действительная матpица A,i,j=1,.,., n. Получить действительную матpицу B,i,j=1,...,n, элемент bij котоpой pавен наименьшему значению элементов данной матpицы, pасположенных...
C++ OpenCv. Получить зеркальное отображение изображения, используя функции: CvScalar, CvGet2D, CvSet2D Доброго времени суток. Прошу помощи в написании кода. Нужно сделать зеркальное отображение изображения, используя только эти функции: CvScalar, CvGet2D, CvSet2D, CvSize... Как я понял для этого нужны... http://www.cyberforum.ru/cpp-beginners/thread1399615.html
C++ Дано действительную матрицу размерности pxq. Определить вектор размерности г, элементы которого равны средним
Дано действительную матрицу размерности pxq. Определить вектор размерности г, элементы которого равны средним арифметическим элементов лент. Входную матрицу и найден вектор вывести на дисплей
Статический константный член-класса C++
Добрый день, что компилятору не нравится? VS 2013 // рекурсивное шаблоное метапрограммирование #include <iostream> using namespace std; template <unsigned long N> struct binary { static...
C++ Сумма факториалов http://www.cyberforum.ru/cpp-beginners/thread1399504.html
прибавление фактариалов 1+2+3
C++ Класс "Студент" #include<iostream> #include<fstream> using namespace std; struct Student { char num; char name; int score; }; int main() подробнее
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru