c++STL 용기 요약:vertor 와 list 의 응용

7401 단어 stlvertorlist
STL 은 서로 조합 하여 사용 할 수 있 는 6 대 구성 요 소 를 제공 합 니 다.
1.용기(containers):각종 데이터 구조,예 를 들 어 vertor,list,deque,set,map.실현 의 측면 에서 볼 때 STL 용 기 는 class template 이다.
2.알고리즘(algorithms):sort,search,copy,earse 와 같은 여러 가지 알고리즘.STL 알고리즘 은 function template 의 일종 이다.
3.교체 기(iterators):용기 와 알고리즘 간 의 접착제 역할 을 하 는 이른바'팬 포인터'입 니 다.모든 STL 용 기 는 자신 만 의 전용 교체 기 를 가지 고 있다.
4.모방 함수(functors):행동 유사 함수 로 알고리즘 의 일부 전략 으로 사용 할 수 있 습 니 다.실현 의 측면 에서 볼 때 모방 함 수 는 operator()를 다시 불 러 온 class 나 class template 입 니 다.
5.어댑터(adapters):용기 나 모방 함수 나 교체 기 핑 계 를 꾸 미 는 데 사용 되 는 물건 입 니 다.예 를 들 어 quue 와 stack.
6.설정 기(allocators):공간의 설정 과 관 리 를 책임 집 니 다.설정 기 는 동적 공간 분배,공간 관리,공간 방출 을 실현 하 는 class template 입 니 다.
STL 은 일반화 위 에 세 워 진 것 이다.배열 은 용기 로 일반화 되 고 포 함 된 대상 의 유형 을 매개 변수 화 합 니 다.함수 가 알고리즘 으로 일반화 되 어 사용 하 는 교체 기의 유형 을 매개 변수 화 하 였 습 니 다.포인터 가 교체 기로 일반화 되 어 가리 키 는 대상 의 유형 을 매개 변수 화 시 켰 다.
vector,string,deque,list 는 표준 시퀀스 용기 라 고 불 린 다.
set,multiset,map,multimap 는 표준 관련 용기 입 니 다.
비 표준 시퀀스 용기 slist 와 rope.slist 는 단 방향 링크 이 고 rope 는 본질 적 으로 중형 문자열 입 니 다.
비표 준 관련 용기 hashset、hash_multiset、hash_map 와 hashmultimap。
표준 비 STL 용기,배열,bitset,valarray,stack,quue 와 priority 포함queue。
교체 기 는 다섯 종류 로 나 뉜 다.
입력 교체 기 는 모든 교체 위치 에서 한 번 만 읽 을 수 있 는 읽 기 전용 교체 기 입 니 다.
출력 교체 기 는 모든 교체 위치 에서 한 번 만 쓸 수 있 는 교체 기 입 니 다.
입력 과 출력 교체 기 는 읽 기와 쓰기 입력 과 출력 흐름(예 를 들 어 파일)으로 만들어 집 니 다.
전방 향 교체 기 는 입력 과 출력 교체 기 능력 이 있 지만,반복 적 으로 읽 거나 위 치 를 쓸 수 있다.
양 방향 교체 기 는 앞 방향 교체 기 처럼 후퇴 를 제외 하고 전진 처럼 쉽다.표준 관련 용 기 는 모두 양 방향 교체 기 를 제공한다.리스트 도 있어 요.
연속 메모리 용기(배열 기반 용기 라 고도 함)는 하나 이상 의 메모리 블록 에 요 소 를 저장 합 니 다.새 요소 가 검색 되 거나 저 장 된 요소 가 삭제 되면 같은 메모리 블록 에 있 는 다른 요 소 는 새 요소 에 공간 을 제공 하거나 원래 삭 제 된 요소 가 차지 하 는 공간 을 채 워 야 합 니 다.이런 이동 은 효율 과 이상 안전 에 영향 을 주 었 다.표준 연속 메모리 용 기 는 vector,string,deque 입 니 다.비표 준 rope 도 연속 메모리 용기 다.
노드 기반 용 기 는 모든 메모리 블록(동적 할당)에 하나의 요소 만 저장 합 니 다.용기 요소 의 삽입 이나 삭 제 는 노드 의 내용 이 아니 라 노드 를 가리 키 는 지침 에 만 영향 을 줍 니 다.따라서 물건 이 삽입 되 거나 삭 제 될 때 요소 값 은 이동 할 필요 가 없습니다.링크 로 표 현 된 용기-예 를 들 어 list 와 slist―는 노드 를 바탕 으로 하 는 것 이 고 모든 표준 관련 용기 도(그들의 전형 적 인 실현 은 균형 트 리)이다.비 표준적 인 산열 용 기 는 서로 다른 노드 기반 의 실현 을 사용한다.
1、vector
vector 는 배열 과 유사 합 니 다.연속 적 인 메모리 공간 을 가지 고 시작 주소 가 변 하지 않 기 때문에 랜 덤 액세스(즉,[]연산 자 를 사용 하여 그 중의 요소 에 접근 하 는 것)를 지원 할 수 있 습 니 다.그러나 메모리 공간 이 연속 적 이기 때문에 중간 에 삽입 하고 삭제 하면 메모리 블록 의 복사(복잡 도 는 O(n)를 초래 할 수 있 습 니 다.또한,이 배열 의 메모리 공간 이 부족 할 때 충분 한 메모 리 를 다시 신청 하고 메모리 복사 가 필요 합 니 다.이것들 은 모두 vector 의 효율 에 큰 영향 을 주 었 다.
vector 는 데이터 형식 이 아니 라 하나의 템 플 릿 일 뿐 다양한 데이터 형식 을 정의 할 수 있 습 니 다.vector 형식의 모든 종 류 는 저장 요소 의 종 류 를 지정 합 니 다.따라서 vector와 vector은 모두 데이터 형식 입 니 다.
 
vector 대상 의 정의 와 초기 화
vector  v1;
vector 는 T 형식의 대상 을 저장 합 니 다.기본 구조 함수 v1 이 비어 있 습 니 다.
vector v2(v1);
v2 는 v1 의 사본 이다.
vector v3(n, i);
v3 는 n 개의 값 이 i 인 요 소 를 포함 합 니 다.
vector ivec4(10, -1);     // 10 elements, each initialized to -1
vector svec(10, "hi!"); // 10 strings, each initialized to "hi!"
vector 의 조작
v.empty()
v 가 비어 있 으 면 true 로 돌아 갑 니 다.그렇지 않 으 면 false 로 돌아 갑 니 다.
v.size()
v 에서 요소 의 개 수 를 되 돌려 줍 니 다.
v.push_back(t)
v 의 끝 에 t 의 요 소 를 추가 합 니 다.
v[n]
v 의 위치 가 n 인 요 소 를 되 돌려 줍 니 다.
v1 = v2
v1 의 요 소 를 v2 의 요소 의 던 전 으로 교체 합 니 다.
v1 == v2
v1 과 v2 가 같 으 면 true 로 돌아 갑 니 다.
!=, <, <=, >, >=
이 조작 부호 들 이 습관 적 으로 가지 고 있 는 의 미 를 유지 하 다.
vector 에 요소 추가:

string word;

vector<string> text;        // empty vector

while (cin >> word) {

    text.push_back(word);  // append word to text

}
  vector :


for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)

    ivec[ix] = 0;

