Контейнерные классы

[Igors]

Допустим мне нужна телефонная книга. Я задаю имя и получаю список телефонов. Что лучше выбрать QMultiMap или QMultiHash?

А Вы собираетесь ее пополнять/редактировать? Если нет, то оба выбора - не лучшие

[Johnik]

Так вы почитали в чем разница между Map и Hash?
Если нужно только искать, то при таких объемах (небольших) разницы вы не увидите. А вот если вы захотите пробегаться по всей коллекции, то разницу вы увидите сразу. Пробуйте.

Поддерживаю. И добавлю, на хабре пробегала статья: QMap vs. QHash: небольшой бенчмарк

[8Observer8]

К Map и Hash я позже вернусь. Для меня это на данный момент сложновато.

Я сейчас с vector'ом разбираюсь. В следующей программке метод size() будет вызнан один раз или каждый раз пока работает цикл?

Код:

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char *argv[]) {

    vector<int> myvector {1, 2, 3, 4, 5, 6, 7, 8};

    cout << "myvector: ";
    for (size_t i = 0; i < myvector.size(); ++i) {
        cout << " " << myvector[i];
    }
    cout << endl;

    return 0;
}

[OKTA]

Look at this 
http://codepad.org/BBfGJchj

[8Observer8]

Look at this 
http://codepad.org/BBfGJchj

Я думал, тут хитрость есть, что для контейнеров один раз будет вызываться, так как если контейнер большой, то вызов size() будет очень дорогим.

На форумах часто попадаются примеры, где size вызывается в цикле

Значит размер буду вычислять до цикла  Спасибо!

Код:

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char *argv[]) {

    vector<int> myvector {1, 2, 3, 4, 5, 6, 7, 8};

    size_t size = myvector.size();
    
    cout << "myvector: ";
    for (size_t i = 0; i < size; ++i) {
        cout << " " << myvector[i];
    }
    cout << endl;

    return 0;
}

[Igors]

Я думал, тут хитрость есть, что для контейнеров один раз будет вызываться, так как если контейнер большой, то вызов size() будет очень дорогим.

Почти для всех контейнеров вызов size() очень дешев, практически бесплатный, поэтому обычно локальную переменную не заводят. Из исключений могу вспомнить только std::list

А вот типичная ловушка с вектором

Код

C++ (Qt)
std::vector <int> vec;
// QVector <int> vec;
// как-то заполнили вектор
...
size_t count = vec.size();
for (size_t i = 0; i < count; ++i) {
 int & val = vec[i];
 if (val < 0) vec.push_back(val);
 val = 0;
} 

[8Observer8]

Почти для всех контейнеров вызов size() очень дешев, практически бесплатный, поэтому обычно локальную переменную не заводят. Из исключений могу вспомнить только std::list

Спасибо! Я думал у size линейная сложность Ан нет - константная: http://www.cplusplus.com/reference/vector/vector/size/

[8Observer8]

Вот в в этой книге http://www.wrox.com/WileyCDA/WroxTitle/Professional-C-2nd-Edition.productCd-0470932449.html постоянно делается упор на C++11, поэтому лучше по-современному, вот так:

Код:

#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char *argv[]) {

    vector<int> myvector {1, 2, 3, 4, 5, 6, 7, 8};
    
    cout << "myvector: ";
    for (auto iter = myvector.cbegin();
            iter != myvector.cend(); ++iter) {
        cout << " " << *iter;
    }
    cout << endl;

    cout << "myvector: ";
    for (auto& i : myvector) {
        cout << " " << i;
    }
    cout << endl;

    return 0;
}

[Igors]

..поэтому лучше по-современному, вот так:

Ах как резво Вы хватаете "вершки" Ловушку из предыдущего поста разберите, толку больше будет

[OKTA]

Спасибо! Я думал у size линейная сложность Ан нет - константная: http://www.cplusplus.com/reference/vector/vector/size/

В общем случае, константная сложность не дает гарантии, что операция будет работать быстрее по сравнению с операцией с линейной сложностью, на сколько я знаю 

[Fat-Zer]

Немного запоздало, про то с чего тема начиналась...

Текст из книги Макса Шлее "Профессиональное программирование на С++. Qt 4.8":

