Резервирование памяти для списка

[RAFA91]

Добрый день !

Подскажите почему не работает этот кусок ?

struct point
{
	int x,y;
	point(int _x, int _y) : x(_x),y(_y) {} 
};
]int _tmain(int argc, _TCHAR* argv[])
{
	
	list<point> mylist;
	 mylist.resize(5);   //??????????
	

	return 0;
}

[Пепел Феникса]

потому что нет конструктора по умолчанию.
http://www.cplusplus.com/reference/list/list/resize/

для связанного списка операция резервирования не имеет смысла ИМХО.
ибо вы забьёте список пустыми значениями(от конструктора по умолчанию), а не резерв некий(да и тогда по-моему лучше вектор уж)

[RAFA91]

просто столкнулся с такой проблемой.

нужно отсортировать список по кускам.

алгоритм сортировки не тянет итераторы списка.

поэтому пришлось создать вектор

vector<point> v(l.begin(),l.end());

и уж с ним мутить кусочную сортировку.

sort(v.begin(),v.end());

потом опять все передавать назад в список

copy(v.begin(),v.end(),l.begin());

v.clear();

[Croessmah]

А зачем что-то резервировать? В copy можно запихнуть back_inserter.

Как уже написал(на другом форуме), можно соорудить адаптер.
Причем можно соорудить адаптер как для итераторов списка, так и для значений, находящихся в списке (например, если копирование в вектор будет неимоверно дорогим).

Ну и можно, например, использовать splice:

#include <iostream>
#include <list>
#include <iterator>

int main()
{
    std::list<int> lst {3, 7, 8, 9, 3, 1, 7, 8, 2, 4, 6, 5, 8} ;
    auto iter_beg = lst.begin() ;
    auto iter_end = lst.end() ;
    std::advance(iter_beg, 5) ;
    std::advance(iter_end, -2) ;
    std::list<int> tmp_lst ;
    tmp_lst.splice(tmp_lst.begin(), lst, iter_beg, iter_end) ;
    tmp_lst.sort() ;
    iter_beg = lst.begin() ;
    std::advance(iter_beg, 5) ;
    lst.splice(iter_beg, tmp_lst) ;
    for(auto e: lst)
        std::cout << e << ' ' ;
}

http://rextester.com/QTHU54921

Вот, вынес всё что нужно в отдельную функцию:

#include <iostream>
#include <list>
#include <iterator>


template<typename T>
void sort_list 
    (
    std::list<T> & lst, //ссылка на список, который будет сортировать
    //и два итератора, которые задают интервал сортировки
    typename std::list<T>::const_iterator begin, 
    typename std::list<T>::const_iterator end 
    )
{
    std::list<T> tmp_lst ;//временный список
    //Определяем расстояние от начала списка до начала интервала сортировки
    typename std::iterator_traits<typename std::list<T>::const_iterator>::difference_type diff = std::distance(lst.cbegin(), begin) ;
    //"Перемещаем(сращиваем)" необходимый кусок списка lst в список tmp_lst 
    //(это делается очень быстро, ибо просто будут меняться несколько указателей, ну и сопутствующие данные, такие как размеры списков).
    tmp_lst.splice(tmp_lst.begin(), lst, begin, end) ;
    //Сортируем временный список
    tmp_lst.sort() ;
    //Берем итератор на начало нашего списка
    typename std::list<T>::const_iterator ins_iterator = lst.begin() ;
    //"Сдвигаем" его до нужной позиции (откуда начинали сортировку)
    std::advance(ins_iterator, diff) ;
    //Ну и сращиваем наш список с временным, причем вставляем кусок туда, где начинали сортировку.
    lst.splice(ins_iterator, tmp_lst) ;
}



int main()
{
    std::list<int> lst {3, 7, 8, 9, 3, 1, 7, 8, 2, 4, 6, 5, 8} ;
    auto iter_beg = lst.begin() ;
    auto iter_end = lst.end() ;
    std::advance(iter_beg, 5) ;
    std::advance(iter_end, -2) ;
    sort_list(lst, iter_beg, iter_end) ;
    for(auto e: lst)
        std::cout << e << ' ' ;
}

[RAFA91]

рад что Вы присутствуете и на этом форуме ))).

адаптер это конечно хорошо только почему бы не воспользоваться другим контейнером ?

[Croessmah]

адаптер это конечно хорошо только почему бы не воспользоваться другим контейнером ?

копирование данных в новый контейнер +
сортировка этого контейнера
(если это вектор, то соответственно будет копирование элементов) +
копирование сортированного куска снова в список +
удаление не сортированных старых данных из списка.
Прикиньте, какой это удар по производительности.
Частично потери производительности на больших контейнерах
можно избежать используя всякие прокси-классы, но всё же это будет медленно.

