컨테이너 클래스

소개

Qt 라이브러리는 범용 템플릿 기반 컨테이너 클래스 세트를 제공합니다. 이러한 클래스는 지정된 유형의 항목을 저장하는 데 사용할 수 있습니다. 예를 들어, 크기 조정이 가능한 QString배열이 필요한 경우 QList<QString>을 사용합니다.

이러한 컨테이너 클래스는 STL 컨테이너보다 더 가볍고 안전하며 사용하기 쉽도록 설계되었습니다. STL에 익숙하지 않거나 "Qt 방식"을 선호하는 경우 STL 클래스 대신 이러한 클래스를 사용할 수 있습니다.

컨테이너 클래스는 암시적으로 공유되고, 재진입이 가능하며, 속도, 낮은 메모리 소비, 최소한의 인라인 코드 확장에 최적화되어 실행 파일의 크기가 작아집니다. 또한 컨테이너에 액세스하는 데 사용되는 모든 스레드에서 읽기 전용 컨테이너로 사용되는 상황에서 스레드 안전합니다.

컨테이너는 트래버스를 위한 이터레이터를 제공합니다. STL 스타일 이터레이터는 가장 효율적인 이터레이터로, Qt 및 STL의 generic algorithms 와 함께 사용할 수 있습니다. 이전 버전과의 호환성을 위해 Java 스타일 이터레이터가 제공됩니다.

QList<int> list = {1, 2, 3, 4, 4, 5};
QSet<int> set(list.cbegin(), list.cend());
/*
    Will generate a QSet containing 1, 2, 3, 4, 5.
*/

컨테이너 클래스

Qt는 다음과 같은 순차적 컨테이너를 제공합니다: QList, QStack, 그리고 QQueue 입니다. 대부분의 응용 프로그램에서는 QList 을 사용하는 것이 가장 좋습니다. 매우 빠른 추가 기능을 제공합니다. 링크된 리스트가 정말로 필요하다면, std::list를 사용하십시오. QStack 와 QQueue 는 LIFO와 FIFO 시맨틱을 제공하는 편의 클래스입니다.

Qt는 이러한 연관 컨테이너도 제공합니다: QMap, QMultiMap, QHash, QMultiHash, 그리고 QSet 입니다. "Multi" 컨테이너는 단일 키와 연관된 여러 값을 편리하게 지원합니다. "해시" 컨테이너는 정렬된 집합에서 이진 검색 대신 해시 함수를 사용하여 더 빠른 조회를 제공합니다.

특수한 경우로 QCache 및 QContiguousCache 클래스는 제한된 캐시 스토리지에서 객체의 효율적인 해시 조회를 제공합니다.

컨테이너는 중첩될 수 있습니다. 예를 들어, 키 유형이 QString 이고 값 유형이 QList<int>인 QMap<QString, QList<int>>를 사용할 수 있습니다.

컨테이너는 컨테이너와 같은 이름의 개별 헤더 파일에 정의됩니다(예: <QList>). 편의를 위해 컨테이너는 <QtContainerFwd> 에서 포워드 선언됩니다.

다양한 컨테이너에 저장된 값은 할당 가능한 모든 데이터 유형이 될 수 있습니다. 자격을 갖추려면 유형이 복사 생성자와 할당 연산자를 제공해야 합니다. 일부 연산에는 기본 생성자도 필요합니다. 이는 int, double 과 같은 기본 유형, 포인터 유형, QString, QDate, QTime 과 같은 Qt 데이터 유형을 포함하여 컨테이너에 저장할 가능성이 있는 대부분의 데이터 유형을 포함하지만 QObject 또는 QObject 서브 클래스 (QWidget, QDialog, QTimer 등)는 포함하지 않습니다. QList <QWidget>를 인스턴스화하려고 하면 컴파일러는 QWidget 의 복사 생성자 및 할당 연산자가 비활성화되었다고 불평합니다. 이러한 종류의 객체를 컨테이너에 저장하려면 예를 들어 QList<QWidget *>와 같이 포인터로 저장하세요.

