질문 게시판 / Q&A

인접리스트 생성에 관해서

by holymoly, 11월 3일, 18:46

//1번
vector<vector<int>> graph;
vector<int> a;
graph.reserve(10);
for(int i = 1; i <= 5; i++){
a.push_back(i);
}
graph[5] = a;
cout << graph[5][1];

//2번
vector<list<int>> graph2;
list<int> b;
graph2.reserve(10);
for(int i = 1; i <= 5; i++){
b.push_back(i);
}
graph2[5] = b;

위 2개의 간단한 코드가 있는데요 1번코드에서는 vector<int>a 가 graph[5]에 대입될 수 있고 컴파일도 잘 되는데
2번코드에서는 list<int> a 가 graph2[5]에 대입이 되지않고 런타임 에러가 납니다. 이유가 뭔지 궁금합니다!
그리고 vector<list<int>> 를 사용하려면 list<int>를 vector에 순서대로 push_back 해주는 방법밖에 없는건가요?

holymoly , 11월 4일, 22:06
 좋은자료 감사합니다! 
prof , 11월 4일, 14:11
 이 자료를 한번 보세요.

An In-Depth Study of the STL Deque Container

https://www.codeproject.com/Articles/5425/An-In-Depth-Study-of-the-STL-Deque-Container 
holymoly , 11월 4일, 03:33
 #prof
정말 감사합니다!! 아무리 구글링을 해도 원하는게 안나와서 답답했는데, 예시 코드까지 만들어 주셔서 이해가 잘 되었습니다! 
reserve를 해주고 그 중간쯤에 값을 넣으면 range-based auto로 출력을 할 때 인지를 못하는게 신기하네요
그리고 중간에 값을 넣어야 겠다 싶으면 graph.resize(20, list<int>()); 를 해주니까 빈 리스트를 손으로 push할 필요없어서 좋은 것 같습니다!
그런데
vector< int > vec;
vec.reserve(10);
vec[5] = 99;
cout << vec[5]; 
이렇게 하면 출력은 99로 잘 나옵니다. 그리고
vector< X > vec; 에서
X가 int, double, longlong, char, vector< Y > 일때도 마찬가지로 vec[5] = 'a'; 이런게 허용은 되고 random access로 출력은 가능한 것 같습니다..
하지만 X가 string, list<Y>, set<Y> 같은 타입일 때는 
vec[5] = "asdf";  <-이와 같은 문장이 교수님이 말씀하신 것 처럼 허용이 되지 않습니다.
element 의 타입에 무관하게 reserve로 할당된 위치에 어떤 원소가 없으면,  random access 를 통한 대입 연산이 허용되지 않아야 하는데
왜 원소의 타입에 따라서 대입연산이 허용되고 말고의 차이가 있는건가요?
제 생각에는 컴파일 과정에서 뭔가 있거나 타입별로 메모리주소 할당 방식이 다르다거나 그런게 있어서 차이가 존재하는것 같은데 잘 모르겠습니다
자꾸 궁금한게 생깁니다ㅠ 답변 해주신다면 정말 감사하겠습니다!! 
prof , 11월 4일, 00:54
 // ----  이 코드를 보세요. 아마 쉽게 이해가 될 것입니다.
// reserve( )는 실제 자료구조에 변화가 없습니다.


#include <bits/stdc++.h>
#define allout(MSG,X)   std::cout<<"\n"<<MSG<<" ";for(auto w:X)std::cout<<w<<", "
using namespace std ;


int main () {

        vector< int> PNU = { 11, 12, 13, 14, 15};
        array <int,7> Temp = {51, 52, 53, 54, 55, 56, 57} ;
        allout(" step 1=", PNU) ;

        PNU.reserve(20) ;
        allout(" step 2=", PNU) ; // reserve( )해봐야 소용없십니데이.

        PNU[10]= -999 ;    // 헛손질
        allout(" step 3=", PNU) ; // reserve( )해봐야 소용없십니데이.
        cout << "\n PNU의 끝 원소=" << *(PNU.end()-1) ;

        PNU.assign( Temp.begin(), Temp.end()) ;
        allout(" step 4=", PNU) ;

        PNU[5]= 87654321 ;
        allout(" step 5=", PNU) ;

  return 0;
} 
prof , 11월 4일, 00:37
 아.. 질문을 제가 오해했습니다. 다음 코드를 보세요.

#include <bits/stdc++.h>
#define allout(MSG,X)   std::cout<<"\n"<<MSG<<" ";for(auto w:X)std::cout<<w<<", "
using namespace std ;


void print_vv( vector<vector<int>> X ){
    cout << "\n In print_vv() " ;
    for(auto w : X){
        for(auto u : w ) {
            cout << u << ", ";
        }
        cout << "\n" ;
    }
}


int main () {

        vector<vector<int>> graph;
        vector<int> a;
        graph.reserve(10);

        for(int i = 1; i <= 5; i++){
            a.push_back(i);
        }
        graph[5] = a;
        cout << "\n graph[5][1]= " << graph[5][1];
        cout << "\n graph[5][0]= " << graph[5][0];
        allout( " graph[5]=", graph[5]) ;
        allout( " graph[1]=", graph[1]) ;
//2번

        vector<list<int>> graph2;
        list<int> b;
        list<int> c;
        graph2.reserve(10);

        for(int i = 1; i <= 5; i++){
            b.push_back(i);
        }

        c = list<int>() ;
        graph2.push_back(c) ;
        graph2.push_back(c) ;
        graph2.push_back(c) ;
        graph2[2] = b;
        allout( " graph2[1]=", graph2[2]) ;

  return 0;
}

A.reserve( )는 말그대로 자리만 준비하는 것입니다. 실제
데이터는 없습니다. 나중에 들어올 것을 준비하라는 것이지요.
따라서 우리가

X[k]=w

를 하려면 reserve한 상태에서 하면 안되도 실제 X[k]에 뭔가 어떤
원소가 있어야 합니다.

즉
vector<int> Q ;

에서 
Q.reserve( 10000)을 한다고 해서 Q[50]이 만들어져 있는 것
좀 전문적으로 말하자면 instanciated된 것은 아니라는 것이죠.
그야말로 "자리만 잡아둔" 상태인거죠.

c = list<int>() ;
        graph2.push_back(c) ;
        graph2.push_back(c) ;
        graph2.push_back(c) ;
        graph2[2] = b;

이렇게 하면 실제 list c에 3개의 원소가 들어간 것입니다.
이 상태라면 Xk]=w은 한번에 수행이 되죠.

요약:

vector <X> mymy ;
mymy.reserve(1000) ;

을 한다고 해서 mymy[10]이 있는 것은 아니다.
mymy[10]= THIS, 이 작업이 동작되려면

1) initialize할 때뭔가를 채워 넣든지
2) 아니면 mymy[10]에 실제 어떤 원소가 있어여 한다.

vetor의  reserve(k)는 다음 vector.push_back( )을 위하여
자리를 미리 확보해주는 것이지 k개의 항목을 뭔가로 채워주는 것은 아니다.

--------------
아주 아주 중요한 질문을 했습니다. 이전까지 가르치면서 이 내용은
가르치지 않았고, 어떤 C++/STL 교재에도 나오지 않는데
아주 유용한 질문같습니다.  질문한 친구는 
수퍼 프로그래머 자질이 보입입니다. ㅎㅎㅎㅎ 
holymoly , 11월 3일, 22:11
 #prof
답변감사합니다!
graph2는 vector임에도 불구하고 
element의 타입이 list<int> 이기 때문에 random access를 통한 요소의 대입이 불가능하다고 이해하면 되나요..? 
prof , 11월 3일, 19:17
 동영상 강의에서 몇번 설명을 했는데요...

list에서는 random access가 안됩니다.
목욕탕 옷보관함을 생각해봅니다.

우리는 우리가 넣은 x칸을 열어 옷을 꺼내야 합니다.
그런데 내가 받은 것은 그 칸이 아니라  a칸 열쇠입니다.
이걸로  a칸을 열면 b칸 엻쇠가 나옵니다.
이제 이걸로 b칸을 열면 다시  c칸 열쇠가 있습니다.
이렇게 한 20개 칸을 열면 마지막에 x칸 열쇠가 있다고 합니다.

linked list은 이런 식이기 때문에 시작 열쇠 a를 알고 있어도
그로부터 5칸 앞선 곳은 어딘지 알수가 없습니다.

그래서 list iterator를 it라고 하면
it++
it--
만 허용됩니다.

it = it + 5 는 안됩니다.

그래서 이런 것이 안됩니다. 
graph2[5] = b;

넣으려면 push_back이나 insert만 가능합니다.
단 insert를 하려면 그곳까지 "새빠지게" 찾아 가야 합니다.

한번에 random access에서 X[k]=w 이게 안되는 것입니다.