stl — Доступ к элементам списка списков в переполнении стека
У меня есть список списков, как это:
std::list<std::list<double> > list;
Я заполнил его списками с двойными числами (на самом деле довольно много, поэтому я не использую вектор. Все это копирование занимает много времени.)
Скажем, я хочу получить доступ к элементу, который может быть принят как list[3][3] если бы список был не списком, а вектором или двумерным массивом. Как бы я это сделал?
Я знаю, что доступ к элементам в списке осуществляется с помощью итератора. Я не мог понять, как выбрать двойной.
Решение
double item = *std::next(std::begin(*std::next(std::begin(list), 3)), 3);
Однако использование вектора обычно дает гораздо лучшую производительность; элемент доступа n списка O (n).
Если вы обеспокоены производительностью сращивания внутренней части контейнера, вы можете использовать deque, у которого есть operator[], амортизированная постоянная вставка и удаление с любого конца и линейное время вставки и удаления изнутри.
Для компиляторов C ++ 03 вы можете реализовать begin а также next сам:
template<typename Container>
typename Container::iterator begin(Container &container)
{
return container.begin();
}
template<typename Container>
typename Container::const_iterator begin(const Container &container)
{
return container.begin();
}
template<typename T, int n>
T *begin(T (&array)[n])
{
return &array[0];
}
template<typename Iterator>
Iterator next(Iterator it, typename std::iterator_traits<Iterator>::difference_type n = 1)
{
std::advance(it, n);
return it;
}
Другие решения
Чтобы на самом деле ответить на ваш вопрос, вы должны, вероятно, посмотреть на std::advance.
Чтобы строго ответить на ваш вопрос, Иоахим Пилеборг ответ это путь:
std::list<std::list<double> >::iterator it = list.begin();
std::advance(it, 3);
std::list<double>::iterator it2 = (*it).begin();
std::advance(it2, 3);
double d = *it2;
Теперь из вашего вопроса и дальнейших комментариев не ясно, всегда ли вы добавляете элементы в конец списков или их можно добавлять где угодно. Если вы всегда добавляете в конец, vector<double> будет работать лучше. vector<T> не нужно копировать каждый раз, когда его размер увеличивается; только всякий раз, когда его вместимость увеличивается, что совсем другое дело.
В дополнение к этому, используя reserve()Как уже говорили другие, многое поможет с перераспределением. Вам не нужно резервировать для объединенного размера всех векторов, но только для каждого отдельного вектора. Так:
std::vector<std::vector<double> > v;
v.reserve(512); // If you are inserting 400 vectors, with a little extra just in case
И вы бы также зарезервировать для каждого vector<double> внутри v, Это все.
Учтите, что ваш список списков займет гораздо больше места. Для каждого double во внутреннем списке ему нужно будет выделить как минимум два дополнительных указателя, а также два дополнительных указателя для каждого списка в глобальном наименьшем. Это означает, что общая память, занятая вашим контейнером, будет примерно в три раза больше, чем у вектора. И все это распределение и управление также требует дополнительного времени выполнения.