vector 교체 기
모든 용 기 는 begin 과 end 라 는 함 수 를 정의 하여 교체 기 를 되 돌려 줍 니 다.용기 에 요소 가 있 으 면 begin 에서 돌아 오 는 교체 기 는 첫 번 째 요 소 를 가리 키 고 있 습 니 다.

vector<int>::iterator iter = ivec.begin();
end 에서 돌아 오 는 교체 기 는 vector 의'말단 요소 의 다음'을 가리 키 고 있 습 니 다.일반적으로 말단 교체 기(of-the-end iterator)라 고 부 르 는데 존재 하지 않 는 요 소 를 가리 키 고 있 음 을 나타 낸다.vector 가 비어 있 으 면 begin 이 돌아 오 는 교체 기 는 end 가 돌아 오 는 교체 기와 같 습 니 다.

for (vector<int>::iterator iter = ivec.begin(); iter != ivec.end(); ++iter)

    *iter = 0;  // set element to which iter refers to 0
const_iterator
앞의 프로그램 은 vector::iterator 로 vector 의 요소 값 을 변경 합 니 다.모든 용기 유형 은 const 라 는 이름 도 정의 합 니 다.iterator 의 형식 입 니 다.이 형식 은 용기 내 요소 에 만 접근 할 수 있 지만 값 을 바 꿀 수 없습니다.