При  создании объекта  класса  QMap<K,T>
  нужно передать  его  размер в конструктор. Этот
размер не является, как это принято в других контейнерных классах, размером, ограничи-
вающим максимальное  количество элементов,  а представляет  собой количество позиций.
Количество позиций должно быть больше количества элементов, ожидаемых для хранения,
иначе поиск элементов в словаре будет проводиться недостаточно эффективно. Желатель-
но, чтобы это значение относилось к разряду простых чисел, т. к. в этом случае размещение
элементов будет более  удобным  (см. приложение 2)

Мне тут каждое предложение непонятно.

В Qt3 было несколько контейнеров Q{Int,Ascii,чего-то-там-ещё,}Dict, так это как раз про них. Передаваемый размер там задавал размер хеш-таблицы...
Дальше взял посмотреть книгу тов. Шлее про Qt-3.2... и что бы вы думали? В разделе «Словари» тот же текст слово в слово =)
т.е. мало того, что оно безбожно устарело, так ещё и с ошибкой...

это ещё 5 копеек к тому что стоит больше верить докам и меньше книгам... особенно отечественным...

если что , то на все остальные вопросы «зачем оно нужно» итп — поймёшь, когда прочитаешь, что такое хеш...

[8Observer8]

Дальше взял посмотреть книгу тов. Шлее про Qt-3.2... и что бы вы думали? В разделе «Словари» тот же текст слово в слово =)
т.е. мало того, что оно безбожно устарело, так ещё и с ошибкой...

Fat-Zer, Спасибо! Как я понял, автор скопировал информацию из старой книги и не поправил. Бывает!

это ещё 5 копеек к тому что стоит больше верить докам и меньше книгам... особенно отечественным...

Да, согласен. Доверяй, но проверяй!

если что , то на все остальные вопросы «зачем оно нужно» итп — поймёшь, когда прочитаешь, что такое хеш...

Да, теория и практика у меня слабы. Стараюсь! Практика + Теория = Гармония

В общем случае, константная сложность не дает гарантии, что операция будет работать быстрее по сравнению с операцией с линейной сложностью, на сколько я знаю  

Утверждение:
Вставка элемента в середину vector'а (линейная сложность) будет работать гарантированно быстрее, чем доступ по индексу в том же векторе (константная сложность).

[8Observer8]

Я думал, тут хитрость есть, что для контейнеров один раз будет вызываться, так как если контейнер большой, то вызов size() будет очень дорогим.

Почти для всех контейнеров вызов size() очень дешев, практически бесплатный, поэтому обычно локальную переменную не заводят. Из исключений могу вспомнить только std::list

А вот типичная ловушка с вектором

Код

C++ (Qt)
std::vector <int> vec;
// QVector <int> vec;
// как-то заполнили вектор
...
size_t count = vec.size();
for (size_t i = 0; i < count; ++i) {
 int & val = vec[i];
 if (val < 0) vec.push_back(val);
 val = 0;
} 

Отличный пример. Где-то подвох, но я его не понял

Функция:

Код:

void func(vector<int> &vec) {
    size_t count = vec.size();
    for (size_t i = 0; i < count; ++i) {
        int & val = vec[i];
        if (val < 0) vec.push_back(val);
        val = 0;
    }
    cout << "!!!!" << " " << vec.size() << endl;
}

Тест нормально проходит:

Код:

void newtestclass::testFunc_002() {
    vector<int> vec;

    // Заполняем массив
    vec.push_back(-1);
    vec.push_back(3);
    vec.push_back(6);
    vec.push_back(7);
    vec.push_back(1);

    // Обрабатываем элементы массива
    func(vec);

    // Проверяем размер массива
    int expectedSize = 6;
    int actualSize = vec.size();
    CPPUNIT_ASSERT_EQUAL(expectedSize, actualSize);
}

[8Observer8]

Извините, неправильно сообщение написал. Исправил.

[OKTA]

Вставка элемента в середину vector'а (линейная сложность) будет работать гарантированно быстрее, чем доступ по индексу в том же векторе (константная сложность). Разве нет?

А почему? Чем больше размер вектора, тем линейная сложность будет больше, разве нет?