VPF::Вектор векторов - Форум программистов

Djuffin

Дата 22.10.2006, 18:14 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 18.3.2005

Репутация: 1
Всего: 2

Кстати!
Я не советую использовать vector<vector<>>. Это очень полохая практика.
Лучше vector<vector<>*>.

Void

Дата 22.10.2006, 18:23 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Djuffin @ 22.10.2006, 20:14

)

Я не советую использовать vector<vector<>>. Это очень полохая практика.
Лучше vector<vector<>*>.

ROTFL.
Извиняюсь.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

mr.DUDA

Дата 22.10.2006, 18:33 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

Согласен с Void. В более мягкой форме: LOL.

--------------------

Djuffin

Дата 22.10.2006, 19:02 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 18.3.2005

Репутация: 1
Всего: 2

Цитата(Void @ 22.10.2006, 18:23)

Цитата(Djuffin @ 22.10.2006, 20:14

)

Я не советую использовать vector<vector<>>. Это очень полохая практика.
Лучше vector<vector<>*>.

ROTFL.
Извиняюсь.

В чем я не прав?

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

Это сообщение отредактировал(а) Djuffin - 22.10.2006, 19:18

Void

Дата 22.10.2006, 19:22 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Djuffin @ 22.10.2006, 21:02

)

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

Вполне. А вы? Hint: sizeof(vector<T>).

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Djuffin

Дата 22.10.2006, 19:47 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 18.3.2005

Репутация: 1
Всего: 2

Цитата(Void @ 22.10.2006, 19:22

)

Вполне. А вы? Hint: sizeof(vector<T>).

При чем здесь размер?
Разве копирующий конструктор для каждого элемента (в данном случае каждого вложенного вектора) вызываться не будет?
Разве не будет проходить перераспределение памяти для каждого из воложенных векторов?

Void

Дата 22.10.2006, 19:54 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Djuffin @ 22.10.2006, 21:47

)

При чем здесь размер?

При том, что отличие вектора от указателя на вектор с т.з. оверхеда на выделение и перевыделение памяти минимальное.

Цитата(Djuffin @ 22.10.2006, 21:47

)

Разве не будет проходить перераспределение памяти для каждого из воложенных векторов?

Т.е. вы хотите сказать, что

Код

vector<vector<int> > m(10, vector<int>(10));
m[0].push_back(0); // вот здесь начнёт перевыделяться память для остальных девяти векторов?

С чего вдруг?

Добавлено @ 19:55
mr.DUDA, отдели пожалуйста ветку в cpp.general.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

mr.DUDA

Дата 22.10.2006, 23:44 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

Модератор: вынес тему из C#

--------------------

Djuffin

Дата 23.10.2006, 00:26 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 18.3.2005

Репутация: 1
Всего: 2

Код


m[0].push_back(0); // вот здесь начнёт перевыделяться память для остальных девяти векторов?

Цитата(Void @ 22.10.2006, 19:54

)

С чего вдруг?

Нет. Вот здесь.

Код


m.push_back(vector<int>(10))

Void

Дата 23.10.2006, 00:51 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Djuffin @ 23.10.2006, 02:26

)

Вот здесь.

m.push_back(vector<int>(10))

Аналогично. Каким образом это затрагивает память, выделенную под содержимое остальных векторов?
Хотя, должен признаться, это implementation defined. Но разумная реализация копиктора и swap таких вещей делать не должна.

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Djuffin

Дата 23.10.2006, 01:09 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 55
Регистрация: 18.3.2005

Репутация: 1
Всего: 2

Цитата(Void @ 23.10.2006, 00:51

)

Хотя, должен признаться, это implementation defined. Но разумная реализация копиктора и swap таких вещей делать не должна.

ВОТ! Золотые твои слова smile

Проведем расследование.

Код


#include <vector>
#include <iostream>

using namespace std;

class Entity
{

public:
    static int copy;
    static int construct;
    static int destroy;