다음은 할당 가능한 데이터 타입의 요구 사항을 충족하는 사용자 정의 데이터 타입의 예시입니다:

class Employee
{
public:
    Employee() {}
    Employee(const Employee &other);

    Employee &operator=(const Employee &other);

private:
    QString myName;
    QDate myDateOfBirth;
};

복사 생성자나 할당 연산자를 제공하지 않는 경우 C++는 멤버별 복사를 수행하는 기본 구현을 제공합니다. 위의 예시에서는 그것으로 충분했을 것입니다. 또한 생성자를 제공하지 않는 경우 C++는 기본 생성자를 사용하여 멤버를 초기화하는 기본 생성자를 제공합니다. 명시적인 생성자나 할당 연산자를 제공하지는 않지만 다음과 같은 데이터 유형을 컨테이너에 저장할 수 있습니다:

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

일부 컨테이너에는 저장할 수 있는 데이터 유형에 대한 추가 요구 사항이 있습니다. 예를 들어 QMap<키, T>의 키 유형은 operator<() 을 제공해야 합니다. 이러한 특수 요구 사항은 클래스의 상세 설명에 문서화되어 있습니다. 특정 함수에는 특별한 요구 사항이 있는 경우도 있으며, 이러한 요구 사항은 함수별로 설명되어 있습니다. 요구 사항이 충족되지 않으면 컴파일러는 항상 오류를 발생시킵니다.

Qt의 컨테이너는 QDataStream 를 사용하여 쉽게 읽고 쓸 수 있도록 연산자<<() 및 연산자>>()를 제공합니다. 즉, 컨테이너에 저장된 데이터 유형도 연산자<<() 및 연산자>>()를 지원해야 합니다. 이러한 지원을 제공하는 것은 간단합니다. 위의 Movie 구조체에서 이를 제공하는 방법은 다음과 같습니다:

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

특정 컨테이너 클래스 함수의 문서에서는 기본 구성 값을 참조합니다. 예를 들어 QList 는 기본 구성 값으로 항목을 자동으로 초기화하며 QMap::value()는 지정된 키가 맵에 없는 경우 기본 구성 값을 반환합니다. 대부분의 값 유형에서 이는 단순히 기본 생성자(예: QString 의 경우 빈 문자열)를 사용하여 값이 생성됨을 의미합니다. 그러나 int 및 double 과 같은 프리미티브 타입과 포인터 타입의 경우 C++ 언어는 초기화를 지정하지 않으며, 이러한 경우 Qt의 컨테이너는 자동으로 값을 0으로 초기화합니다.

컨테이너에 대한 이터레이션

범위 기반

컨테이너에는 범위 기반 for 을 사용하는 것이 좋습니다:

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : list) {
   ...
}

컨텍스트가 아닌 컨텍스트에서 Qt 컨테이너를 사용할 때, 암시적 공유는 원치 않는 컨테이너 분리를 수행할 수 있다는 점에 유의하세요. 이를 방지하려면 std::as_const() 을 사용하십시오:

QList<QString> list = {"A", "B", "C", "D"};
for (const auto &item : std::as_const(list)) {
    ...
}

연관 컨테이너의 경우 값을 반복합니다.

인덱스 기반

메모리에 연속적으로 항목을 저장하는 순차적 컨테이너(예: QList)의 경우 인덱스 기반 반복을 사용할 수 있습니다:

QList<QString> list = {"A", "B", "C", "D"};
for (qsizetype i = 0; i < list.size(); ++i) {
    const auto &item = list.at(i);
    ...
}

이터레이터 클래스

