102 / 75 / 17
Регистрация: 23.07.2014
Сообщений: 877
Записей в блоге: 1
1

Реализация STL-совместимого списка

06.10.2014, 13:50. Показов 1183. Ответов 7
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Как известно (курим Мейерса), в STL для класса list обычно выбирается O(1) время работы метода splice, а метод size() имеет линейную сложность, потому что чай или с молоком, или с лимоном, но не обои сразу. Однако, стандарт Си++11 требует от обоих методов время O(1). Как это можно реализовать? Ну и вопрос риторический: почему в GNU'сной реализации и в stlport size() всё равно определён как std::distance(begin(), end()), невзирая ни на какой Си++11?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.10.2014, 13:50
Ответы с готовыми решениями:

Реализация примитивного STL совместимого контейнера
Как то застрял на этом. Как правильно объявить все typedef для итератора? Нужен минимальный...

STL реализация графа c++
пример реализации графа с весом

Нужна реализация STL
Привет всем! Где мне можно найти реализацию map, set, string и list из стандартной библиотеки...

Реализация list из STL
Можете скинуть реализацию класса list из STL.

7
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
06.10.2014, 14:01 2
CyberSolver, clang кеширует к примеру.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template <class _Tp, class _Alloc>
class __list_imp
{
// ...
__compressed_pair<size_type, __node_allocator> __size_alloc_;
// ...
    _LIBCPP_INLINE_VISIBILITY
          size_type& __sz() _NOEXCEPT {return __size_alloc_.first();}
    _LIBCPP_INLINE_VISIBILITY
    const size_type& __sz() const _NOEXCEPT
        {return __size_alloc_.first();}
}
 
template <class _Tp, class _Alloc = allocator<_Tp> >
class _LIBCPP_TYPE_VIS list
    : private __list_imp<_Tp, _Alloc>
{
typedef __list_imp<_Tp, _Alloc> base;
// ...
    _LIBCPP_INLINE_VISIBILITY
    size_type size() const _NOEXCEPT     {return base::__sz();}
// ...
 
template <class _Tp, class _Alloc>
typename list<_Tp, _Alloc>::iterator
list<_Tp, _Alloc>::insert(const_iterator __p, const value_type& __x)
{
// ...
    ++base::__sz();
// ...
}
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
06.10.2014, 18:26 3
Цитата Сообщение от CyberSolver Посмотреть сообщение
Как это можно реализовать?
Таскать переменную рядом в свойствах (так вроде компиль VS делает).
0
102 / 75 / 17
Регистрация: 23.07.2014
Сообщений: 877
Записей в блоге: 1
06.10.2014, 18:33  [ТС] 4
ForEveR, а как у них реализован splice? Нет никакой проблемы хранить поле с размером и увеличивать при insert и уменьшать при erase. Проблема в этом гадком сплайсе.

MrGluck, если вы про размер, то это не поможет: по двум итераторам размер вы не определите.
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
06.10.2014, 20:03 5
CyberSolver, Вот сорцы листа: https://github.com/llvm-mirror... clude/list
Смотрите как он реализован.
2
2835 / 1644 / 254
Регистрация: 03.12.2007
Сообщений: 4,222
06.10.2014, 20:20 6
Этот баг уже становится фичей...
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561
You've lived with O(n) size for 15 years, you can live with it for a while longer until libstdc++'s ABI changes.
1
102 / 75 / 17
Регистрация: 23.07.2014
Сообщений: 877
Записей в блоге: 1
07.10.2014, 11:18  [ТС] 7
Может я, конечно, и идиот, но, как показало внимательное чтение стандарта, splice'ы не мешают сделать size() константным. Остался вопрос: неужели так сложно переписать код под стандарт? Или, как написано в ссылке Somebody, ребята трясутся над мифической ABI-совместимостью?

Ну и риторический вопрос: а так ли надо верить Мейерсу?
0
923 / 639 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
08.10.2014, 19:57 8
Цитата Сообщение от CyberSolver Посмотреть сообщение
если вы про размер, то это не поможет: по двум итераторам размер вы не определите.
Цитата Сообщение от CyberSolver Посмотреть сообщение
Нет никакой проблемы хранить поле с размером и увеличивать при insert и уменьшать при erase. Проблема в этом гадком сплайсе
Если в сплайс подаются два итератора вставляемого списка, то стандарт, вроде бы, и не требует O(1). Требует только, если список целиком, или один его элемент (первые две формы).
Цитата Сообщение от CyberSolver Посмотреть сообщение
Или, как написано в ссылке Somebody, ребята трясутся над мифической ABI-совместимостью?
Не думаю, что ребят из libstdc++ сильно заботит ABI. Этва проблема актуальна только для закрытых продуктов. ABI в libstdc++, и даже в libc нередко меняется. Скорее, по их мнению, требования стандарта идеологически неверны. Сделать в сплайсе О(1) можно только через введение дополнительное поля, в результате появляется вероятность того, что при ошибке сбое и т.п. объект окажется внутренне противоречивым - хранимый размер не равен расчетному.
Мало кого смущает, что длина Си строк - O(N).
Помню, на каком-то форуме Ява-программист ругал Си за низкую производительность при работе со строками. Ему кто-то предложил задачу, где часто ищется длина строк и попросил написать программу на Яве, а сам написал аналогичную на Си. Соотношени времени оказалось 200:1 в пользу Си.
0
08.10.2014, 19:57
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
08.10.2014, 19:57
Помогаю со студенческими работами здесь

Реализация алгоритмов библиотеки STL
Ребят помогите пожалуйста, как создать програмку, которая бы создавала массив 4 на 3, и заполняла...

реализация Shell Sort в stl
Всем привет! Кто-нибудь знает, есть ли в Stl реализация сортировки Шелла? std::sort()...

реализация stack и dack в STL
я так понимаю, что реализация этих адаптеров основана на vector и list ? Тогда зачем нужен stack,...

Сортировка списка (STL)
Здравствуйте, я столкнулся с проблемой: Мне нужно отсортировать обьекты. Обьекты есть елементами...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru