1 Востаннє редагувалося Kizyak (08.02.2017 22:08:00)

Тема: ітератори

В мене виникло запитаня.

#include <vector>
#include <string>

struct SomeStruct
{
    std::vector<std::string>::iterator it;
    std::string data;
};

int main(int argc, char *argv[])
{
    std::vector<std::string> vec;
    SomeStruct str;

    // запишемо якісь елементи
    vec.push_back("lalalalalala");
    vec.push_back("hahahahahaha");
    vec.push_back("bambambabambam");

    str.data = "kokokokoko";
    str.it = vec.begin();    // присвоїмо ітератор

    // ще пододаємо елементів
    vec.push_back("go go go");
    vec.push_back("mu mu mu mu mu");

    // якщо вектор не виділив достатнь пам'яті для цих п'яти
    // елементів, то він створить більший масив і перепише туди вже
    // існуючі елементи
    str.data = *str.it;
    // запитання: чи буде вказувакти str.it на тей самий перший елемент
    // після перезапису масиву
    
    return 0;
}

2

Re: ітератори

Одразу зауважу, що ваш код жодним чином не стосується вашого запитання.
А відповідь - це UB. На практиці - не буде.
http://ideone.com/W0Wssc

Подякували: varkon, Kizyak2

3

Re: ітератори

Хочу зауважити на приклад пана koala, що всі ітератори і посилання анулюються лише якщо новий size() більше ніж capacity(). Тому не факт, що після цього

    for(int i = 100;i<200;++i){
      v.push_back(i+1);
    }

it вказуватиме на звільнену область пам'яті ;)

    cout << *it << endl;//тут має бути 1, бо it вказує у звільнену область пам'яті, 
                        //де ще лишаються старі дані, але це не гарантовано
Прихований текст

Також, прохання вставляти код і в відповідь також, бо не дуже хочеться лазити по додаткових сайтах (щоб не гаяти час)

Подякували: Kizyak, koala2

4

Re: ітератори

Дякую за уточнення, виправлений варіант: http://ideone.com/dyq7sm

Подякували: Yola1

5 Востаннє редагувалося -=ЮрА=- (09.02.2017 23:55:26)

Re: ітератори

Kizyak - відповід зажди ні, бо у прикладі на момент присвоювання вектор тримає 3 строки, потім буде гарантований ріалок пам'яті при кожному push_back-у. Ніяких якщо там не буде.

cout << *it << endl;//тут має бути 1, бо it вказує у звільнену область пам'яті,
                        //де ще лишаються старі дані, але це не гарантовано

- який один? Навіть якщо менеджер пам'яті не затер блок, у вектор пхаємо інтеджери зі 100.

Подякували: Kizyak1

6

Re: ітератори

Подивіться внизу stdout.
І ніяких "гарантованих realloc-ів".

7 Востаннє редагувалося -=ЮрА=- (10.02.2017 09:03:44)

Re: ітератори

Подивіться внизу stdout.
І ніяких "гарантованих realloc-ів".

- а що там дивитись, граєтесь в УБ
http://codepad.org/mFLVRxnS

8 Востаннє редагувалося -=ЮрА=- (10.02.2017 09:14:11)

Re: ітератори

Гадаю буде умісно зазначти : Те що там капасіті збільшується, то це працює схема

if( current_item + 1 == size )
    resize(size *= 2);
internal_arr[current_item] = val;

І що з того? Ви знаєте початковий чанк сайз, щоб вирахувати приріст меморі?Ви впевнені у схемі *2? А може буде схема size += 1024 і т.д. Звісно нічого не знаєте, тому це все УБ. size *= 2, чи size += chunk, роблять, щоб зменшити кількусть ріалоків, бо ріалок дуже затратна річ. То що з того? Ви не маєте ніяких відомостей про внутрішню реалізацію ріалока, тому не треба гадати та розраховувати "на сприятливі фази луни". Єдина річ яка гарантовано позбавляє гадань - то це reserve

9

Re: ітератори

"Чанк сайз", "меморі", "ріалок". Ви певні, що це українська мова?
І так, звісно, я в курсі, що там UB, я про це і писав. Що ж до схеми "*2", то я спеціально переробив код, щоб на неї не розраховувати.

10 Востаннє редагувалося -=ЮрА=- (11.02.2017 00:09:52)

Re: ітератори

"Чанк сайз", "меморі", "ріалок". Ви певні, що це українська мова?

- це зветься технічний жаргон, про його заборону тут ніде не йшлось. Далі окрім УБ я нічого не бачив, поясніть що конкретно ви показували у прикладах?

І ніяких "гарантованих realloc-ів".

- ви затиснуті у конкретній реалиізації стл-ського вектора, а саме схеми size *= 2. Ще раз повторюю, вектор має тримати рівно стільки елемнтів, скільки ми в нього додали, всі ці капасіті - звуться меморі оверхед і являють собою лише оптимізацію. У "звичайному" вакуумі вам невідомо який алокатор використовує вектор.

11

Re: ітератори

-=ЮрА=- написав:

- ви затиснуті у конкретній реалиізації стл-ського вектора, а саме схеми size *= 2. Ще раз повторюю, вектор має тримати рівно стільки елемнтів, скільки ми в нього додали, всі ці капасіті - звуться меморі оверхед і являють собою лише оптимізацію. У "звичайному" вакуумі вам невідомо який алокатор використовує вектор.

У нас не вакуум, у нас є Стандарт, і Стандарт каже

Стандарт написав:

23.3.6 Клас шаблон vector
23.3.6.1 Клас шаблон вектор: огляд
vector - це послідовний контейнер, що має сталий (амортизований) час вставляння і видалення елементів в/з хвоста; вставляння і видалення з середини займає лінійний час. Керування пам'яттю виконується автоматично, хоча можна надати підказку для покращення ефективності.

Пояснення перекладача:
Лінійний (амортизований) час неможливо надати якщо перевиділяти пам'ять на кожному вставлянні. Поясню на прикладі як це рахується якщо розмір щоразу збільшується на 2 (чи на 1.1, чи на 1.5, чи на 157.638).

Припустимо, що пам'ять виділялась так, спочатку на 2 елементи, потім на 4, 8, 16, 32, 64, 128, 256, 512, 1024. Отже у нас є пам'ять на 1024, а скільки ж ми виділяли - 4 + 8 + 16 + 32 + 64 + 128 + 256 +512 + 1024 (нічого не нагадує, так це геометричний ряд) = 1024 * (1 + 1/2 + 1/4 + ... + 1/256) < 2048. І це завжди буде так, бо 1 + сума_по_n(1/n) = 2. Отже, маємо сталий час - O(1).

При виділенні кожного разу додатково 1 елемента чи 10, чи 100 - не можливо досягти сталого часу. Виділення мусить залежати від n.
кінець пояснення від перекладача

12 Востаннє редагувалося -=ЮрА=- (11.02.2017 22:06:58)

Re: ітератори

Yola, своє пояснення від перекладача(вірніше свої думки, яки віділені немов би прописані у стандарті) залиши при собі, цього в стандарті немає.
Продовжимо - виділення пам'яті взагалі то залежить від меморі менеджера та заліза. (колись пам'ять вимірювалась у Кб, а зараз у Тб).
Далі йдемо - переклад стандарту наведено застарілий(дивісь скріншоти). Який там рік 2003?Чи який?З роками сторінок побільшало, як і пунктів. Також у майбутньому рекомендую хочаб листати орігінал, а не переклади, буде хоча б професійно.

Припустимо, що пам'ять виділялась так, спочатку на 2 елементи,

- відкрий контейнер, та подивись яка там схема, чи не знаєш де шукати?

(нічого не нагадує, так це геометричний ряд) = 1024 * (1 + 1/2 + 1/4 + ... + 1/256) < 2048

- ні не нагадує, бо це прогресія

4, 8, 16, 32, 64, 128, 256, 512, 1024

(геометрічна), яка має безкінечну суму(а не сталу), проте насмішив, дякую;)

Post's attachments

1.png 53.95 kb, 173 downloads since 2017-02-11 

13

Re: ітератори

А ось тут прописані вектори

Post's attachments

2.png 75.57 kb, 176 downloads since 2017-02-11 

14

Re: ітератори

Yola написав:

Припустимо, що пам'ять виділялась так, спочатку на 2 елементи, потім на 4, 8, 16, 32, 64, 128, 256, 512, 1024. Отже у нас є пам'ять на 1024, а скільки ж ми виділяли - 4 + 8 + 16 + 32 + 64 + 128 + 256 +512 + 1024 (нічого не нагадує, так це геометричний ряд) = 1024 * (1 + 1/2 + 1/4 + ... + 1/256) < 2048. І це завжди буде так, бо 1 + сума_по_n(1/n) = 2. Отже, маємо сталий час - O(1).

Напились вчора чи що?

Подякували: koala1

15

Re: ітератори

@Юра, Припустимо, що я переклав із застарілого стандарту. Але ж ваш скріншот говорить In addition, supports (amortized) constant time insert and erase operations at the end; -- підкажіть, будь ласка, як це можна втілити із  підходом реалокації на кожному вставлянні? чи на кожному десятому, чи на кожному сотому?

-=ЮрА=- написав:

(нічого не нагадує, так це геометричний ряд) = 1024 * (1 + 1/2 + 1/4 + ... + 1/256) < 2048

- ні не нагадує, бо це прогресія

4, 8, 16, 32, 64, 128, 256, 512, 1024

(геометрічна), яка має безкінечну суму(а не сталу), проте насмішив, дякую;)

Винесіть 1024 за дужки і скажіть чому дорівнює сума в дужках. І я ніде не писав, що цей геометричний ряд має сталу суму. Що я писав, так це те, що в перерахунку на кожен елемент, сума стала, тобто суму треба поділити на кількість елементів, щоб отримати сталу - це те, чого вимагає стандарт.

0x9111A написав:

Напились вчора чи що?

Вимагаю поваги до суду учасників форуму. Вкажіть, що не так, буду вдячний.

16 Востаннє редагувалося -=ЮрА=- (12.02.2017 11:14:06)

Re: ітератори

Але ж ваш скріншот говорить In addition, supports (amortized) constant time insert and erase operations at the end; -- підкажіть, будь ласка, як це можна втілити із  підходом реалокації на кожному вставлянні? чи на кожному десятому, чи на кожному сотому?

- ми можему взагалі отримати константний час, який не залежить від n - просто говоримо мендежру пам'яті двигати кінцевий маркер блоку. Через те, що вектор являє собою кросс платформений контейнер, він не може використовувати специфічні функції меморі менджменту, ось тому люд і вирішив хоч якось зоптимізувати таку затратну річ як пушбек, в результаті чого з'явилася схема *2. Далі : на кожному

4 + 8 + 16 + 32 + 64 + 128 + 256 +512 + 1024

ріалоку йде замовлення нової меморі, копіюювання в неї елементів, а потім видаленння старої.
Ще раз прикріпляю скруншот, його бажано прочитати дуже дуже ретельно, без гугл транслейт, а з розумінням.

Post's attachments

necessary.png 82 kb, 192 downloads since 2017-02-12 

17

Re: ітератори

Далі по математиці

Винесіть 1024 за дужки і скажіть чому дорівнює сума в дужках. І я ніде не писав, що цей геометричний ряд має сталу суму.

- тобто ти з одного боку кажеш, що прогресія(тобто конкретний числовий ряд) не має сталої суми, а потім розглядаєш часткову суму ряду

Що я писав, так це те, що в перерахунку на кожен елемент, сума стала, тобто суму треба поділити на кількість елементів

- я не буду супроводжувати це в'їдливим коментаром, можливо перечитаєш та зрозумієш сам.

18 Востаннє редагувалося -=ЮрА=- (12.02.2017 11:19:50)

Re: ітератори

Yola, ще хотілось би почути від тебе як ти розумієш те що написано в стандарті

In addition, supports (amortized) constant time insert and erase operations at the end

- переклади на рідну будь ласка. Можливо ти англійську погано знаєш, тому погано розумієш.

Ще хотів би, щоб перечитав тему, бо я тут змушений відволікатися на якісь твої ряди, якісь суми, тема стосувалася простого - чи буде ітератор вказувати на валідну ячійку пам'яті після додавання елементів у вектор : в загальному випадку відповідь ні ніколи.  Ти з чимось не погоджуєся?Що взагалі хочеш доказати?Чи це той випадок коли йде доказ для доказу, а чого не зрозуміло)

19

Re: ітератори

Все таки я хотів би повернутися до цього :

Що ж до схеми "*2", то я спеціально переробив код, щоб на неї не розраховувати.

можно пальцем показати де саме?Викликали конструктор вектору?І що цим конкретно хотіли сказати?

20

Re: ітератори

-=ЮрА=- написав:

Все таки я хотів би повернутися до цього :

Що ж до схеми "*2", то я спеціально переробив код, щоб на неї не розраховувати.

можно пальцем показати де саме?Викликали конструктор вектору?І що цим конкретно хотіли сказати?

    auto old_capacity = v.capacity();
    while( old_capacity == v.capacity() ) {
      v.push_back(i++);
    }

Де тут очікується, що помножиться саме на 2?