Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Vlad1slav
21 / 21 / 5
Регистрация: 16.09.2009
Сообщений: 111
#1

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

20.03.2015, 12:30. Просмотров 1022. Ответов 13
Метки нет (Все метки)

Часто приходилось пользоваться Listом, но сейчас столкнулся с небольшой неоднозначностью.

Согласно документации, метод size() в 11 стандарте имеет константную сложность. Чтобы сложность была константной, нужно хранить переменную-счётчик, но в объявлении классов List и _List_base я такого не обнаружил. Зато нащёл метод
C++
1
2
size() const _GLIBCXX_NOEXCEPT
      { return std::distance(begin(), end()); }
что совпадает с данным описанием. Если посмотреть на реализацию distance, то можно убедиться, что для итераторов с произвольным доступом сложность константная, а для остальных - линейная.
Итератор Lista никак не может быть итератором произвольного доступа (ну разве что, в случае извращений с поддержкой вспомогательного массива).

В общем, это ошибка в описании, или я чего-то не догоняю? Какая реально сложность у метода size(), в 11 стандарте?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.03.2015, 12:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация std::list, сложность list::size() (C++):

Реализация std::list<>::begin() - C++
Вопрос строго для знатоков реализации STL. Каким образом реализована &quot;перегрузка&quot; у списка метода begin() только по возвращаемому...

Вопрос по std::list - C++
Не произойдёт ли здесь какая-нибудь ошибка после удаления элемента из списка? std::list&lt;int&gt; myList; std::list&lt;int&gt;::iterator iter; ...

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

Сортировка std::list - C++
Есть такой фрагмент програми. Создаю функцию для сортировки list. Вроде все правильно. В класе перегружены оператори &lt; i =. Не знаю что...

Static std::list - C++
Добрый день, помогите решить проблему. &quot;Каждое статическое поле должно быть проинициализировано до main() явным образом&quot; - как я помню...

