알고리즘 문제에서 STL의 벡터 사용 방법 질문드립니다.

  • inpp
    inpp

    안녕하세요.
    C++ 사용 시
    endl이 오래 걸려서 \n으로 사용하는게 빠르다던가
    cin cout 사용 시
    sync_with_stdio(false); 등을 사용한다 이런 점 등 많이 알게 됐는데
    궁금한 점이 2가지 있어서 질문드립니다.

    첫 번째로 책에 보면
    반복문에서 vector.size() 구문을 많이 쓰는데
    이게 strlen처럼 시간을 많이 잡아먹을거 같은데, 시간에 영향이 거의 안미쳐서 사용하는 것인가요? 아니면 책의 가독성을 위해 사용한 것인가요? 실제로는 strlen처럼 다른 변수에 저장한 후 루프를 돌리는게 맞는 것인지?

    두 번째로
    벡터 사용 시에
    push_back은 시간이 오래 걸린다고 들었는데
    알고리즘에 vector 사용 시, 입력값을 받아 자료를 추가할 때
    vector.push_back()의 형식으로 넣어줘도 시간 상 안 좋은 영향이 없는지? 혹시 있다면 주로 어떤 식으로 사용하는지 궁금합니다.

    알려주시면 감사하겠습니다!


    8년 전
4개의 댓글이 있습니다.
  • kcm1700
    kcm1700

    C++11 기준으로,
    vector에서 size()는 상수 시간임이 보장이 되어 있습니다.
    vector에서 push_back()은 amortized 상수 시간임이 보장되어 있습니다. (개별 연산은 오래 걸릴 수 있어도 전체를 놓고 보면 상수 시간)

    push_back의 속도가 걱정된다면 reserve()함수를 미리 불러주면 됩니다. 하지만 그다지 차이는 안 납니다.


    8년 전 link
  • kcm1700
    kcm1700

    vector에서 size()를 호출하는 것은 자주 쓰이는 최적화 해주는 컴파일러라면 다른 변수에 저장한 후 루프를 돌리는 것과 차이가 아예 안 나거나 거의 안 납니다.
    보통의 경우에 push_back()은 충분히 빠릅니다.


    8년 전 link
  • Being
    Being

    공부하시는 김에 emplace_back()도 찾아보심이.. :)


    8년 전 link
  • inpp
    inpp

    답변 감사드립니다!
    자꾸 마음에 걸리면서 코딩했는데 이제 좀 알거같네요


    8년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.