이터레이터는 컨테이너의 항목에 접근하는 통일된 수단을 제공합니다. Qt의 컨테이너 클래스는 두 가지 유형의 이터레이터를 제공합니다: STL 스타일 이터레이터와 Java 스타일 이터레이터입니다. 두 유형의 이터레이터는 컨테이너의 데이터가 수정되거나 생성되지 않은 멤버 함수에 대한 호출로 인해 암시적으로 공유된 복사본에서 분리될 때 무효화됩니다.

STL 스타일 이터레이터

STL 스타일 이터레이터는 Qt 2.0 릴리스부터 사용 가능했습니다. 이터레이터는 Qt 및 STL의 generic algorithms 와 호환되며 속도에 최적화되어 있습니다.

각 컨테이너 클래스에는 읽기 전용 액세스를 제공하는 이터레이터와 읽기-쓰기 액세스를 제공하는 이터레이터의 두 가지 STL 스타일 이터레이터 유형이 있습니다. 읽기 전용 이터레이터는 읽기-쓰기 이터레이터보다 빠르므로 가능하면 읽기 전용 이터레이터를 사용해야 합니다.

STL 이터레이터의 API는 배열의 포인터를 모델로 합니다. 예를 들어 ++ 연산자는 이터레이터를 다음 항목으로 전진시키고 * 연산자는 이터레이터가 가리키는 항목을 반환합니다. 실제로 인접한 메모리 위치에 항목을 저장하는 QList 및 QStack 의 경우 iterator 유형은 T * 에 대한 typedef이고 const_iterator 유형은 const T * 에 대한 typedef일 뿐입니다.

이 논의에서는 QList 와 QMap 에 집중하겠습니다. QSet 의 이터레이터 타입은 QList 의 이터레이터와 완전히 동일한 인터페이스를 가지며, 마찬가지로 QHash 의 이터레이터 타입은 QMap 의 이터레이터와 동일한 인터페이스를 가집니다.

다음은 QList<QString>의 모든 요소를 순서대로 반복하고 소문자로 변환하는 일반적인 루프입니다:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.begin(), end = list.end(); i != end; ++i)
    *i = (*i).toLower();

STL 스타일 이터레이터는 항목을 직접 가리킵니다. 컨테이너의 begin() 함수는 컨테이너의 첫 번째 항목을 가리키는 이터레이터를 반환합니다. 컨테이너의 end() 함수는 컨테이너의 마지막 항목에서 한 위치 지나 가상의 항목에 대한 반복자를 반환합니다. end()는 잘못된 위치를 표시하므로 절대로 역참조해서는 안 됩니다. 일반적으로 루프의 중단 조건에서 사용됩니다. 목록이 비어 있으면 begin()는 end()와 같으므로 루프를 실행하지 않습니다.

아래 다이어그램은 4개의 항목이 포함된 목록에서 유효한 반복자 위치를 빨간색 화살표로 표시한 것입니다:

STL 스타일 이터레이터로 역방향 반복은 역방향 이터레이터로 수행됩니다:

QList<QString> list = {"A", "B", "C", "D"};

for (auto i = list.rbegin(), rend = list.rend(); i != rend; ++i)
    *i = i->toLower();

지금까지 코드 스니펫에서는 단항 * 연산자를 사용하여 특정 반복자 위치에 저장된 항목( QString)을 검색한 다음 QString::toLower()를 호출했습니다.

읽기 전용 액세스의 경우 const_iterator, cbegin() 및 cend()를 사용할 수 있습니다. 예를 들어

for(auto i = list.cbegin(), end = list.cend(); i != end; ++i)    qDebug() << *i;

다음 표에는 STL 스타일 이터레이터의 API가 요약되어 있습니다:

++ 및 -- 연산자는 접두사(++i, --i) 및 접미사(i++, i--) 연산자로 모두 사용할 수 있습니다. 접두사 버전은 반복자를 수정하고 수정된 반복자에 대한 참조를 반환하고, 접두사 버전은 반복자를 수정하기 전에 반복자의 복사본을 가져와서 그 복사본을 반환합니다. 반환 값이 무시되는 표현식에서는 접두사 연산자(++i, --i)를 사용하는 것이 약간 더 빠르므로 사용하는 것이 좋습니다.

컨스트가 아닌 반복자 유형의 경우 단항 * 연산자의 반환값을 할당 연산자의 왼쪽에 사용할 수 있습니다.

QMap 및 QHash 의 경우 * 연산자는 항목의 값 구성 요소를 반환합니다. 키를 검색하려면 이터레이터에서 key()를 호출합니다. 대칭의 경우, 반복자 유형은 값을 검색하는 value() 함수도 제공합니다. 예를 들어 다음은 QMap 의 모든 항목을 콘솔에 출력하는 방법입니다:

QMap<int,  int> map;...for(auto i = map.cbegin(), end = map.cend(); i != end; ++i)    qDebug() << i.key() << ':' << i.value();

암시적 공유 덕분에 함수가 값당 컨테이너를 반환하는 비용이 매우 저렴합니다. Qt API에는 값당 QList 또는 QStringList 을 반환하는 수십 개의 함수가 포함되어 있습니다(예: QSplitter::sizes()). STL 이터레이터를 사용하여 이러한 함수를 반복하려면 항상 컨테이너의 복사본을 가져와서 복사본을 반복해야 합니다. 예를 들어

// RIGHT
const QList<int> sizes = splitter->sizes();
for (auto i = sizes.begin(), end = sizes.end(); i != end; ++i)
    ...

// WRONG
for (auto i = splitter->sizes().begin();
        i != splitter->sizes().end(); ++i)
    ...

컨테이너에 대한 const 또는 non-const 참조를 반환하는 함수에서는 이 문제가 발생하지 않습니다.

암시적 공유 이터레이터 문제

암시적 공유는 STL 스타일 이터레이터에 또 다른 결과를 가져옵니다. 이터레이터가 해당 컨테이너에서 활성화되어 있는 동안에는 컨테이너를 복사하지 않아야 합니다. 반복자는 내부 구조를 가리키므로 컨테이너를 복사하는 경우 반복자를 매우 주의해야 합니다. 예

QList<int> a, b;
a.resize(100000); // make a big list filled with 0.

QList<int>::iterator i = a.begin();
// WRONG way of using the iterator i:
b = a;
/*
    Now we should be careful with iterator i since it will point to shared data
    If we do *i = 4 then we would change the shared instance (both vectors)
    The behavior differs from STL containers. Avoid doing such things in Qt.
*/

a[0] = 5;
/*
    Container a is now detached from the shared data,
    and even though i was an iterator from the container a, it now works as an iterator in b.
    Here the situation is that (*i) == 0.
*/

b.clear(); // Now the iterator i is completely invalid.

int j = *i; // Undefined behavior!
/*
    The data from b (which i pointed to) is gone.
    This would be well-defined with STL containers (and (*i) == 5),
    but with QList this is likely to crash.
*/

위의 예는 QList 의 문제만 보여주지만, 이 문제는 암시적으로 공유되는 모든 Qt XML 컨테이너에 존재합니다.

자바 스타일 이터레이터

Java 스타일 이터레이터는 Java의 이터레이터 클래스를 모델로 합니다. 새 코드는 STL 스타일 이터레이터를 선호해야 합니다.

std 컨테이너와 비교한 Qt 컨테이너

Qt 컨테이너와 std 알고리즘

#include <algorithm> 의 함수와 함께 Qt 컨테이너를 사용할 수 있습니다.

QList<int> list = {2, 3, 1};

std::sort(list.begin(), list.end());
/*
    Sort the list, now contains { 1, 2, 3 }
*/

std::reverse(list.begin(), list.end());
/*
    Reverse the list, now contains { 3, 2, 1 }
*/

int even_elements =
        std::count_if(list.begin(), list.end(), [](int element) { return (element % 2 == 0); });
/*
    Count how many elements that are even numbers, 1
*/

기타 컨테이너형 클래스

Qt에는 어떤 면에서 컨테이너와 유사한 다른 템플릿 클래스가 포함되어 있습니다. 이러한 클래스는 이터레이터를 제공하지 않으며 foreach 키워드와 함께 사용할 수 없습니다.

• QCache<Key, T>는 Key 타입의 키와 연관된 특정 타입 T의 객체를 저장하는 캐시를 제공합니다.
• QContiguousCache<T>는 일반적으로 연속적인 방식으로 액세스되는 데이터를 효율적으로 캐싱하는 방법을 제공합니다.

Qt의 템플릿 컨테이너와 경쟁하는 추가적인 비 템플릿 유형은 QBitArray, QByteArray, QString, QStringList 입니다.

알고리즘 복잡성

알고리즘 복잡성은 컨테이너의 항목 수가 증가함에 따라 각 함수가 얼마나 빠른지(또는 느린지)와 관련이 있습니다. 예를 들어, std::목록 중간에 항목을 삽입하는 것은 목록에 저장된 항목 수에 관계없이 매우 빠른 작업입니다. 반면에 QList 중간에 항목을 삽입하는 것은 QList 에 많은 항목이 포함되어 있는 경우 항목의 절반을 메모리에서 한 위치 이동해야 하므로 잠재적으로 매우 비용이 많이 들 수 있습니다.

알고리즘의 복잡성을 설명하기 위해 "큰 오" 표기를 기반으로 다음 용어를 사용합니다:

• 상수 시간: O(1). 컨테이너에 얼마나 많은 항목이 있든 상관없이 동일한 시간이 필요한 함수를 상수 시간으로 실행되는 함수라고 합니다. 한 가지 예로 QList::push_back()를 들 수 있습니다.
• 로그 시간: O(로그 n). 로그 시간으로 실행되는 함수는 실행 시간이 컨테이너에 있는 항목 수의 로그에 비례하는 함수입니다. 한 가지 예로 이진 검색 알고리즘을 들 수 있습니다.
• 선형 시간: O(n). 선형 시간으로 실행되는 함수는 컨테이너에 저장된 항목 수에 정비례하는 시간 내에 실행됩니다. 한 가지 예는 QList::insert()입니다.
• 선형 로그 시간: O(n 로그 n). 선형-로그 시간으로 실행되는 함수는 선형 시간 함수보다 점근적으로 느리지만 이차 시간 함수보다 빠릅니다.
• 이차 시간: O(n²). 이차 시간 함수는 컨테이너에 저장된 항목 수의 제곱에 비례하는 시간 내에 실행됩니다.

다음 표에는 순차 컨테이너 QList<T>의 알고리즘 복잡도가 요약되어 있습니다:

표에서 "Amort."는 "상각된 동작"을 의미합니다. 예를 들어, "Amort. O(1)"은 함수를 한 번만 호출하면 O(n) 동작을 얻을 수 있지만, 여러 번(예: n번 ) 호출하면 평균 동작이 O(1)이 된다는 의미입니다.

다음 표는 Qt의 연관 컨테이너와 집합의 알고리즘 복잡도를 요약한 것입니다:

QList, QHash, QSet 를 사용하면 항목 추가 성능이 O(로그 n)로 상각됩니다. 항목을 삽입하기 전에 예상 항목 수를 QList::reserve(), QHash::reserve() 또는 QSet::reserve()로 호출하여 O(1)로 낮출 수 있습니다. 다음 섹션에서는 이 주제에 대해 더 자세히 설명합니다.

프리미티브 및 재배치 가능한 유형에 대한 최적화

Qt 컨테이너는 저장된 요소가 재배치 가능하거나 심지어 프리미티브인 경우 최적화된 코드 경로를 사용할 수 있습니다. 그러나 원시형인지 재배치 가능한지 여부는 모든 경우에 감지할 수 없습니다. Q_DECLARE_TYPEINFO 매크로를 Q_PRIMITIVE_TYPE 플래그 또는 Q_RELOCATABLE_TYPE 플래그와 함께 사용하여 유형을 원시적이거나 재배치 가능한 것으로 선언할 수 있습니다. 자세한 내용과 사용 예는 Q_DECLARE_TYPEINFO 문서를 참조하세요.

Q_DECLARE_TYPEINFO 를 사용하지 않는 경우, Qt는 기본 형을 식별하기 위해 std::is_trivial_v<T>를 사용하고, 재배치 가능한 형을 식별하기 위해 std::is_trivially_copyable_v<T>와 std::is_trivially_destructible_v<T>를 모두 요구할 것입니다. 이는 성능이 최적이 아닐 수도 있지만 항상 안전한 선택입니다.

성장 전략

QList<T>, QString, QByteArray 은 해당 항목을 메모리에 연속적으로 저장하고, QHash<키, T>는 해시의 항목 수에 비례하는 크기의 해시 테이블을 유지합니다. 컨테이너 끝에 항목이 추가될 때마다 데이터를 재할당하지 않기 위해 이러한 클래스는 일반적으로 필요 이상으로 많은 메모리를 할당합니다.

다른 QString 에서 QString 을 빌드하는 다음 코드를 살펴보세요:

QString onlyLetters(const QString &in)
{
    QString out;
    for (qsizetype j = 0; j < in.size(); ++j) {
        if (in.at(j).isLetter())
            out += in.at(j);
    }
    return out;
}

out 문자열을 한 번에 한 글자씩 추가하여 동적으로 빌드합니다. QString 문자열에 15000자를 추가한다고 가정해 보겠습니다. 그러면 QString 공간이 부족해지면 8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376 등 11번(가능한 15000개 중)의 재할당이 발생합니다. 결국 QString 에는 16376 개의 유니코드 문자가 할당되고 그 중 15000 개가 사용됩니다.

위의 값은 다소 이상하게 보일 수 있지만 여기에는 기본 원칙이 있습니다. 매번 크기가 두 배로 증가합니다. 더 정확하게는 2의 다음 거듭제곱에서 16바이트를 뺀 값으로 진행합니다. QString 은 내부적으로 UTF-16을 사용하므로 16바이트는 8글자에 해당합니다.

QByteArray 는 QString 와 동일한 알고리즘을 사용하지만 16바이트는 16자에 해당합니다.

QList<T>도 같은 알고리즘을 사용하지만 16바이트는 16/sizeof(T) 요소에 해당합니다.

QHash<키, T>는 완전히 다른 경우입니다. QHash 의 내부 해시 테이블은 2의 거듭제곱만큼 커지며, 커질 때마다 항목은 qHash(키) % QHash::capacity() (버킷 수)로 계산된 새 버킷에 재배치됩니다. 이 설명은 QSet<T>와 QCache<키, T>에도 적용됩니다.

대부분의 응용 프로그램에서는 Qt에서 제공하는 기본 증가 알고리즘으로 충분합니다. 더 많은 제어가 필요한 경우 QList<T>, QHash<키, T>, QSet<T>, QString, QByteArray 에서 항목을 저장하는 데 사용할 메모리 양을 확인하고 지정할 수 있는 세 가지 함수를 제공합니다:

• capacity()는 메모리가 할당된 항목의 수( QHash 및 QSet 의 경우 해시 테이블의 버킷 수)를 반환합니다.
• reserve(size)는 크기 항목에 대한 메모리를 명시적으로 사전 할당합니다.
• squeeze()는 항목을 저장하는 데 필요하지 않은 메모리를 해제합니다.

컨테이너에 저장할 항목 수를 대략적으로 알고 있다면 reserve()를 호출하여 시작하고, 컨테이너 채우기가 끝나면 squeeze()를 호출하여 미리 할당된 여분의 메모리를 해제할 수 있습니다.