for (vector<string>::const_iterator iter = text.begin();  iter != text.end(); ++ iter)

    *iter = " ";     // error: *iter is const
2、list
list 는 데이터 구조의 양 방향 링크 로 이 루어 지기 때문에 메모리 공간 은 연속 되 지 않 을 수 있 습 니 다.따라서 포인터 로 만 데이터 에 접근 할 수 있 습 니 다.이 특징 으로 인해 무 작위 액세스 가 매우 비효 율 적 이 고 중간 요 소 를 옮 겨 다 니 며 복잡 도 O(n)를 검색 해 야 하기 때문에[]연산 자 를 다시 불 러 오지 않 았 습 니 다.그러나 링크 의 특징 으로 인해 임의의 삭제 와 삽입 을 효율 적 으로 지원 할 수 있 습 니 다.
list::iterator 와 vector::iterator 의 차이 점:

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

int main( void )
{
        vector<int> v; 
        list<int> l;

        for (int i=0; i<8; i++)     // v l
        {
                v.push_back(i);
                l.push_back(i);
        }

        cout << "v[2] = " << v[2] << endl;
        //cout << "l[2] = " << l[2] << endl;       // ,list []
        cout << (v.begin() < v.end()) << endl;
        //cout << (l.begin() < l.end()) << endl;   // ,list::iterator < >
        cout << *(v.begin() + 1) << endl;

        vector<int>::iterator itv = v.begin();
        list<int>::iterator itl = l.begin();
        itv = itv + 2;
        //itl = itl + 2;                  // ,list::iterator +
        itl++;itl++;                    //list::iterator ++, ++ 。
        cout << *itv << endl;
        cout << *itl << endl;

        return 0;
}
vector 는 연속 적 인 메모리 공간 을 가지 고 있 기 때문에 무 작위 접근 을 지원 할 수 있 습 니 다.따라서 vector:iterator 는"+","+=","<"등 조작 자 를 지원 합 니 다.한편,list 의 메모리 공간 은 연속 되 지 않 을 수 있 습 니 다.무 작위 접근 을 지원 하지 않 기 때문에 list:iterator 는"+","+=","<"등 연산 자 를 지원 하지 않 기 때문에 코드 20,26 줄 에 컴 파일 오류 가 발생 할 수 있 습 니 다."+"를 사용 하여 교체 할 수 있 습 니 다.예 를 들 어 코드 27 줄,itl+를 두 번 사용 하여 itl 을 이동 할 수 있 습 니 다.그리고 list 도[]연산 자 를 지원 하지 않 기 때문에 코드 18 줄 에 컴 파일 오류 가 발생 했 습 니 다.한 마디 로 하면 삽입 과 삭제 의 효율 에 신경 쓰 지 않 고 효율 적 인 액세스 가 필요 하 다 면 vector 를 사용 합 니 다.많은 삽입 과 삭제 가 필요 하 다 면 즉시 액세스 에 관심 이 없 으 면 list 를 사용 해 야 합 니 다.
vector 는 연속 적 인 메모리 공간 을 가지 고 있 기 때문에 무 작위 접근 을 지원 합 니 다.삽입 과 삭제 의 효율 에 신경 쓰 지 않 고 효율 적 인 접근 이 필요 하 다 면 vector 를 사용 합 니 다.list 는 연속 되 지 않 는 메모리 공간 을 가지 고 있 기 때문에 무 작위 접근 을 지원 합 니 다.많은 삽입 과 삭제 가 필요 하고 즉시 접근 에 관심 이 없 으 면 list 를 사용 해 야 합 니 다.대부분의 삽입 과 삭제 가 시퀀스 의 머리 나 끝 에 발생 할 때 deque 라 는 데이터 구 조 를 선택 할 수 있 습 니 다.

좋은 웹페이지 즐겨찾기