std::list<T*> вызвать метод - C++
Как во время просмотра MyList вызвать метод Show() каждого обьекта? class MyVehicle { public: virtual void Show() { /* ......

13
DrOffset
7387 / 4464 / 1013
Регистрация: 30.01.2014
Сообщений: 7,317
20.03.2015, 12:36 #2
Vlad1slav, а версия GCC у тебя какая? Скорее всего просто в твоей версии стандартная библиотека еще не до конца поддерживает С++11.
Смотри тут.
0
ForEveR
В астрале
Эксперт С++
7985 / 4744 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
20.03.2015, 12:38 #3
Vlad1slav,
Complexity
Constant or linear. (until C++11)
Constant. (since C++11)
0
Vlad1slav
21 / 21 / 5
Регистрация: 16.09.2009
Сообщений: 111
20.03.2015, 13:05  [ТС] #4
DrOffset, mingw 4.9.1, версия gcc соответственно 4.9.1.
0
Ilot
Модератор
Эксперт С++
1825 / 1183 / 232
Регистрация: 16.05.2013
Сообщений: 3,119
Записей в блоге: 5
Завершенные тесты: 1
20.03.2015, 13:08 #5
Кстати вопрос хороший.
Если посмотреть реализацию списка то увидим:
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)
0
DrOffset
7387 / 4464 / 1013
Регистрация: 30.01.2014
Сообщений: 7,317
20.03.2015, 13:17 #6
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Ilot Посмотреть сообщение
DrOffset, посмотрел по приведенной вами ссылке. Код тот же (у меня версия 4.9.0)
Нужно еще раз посмотреть, по-внимательней
Оттуда:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#if _GLIBCXX_USE_CXX11_ABI
size_t _M_get_size() const { return _M_impl._M_node._M_data; }
void _M_set_size(size_t __n) { _M_impl._M_node._M_data = __n; }
void _M_inc_size(size_t __n) { _M_impl._M_node._M_data += __n; }
void _M_dec_size(size_t __n) { _M_impl._M_node._M_data -= __n; }
size_t _M_distance(const __detail::_List_node_base* __first, const __detail::_List_node_base* __last) const
{ return _S_distance(__first, __last); }
// return the stored size
size_t _M_node_count() const { return _M_impl._M_node._M_data; }
#else
// dummy implementations used when the size is not stored
size_t _M_get_size() const { return 0; }
void _M_set_size(size_t) { }
void _M_inc_size(size_t) { }
void _M_dec_size(size_t) { }
size_t _M_distance(const void*, const void*) const { return 0; }
// count the number of nodes
size_t _M_node_count() const
{
    return _S_distance(_M_impl._M_node._M_next,
    std::__addressof(_M_impl._M_node));
}
#endif
Добавлено через 5 минут
Цитата Сообщение от Vlad1slav Посмотреть сообщение
mingw 4.9.1, версия gcc соответственно 4.9.1.
Ждать следующей версии. Вот табличка, там четко указано, что std::list в текущей реализации не соответствует С++11. Это связано в техническими проблемами из-за смены ABI.
2
Ilot
Модератор
Эксперт С++
1825 / 1183 / 232
Регистрация: 16.05.2013
Сообщений: 3,119
Записей в блоге: 5
Завершенные тесты: 1
20.03.2015, 13:18 #7
DrOffset, да, но поднимаемся на несколько строчек выше:
C++
1
2
3
4
5
6
7
8
9
10
11
12
 static size_t
    _S_distance(const __detail::_List_node_base* __first,
        const __detail::_List_node_base* __last)
    {
        size_t __n = 0;
        while (__first != __last)
          {
            __first = __first->_M_next;
            ++__n;
          }
        return __n;
    }

Цитата Сообщение от DrOffset Посмотреть сообщение
Ждать следующей версии. Вот табличка, там четко указано, что std::list в текущей реализации не соответствует С++11. Это связано в техническими проблемами из-за смены ABI.
Теперь вопросов быть не должно. Все ясно.
0
DrOffset
7387 / 4464 / 1013
Регистрация: 30.01.2014
Сообщений: 7,317
20.03.2015, 13:22 #8
Ссылка же, которую я привел с текущего состояния реализации на репозитории. Как видно, они поддержку добавили, значит она появится в следующем релизе.

Добавлено через 2 минуты
Цитата Сообщение от Ilot Посмотреть сообщение
да, но поднимаемся на несколько строчек выше:
Не там смотришь.
Смотри реализацию метода size и что он вызывает, он вызывает не distance, а _M_node_count()
C++
1
2
3
4
 /** Returns the number of elements in the %list. */
size_type
size() const _GLIBCXX_NOEXCEPT
{ return this->_M_node_count(); }
Добавлено через 1 минуту
А она в свою очередь в С++11 реализована как:
C++
1
size_t _M_node_count() const { return _M_impl._M_node._M_data; }
2
Ilot
Модератор
Эксперт С++
1825 / 1183 / 232
Регистрация: 16.05.2013
Сообщений: 3,119
Записей в блоге: 5
Завершенные тесты: 1
20.03.2015, 13:23 #9
Цитата Сообщение от DrOffset Посмотреть сообщение
Смотри реализацию метода size и что он вызывает, он вызывает не distance, а _M_node_count()
А _M_node_count() в свою очередь вызывает _S_distance(...). Вот я и привел код этой функции. Все логично
0
DrOffset
20.03.2015, 13:25
  #10

Не по теме:

Цитата Сообщение от Ilot Посмотреть сообщение
А _M_node_count() в свою очередь вызывает _S_distance(...). Вот я и привел код этой функции. Все логично
Господи, ну удели ты больше 3х секунд чтению кода

0
Vlad1slav
21 / 21 / 5
Регистрация: 16.09.2009
Сообщений: 111
20.03.2015, 13:26  [ТС] #11
ForEveR, я тоже умею читать документацию. Но тему я создал неспроста.

В общем решил сам проверить:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <list>
#include <iostream>
 
#include <ctime>
#include <cstdio>
 
int main(void)
{
  std::list<int> l;
  const int N = 1000000;
  for (int i = 0; i < N; i++)
      l.push_back(1);
 
  double start = clock();
  for (int i = 0; i < 1000; i++)
      l.size();
  std::cout << (clock() - start) / CLOCKS_PER_SEC << std::endl;
 
  return 0;
}
При N = 10^6, время работы 14,29 сек
При N = 10^5, время работы 1,426 сек
Очевидно, что время линейное...
0
Ilot
Модератор
Эксперт С++
1825 / 1183 / 232
Регистрация: 16.05.2013
Сообщений: 3,119
Записей в блоге: 5
Завершенные тесты: 1
20.03.2015, 13:28 #12
DrOffset, точно мой косяк. Директиву #else не заметил
1
ForEveR
В астрале
Эксперт С++
7985 / 4744 / 321
Регистрация: 24.06.2010
Сообщений: 10,547
Завершенные тесты: 3
20.03.2015, 13:44 #13
Vlad1slav, Вопрос же был:
В общем, это ошибка в описании, или я чего-то не догоняю? Какая реально сложность у метода size(), в 11 стандарте?
Реальная сложность описана в документации. То, что в библиотеке это не реализованно - не проблема стандарта.

Добавлено через 4 минуты
Допустим в libc++, которая стоит у меня (далеко не новейшая), это реализовано.

C++
1
2
3
4
5
6
7
8
    _LIBCPP_INLINE_VISIBILITY
    size_type size() const _NOEXCEPT     {return base::__sz();}
 
    typedef __list_imp<_Tp, _Alloc> base;
    _LIBCPP_INLINE_VISIBILITY
          size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
 
    __compressed_pair<size_type, __node_allocator> __size_alloc_;
1
Vlad1slav
21 / 21 / 5
Регистрация: 16.09.2009
Сообщений: 111
20.03.2015, 16:05  [ТС] #14
ForEveR, Мой косяк, несовсем корректно вопрос поставил. Просто хотелось услышать небольшую аргументацию, как это работает (т.е. как так получилось, что переменная size нигде не храниться, а время констатное получается).

В общем, всем спасибо, разобрался.
Значит всё-таки List отдельно хранит размер в 11 стандарте.
0
20.03.2015, 16:05
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2015, 16:05
Привет! Вот еще темы с ответами:

Remove_if для std::list - C++
Здравствуйте! Помогите мне разобраться,пожалуйста.Перечитал кучу всего,но так и не понял ,что можно писать в аргументе метода remove_if. ...

Непосредственное удаление из std::list - C++
Собственно проблема вот в чем раньше, когда я создавал игру, у меня были самодельные листы типа struct List { T data; ...

Std::list, ошибка LNK2019 - C++
Добрый день! // element.h class Element { public: Element(){}; ~Element(){};

Удаление значения в std::list - C++
Имеем метод для удаления, где value - предов. значение, а list&lt;films&gt; coll - копия др. списка(который уже наполнен данными). ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.