Все эти вопросы решаются splice'ом, который я показал.
Из одного списка данные просто вырезаются (там же тупо переставить указатели),
далее сортировка временного списка (опять же перестановкой указателей),
затем сращиваем сортированный список со старым (и снова тупо указатели поменять).

А теперь представьте себе разницу в производительности этих двух способов,
если один элемент в списке,
допустим, занимает несколько сотен килобайт и копирование его очень дорого обходится.
splice будет в выигрыше практически в любом случае.
А если контейнер очень большой и
кусок для сортировки большой и данные громоздки, то выигрыш просто огромный.

рад что Вы присутствуете и на этом форуме

Здесь присутствую не только я

[Croessmah]

Для примера немного переделал код.
Теперь у нас не int'ы, а некая структура, которая будет вести лог по созданию элементов:

struct Test
{
    Test(int x) : x_(x){std::cout << "ctor. x = " << x_ << std::endl ; }
    Test(const Test& src) : x_(src.x_){std::cout << "cctor. x = " << x_ << std::endl ; }
    Test(Test&& src) : x_(src.x_){std::cout << "mctor. x = " << x_ << std::endl ; }
    const Test& operator=(const Test& rhv) { x_=rhv.x_ ; std::cout << "oper=. x = " << x_ << std::endl ; return *this; }
    ~Test(){std::cout << "dtor. x = " << x_ << std::endl ; }
    bool operator<(const Test& rhv) {return x_<rhv.x_ ;}
    int x_ ;
} ;

std::ostream& operator<<(std::ostream& stream, const Test& obj)
{
    stream << obj.x_ << ' ' ;
    return stream ;
}

Сортировать будем диапазон с третьего (по счету) и до предпоследнего элемента (включительно).
итак, алгоритм с копированием в вектор:

int main()
{
    std::list<Test> lst {3, 7, 8, 9, 3, 1, 7, 8, 2, 4, 6, 5, 8} ;
    auto iter_beg = lst.begin() ;
    auto iter_end = lst.end() ;
    std::advance(iter_beg, 2) ;
    std::advance(iter_end, -1) ;
    
    std::cout << "start algorithm" << std::endl ;
    
    std::vector<Test> tmp_vec(iter_beg, iter_end) ;
    std::sort(tmp_vec.begin(), tmp_vec.end()) ;
    std::move(tmp_vec.begin(), tmp_vec.end(), iter_beg) ;
    
    std::cout << "end algorithm" << std::endl ; 
    for(const auto & e: lst)
        std::cout << e << ' ' ;
    std::cout << std::endl ;
}

http://rextester.com/ULHK36349
Нас интересует только часть вывода между
start algorithm
и
end algorithm
Видите сколько там всяких копирований происходит? (конечно, это тоже можно оптимизировать, но не настолько, чтобы противопоставить splice'ам).
Вот код со splice'ами:

int main()
{
    std::list<Test> lst {3, 7, 8, 9, 3, 1, 7, 8, 2, 4, 6, 5, 8} ;
    auto iter_beg = lst.begin() ;
    auto iter_end = lst.end() ;
    std::advance(iter_beg, 2) ;
    std::advance(iter_end, -1) ;
    
    std::cout << "start algorithm" << std::endl ; 
    sort_list(lst, iter_beg, iter_end) ;
    std::cout << "end algorithm" << std::endl ; 
    for(const auto & e: lst)
        std::cout << e << ' ' ;
    std::cout << std::endl ;
}

http://rextester.com/OBD79718
И что мы видим? Да просто

start algorithm
end algorithm

ничего!
То есть копирований самих данных нет вообще!
Всё решается перестановкой указателей в самих списках.

[RAFA91]

Croessmah благодарю Вас за этот пример. на досуге попытаюсь его прочесть.

то что касается производительности :

мы же не в каменном веке где частота 1 мега. теперь думаю не стоит жалеть память.

[RAFA91]

функция

advance(it,7);

как я понял это аналог

for (int i=0; i<7 && it!=mylist1.end(); i++) it++;

?

[Croessmah]

как я понял это аналог

http://www.cplusplus.com/reference/iterator/advance/
Зависит от типа итератора.
Для bidirectional итератора - будет использован operator++ для "перемещения на n позиций"
(ну или operator--, в зависимости от того, куда двигаем).
Для random-access итератора - будет использован один operator+
(ну или operator-, в зависимости от того, куда двигаем).

Ваш цикл не верен.
У advance есть только итератор и кол-во позиций, на которые двигаем.
Доступа к самому списку у него нет, так что mylist1.end() не прокатит.

теперь думаю не стоит жалеть память.

Создатели некоторых приложений, видимо, тоже так думают...
Поэтому их тормознутое УГ на помойке софта валяется.