    Entity()
    {
        construct++;
    }

    Entity(const Entity &e)
    {
        copy++;
    }

    ~Entity()
    {
        destroy++;
    }
};

int Entity::copy = 0;
int Entity::construct = 0;
int Entity::destroy = 0;

int copy_before_add;
int construct_before_add;
int destroy_before_add;

void test()
{
    vector<vector<Entity> > m(4, vector<Entity>(10));
    vector<Entity> v(1);

    copy_before_add = Entity::copy;
    construct_before_add = Entity::construct;
    destroy_before_add = Entity::destroy;
    
    m.push_back(v);
}

int main(int argc, char* argv[])
{
    test();
    cout << "copy: " << Entity::copy << endl; 
    cout << "construct: " << Entity::construct << endl;
    cout << "destroy: " << Entity::destroy << endl;

    cout << "copy_before_add: " << copy_before_add << endl; 
    cout << "construct_before_add: " << construct_before_add << endl;
    cout << "destroy_before_add: " << destroy_before_add << endl;

    cout << "COPY OVERHEAD: " << Entity::copy - copy_before_add - 1 << endl;
    return 0;
}

Результаты.

Тут есть overhead.

Код


Borland C++ 5.6.4 for Win32 Copyright (c) 1993, 2002 Borland
Turbo Incremental Link 5.64 Copyright (c) 1997-2002 Borland

Код


copy: 92
construct: 2
destroy: 94
copy_before_add: 51
construct_before_add: 2
destroy_before_add: 12
COPY OVERHEAD: 40

А тут нету.

Код


Microsoft® C/C++ Compiler Driver 8.00.50727.42

Код


copy: 53
construct: 2
destroy: 55
copy_before_add: 51
construct_before_add: 2
destroy_before_add: 12
COPY OVERHEAD: 1

ВЫВОДЫ: (которые я для себя сделал)
0. Когда имеешь дело с STL надо хорошо обдумывать каждую строку кода.
1. Я отстал от современных реализаций STL.
2. На ROTFL мое замечание не тянет. smile

Dude03

Дата 23.10.2006, 07:01 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 257
Регистрация: 28.4.2006

Репутация: нет
Всего: 6

Цитата(Void @ 22.10.2006, 19:22)

Цитата(Djuffin @ 22.10.2006, 21:02

)

Вполне. А вы? Hint: sizeof(vector<T>).

лол, если автор поста хотел пошутить, то посмеялся, а если нет - плакать надо smile

Daevaorn

Дата 23.10.2006, 08:09 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(Djuffin @ 22.10.2006, 19:14

)

Лучше vector<vector<>*>.

Нет, ну давайте быть откровенными до конца, что это тоже не выход.

Код


std::vector< boost::shared_ptr< std::vector< T > > >

mr.DUDA

Дата 23.10.2006, 09:13 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

В мелкомягкой реализации вектор содержит массив указателей на объекты, а не сами объекты. Поэтому алгоритм copy всего лишь скопирует N указателей при расширении массива (когда capacity не хватает).

--------------------

Daevaorn

Дата 23.10.2006, 09:25 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(mr.DUDA @ 23.10.2006, 10:13

)

В мелкомягкой реализации вектор содержит массив указателей на объекты, а не сами объекты.

Это в какой?

mr.DUDA

Дата 23.10.2006, 10:18 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

Цитата(Daevaorn @ 23.10.2006, 09:25

)

Это в какой?

Visual Studio N \ VC \ include \ vector

З.Ы. а что, разные бывают что ли ? smile

--------------------

JackYF

Дата 23.10.2006, 15:49 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Насколько я читал, STL по определению реализует семантику значений, а не указателей. Поэтому если я копирую вектор, то мне же нужно скопировать значения из вектора, а не указатели на них!

Это, по-моему, описано в стандарте. В этом случае мелкомягкие .... <ваша фантазия> smile

