C++ : 벡터의 비 연속 인덱스에 값을 할당 하시겠습니까?

Question

알 수없는 크기의 벡터를 선언하려면 인덱스 5, 인덱스 10, 인덱스 1, 인덱스 100에 순서대로 값을 할당하십시오. 벡터에서 쉽게 할 수 있습니까?

쉬운 방법이없는 것 같습니다. 크기가없는 벡터를 초기화하면 resize() 또는 push_back()을 수행하여 메모리를 할당하지 않고 인덱스 5에 액세스 할 수 없습니다. 그러나 resize는 이전에 저장된 값을 벡터에서 지 웁니다. 나는 처음부터 크기를 주어서 벡터를 만들 수 있지만 벡터의 크기가 얼마나 큰지는 알지 못합니다.

그래서 고정 된 크기를 선언 할 필요가 없으며 벡터의 불연속 인덱스에 계속 액세스 할 수 있습니까?

(이 작업에서는 어레이가 더 쉬울 것으로 생각됩니다.)

Answer 1

크기를 조정해도 벡터가 지워지지 않습니다. 벡터의 모든 값을 보존하고 그 인덱스 n 액세스가되도록 충분한 기본 초기화 값을 추가합니다

if (v.size() <= n) 
     v.resize(n+1); 
    v[n] = 42; 

이 : 당신은 쉽게 뭔가를 할 수 있습니다.

즉, 모든 색인이나 연속적인 메모리가 필요하지 않은 경우 다른 데이터 구조를 고려할 수 있습니다.

Answer 2

정수 키와 값 사이의 std :: map은 더 쉬운 해결책이되지 않습니까? 벡터는 연속적으로 메모리를 할당해야하기 때문에 가끔씩 색인을 사용하는 경우 많은 메모리를 낭비하게됩니다.

Answer 3

resize() 벡터에 저장된 값을 지우지 않습니다.
는 this documentation

가 나는 또한 주장 볼 것을이 당신이 vector 당신을 위해 컨테이너하지 않을 수 다음 그 수를해야 할 것입니다 경우. 아마도 map을 사용해 보셨습니까?

Answer 4

인접한 값 집합을 포함하지 않는 데이터 구조는 스파 스 또는 압축 데이터 구조로 알려져 있습니다. 이것이 당신이 찾고있는 것 같습니다.

이 경우, 스파 스 벡터이 필요합니다. 부스트에 구현 된 코드가 있습니다. link text

일반적으로 스파 스 구조는 메모리를 절약하는 데 사용됩니다. 문제 설명에서 메모리 사용에 대해 실제로 신경 쓰지 않고, 아직 존재하지 않는 요소 (자동 크기 조정 컨테이너 필요)를 처리하는 것이 가능합니다. 이 경우 외부 종속성이없는 간단한 솔루션은 다음과 같습니다.

벡터를 보유하고 모든 벡터 메소드를 전달하는 템플릿 클래스를 만듭니다. 인덱스가 범위를 벗어난 경우 연산자 []를 변경하여 벡터의 크기를 조정하십시오.

// A vector that resizes on dereference if the index is out of bounds. 
template<typename T> 
struct resize_vector 
{ 
    typedef typename std::vector<T>::size_type size_type; 
    // ... Repeat for iterator/value_type typedefs etc 

    size_type size() const { return m_impl.size() } 
    // ... Repeat for all other vector methods you want 

    value_type& operator[](size_type i) 
    { 
     if (i >= size()) 
      resize(i + 1); // Resize 
     return m_impl[i]; 
    } 
    // You may want a const overload of operator[] that throws 
    // instead of resizing (or make m_impl mutable, but thats ugly). 

private: 
    std::vector<T> m_impl; 
}; 

다른 답변에서 언급했듯이 벡터 크기를 조정하면 요소가 지워지지 않습니다. 대신 크기 조정을 통해 새 요소를 추가하면 기본 생성자가 호출됩니다. 따라서이 클래스를 사용할 때 operator[]이 기본 생성 객체 참조를 반환 할 수 있다는 것을 알아야합니다. 그러므로 <T>의 기본 생성자는이 목적을 위해 객체를 적절한 값으로 설정해야합니다.요소에 이전에 값이 할당되었는지 여부를 알아야 할 경우 예를 들어 감시 값을 사용할 수 있습니다.

std::map<size_t, T>을 사용하기위한 제안은 추가 메모리 사용, 불연속 요소 저장 및 O (1) 대신 O (logN) 조회가 필요하다는 가정하에 솔루션으로 장점이 있습니다. 이것은 모두 희소 표현 또는 자동 크기 조정을 원하는지 여부에 달려 있습니다. 잘하면이 답변은 두 가지 모두를 다룹니다.