728x90 리스트3 [Algorithm] 벡터(Vector)와 리스트(List)의 차이점 벡터(vector) 벡터는 동적배열을 만드는 연산을 수행한다. 따라서 연속적인 메모리를 확보한다. 자신의 요소를 내부의 동적 배열 ( dynamic array )로 복사한다. 임의 접근 연산자를 제공([])하기 때문에 어떠한 값에 접근하든 상수시간이 소요된다 동적배열이기 때문에 배열의 중간에 새로 추가하거나 삭제하면 많은 값이 이동해야하기 때문에 오랜 시간이 걸린다 따라서 중간에 추가 하기보단 뒷부분에 추가한다 ( push_back ) 동적배열이기 때문에 크기의 확장과 축소가 자유롭지만 재할당 비용은 크다. 장점 임의접근을 상수시간에 가능하다. 따라서 읽기에 매우 강하다. 단점 중간에 값을 추가/제거하는 비용이 크다 재할당 비용이 크다 리스트(list) 리스트는 요소들을 양방향 연결리스트의 형태로 관리한.. [프로그래밍 공부]/Algorithm 2022. 1. 15. 더보기 ›› [Algorithm] STL 순방향 리스트 (Forward list) 순방향 리스트 C++11에서 도입된 컨테이너로 자신의 요소를 단방향 연결리스트로 관리한다. 사진 출처 : http://hyeonstorage.tistory.com/259 순방향 연결리스트를 사용하기 위해서는 를 인클루드 해야한다. namespace std 안에 정의되어 있다. 기능 순방향 리스트는 개념적으로 되돌아가지 못하는 리스트와 같다. 따라서 리스트가 제공하지 않는 기능은 제공되지 않는다. 리스트보다 좋은 점은 메모리를 덜 사용하고 실행 시간이 조금 더 빠르다 되돌아가지 못하기 때문에 리스트에는 없는 제약 조건이 몇 가지 있다. 1. 양방향이 아닌 순방향 반복자를 제공한다. 따라서 역방향 연산은 제공되지 않는다. 2. size() 함수를 제공하지 않는다. 공간이나 시간 부하를 만드는 특성을 생략했기.. [프로그래밍 공부]/Algorithm 2022. 1. 15. 더보기 ›› [Algorithm] STL 리스트(List) 리스트 리스트는 요소들을 양방향 연결리스트의 형태로 관리한다. 리스트를 사용하기 위해서는 를 인클루드 해야한다. 리스트는 namespace std에 정의되어 있다. 리스트 객체는 앵커(anchor)라 불리는 포인터 2개를 제공한다. 이 두 개의 포인터는 첫 번째와 마지막 요소를 가리킨다. 새로운 요소를 삽입하기 위해서는 이 포인터를 조작해야한다. 이로인해 벡터, 데크, 배열과는 다른 특성이 나타난다. 1. 리스트는 임의 접근을 제공하지 않는다. n번째 요소에 접근하기 위해서는 링크를 타고 가야 한다. 양방향 리스트로 되어있기 때문에 뒤에서도 타고 갈 수 있다. 2. 각 위치에서 요소를 삽입하고 제거하는 연산은 빠르다. 다른 요소의 이동이 필요 없기 때문이다. 포인터만 몇개 고치면 바로 삽입/삭제가 가능하.. [프로그래밍 공부]/Algorithm 2022. 1. 15. 더보기 ›› 728x90 이전 1 다음