Но я себе это плохо представляю...

Цитата(mr.DUDA @ 23.10.2006, 09:13

)

mr.DUDA, ты уверен в этом?

--------------------

Пожаловаться на меня как модератора можно здесь.

Void

Дата 23.10.2006, 16:18 (ссылка)

(нет голосов)

Загрузка ...

λcat.lolcat

Профиль
Группа: Участник Клуба
Сообщений: 2206
Регистрация: 16.11.2004
Где: Zürich

Репутация: 40
Всего: 173

Цитата(Djuffin @ 23.10.2006, 03:09

)

0. Когда имеешь дело с STL надо хорошо обдумывать каждую строку кода.
1. Я отстал от современных реализаций STL.
2. На ROTFL мое замечание не тянет.

+++
Погорячился smile

--------------------

“Coming back to where you started is not the same as never leaving.” — Terry Pratchett

Daevaorn

Дата 23.10.2006, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(mr.DUDA @ 23.10.2006, 11:18

)

Visual Studio N \ VC \ include \ vector

З.Ы. а что, разные бывают что ли ?

Представь себе да.

Цитата(JackYF @ 23.10.2006, 16:49

)

Это, по-моему, описано в стандарте. В этом случае мелкомягкие .... <ваша фантазия>

Согласен на все 100% smile

mr.DUDA

Дата 23.10.2006, 19:01 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

Цитата(JackYF @ 23.10.2006, 15:49

)

mr.DUDA, ты уверен в этом?

Насколько я смог понять, да.
Значения лежат в классе-обёртке _Alloc, которая в свою очередь лежит в векторе. Если я не прав, ногами не пинайте, я смотрю что тут сишники собрались хардкорные.

Цитата(Daevaorn @ 23.10.2006, 17:54

)

Представь себе да.

Хм, пример ?

--------------------

JackYF

Дата 23.10.2006, 19:16 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Во-первых, _Alloc зависит от реализации.
У него даже не факт, что имя такое...

Во-вторых, контейнеры STL реализуют семантику значений, и по сему указатели там хранится в принципе не могут. Кроме того, для контейнера std::vector гарантируется, что элементы будут лежать рядом, и к элементам вектора можно обращаться как к обычному массиву.

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

Если нужно хранить указатели на элементы - пожалуйста, храните объекты T*, кто запрещает?..

Примеры реализаций:
STLport
Dinkumware Standart C++ Library
Microsoft - ...
GNU - ...

Это навскидку, а есть еще и другие...

--------------------

Пожаловаться на меня как модератора можно здесь.

Daevaorn

Дата 23.10.2006, 19:21 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(mr.DUDA @ 23.10.2006, 20:01

)

Насколько я смог понять, да.

Не верно понял.

Цитата(mr.DUDA @ 23.10.2006, 20:01

)

Значения лежат в классе-обёртке _Alloc, которая в свою очередь лежит в векторе

И какой ты вывод сделал?

Цитата(mr.DUDA @ 23.10.2006, 20:01

)

Хм, пример ?

У каждой версии студии своя реализия. База общая, это реализация от Dinkware, но от версии к версии отличия очень существенны.

mr.DUDA

Дата 24.10.2006, 09:04 (ссылка)

(нет голосов)

Загрузка ...

3D-маньяк

Профиль
Группа: Экс. модератор
Сообщений: 8244
Регистрация: 27.7.2003
Где: город-герой Минск

Репутация: 25
Всего: 232

Цитата(Daevaorn @ 23.10.2006, 19:21

)

Не верно понял.

Вполне возможно

Цитата(Daevaorn @ 23.10.2006, 19:21

)

И какой ты вывод сделал?

Неверный вывод о том, что обёртка содержит указатель, который и копируется в copy constructor

Цитата(Daevaorn @ 23.10.2006, 19:21

)

+1
маньяк ! smile

--------------------

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »