C ++ 11에서 표준 라이브러리 컨테이너를 효율적으로 선택하려면 어떻게해야합니까?

C ++ 11에서 표준 라이브러리 컨테이너를 효율적으로 선택하려면 어떻게해야합니까?

---

"C ++ 컨테이너 선택"이라는 잘 알려진 이미지 (치트 시트)가 있습니다. 원하는 사용법에 가장 적합한 컨테이너를 선택하는 순서도입니다.

이미 C ++ 11 버전이 있는지 아는 사람이 있습니까?

이것은 이전 것입니다 :

---

내가 아는 것은 아니지만 텍스트로 할 수 있다고 생각합니다. 또한 차트는 list일반적으로 좋지 않은 컨테이너가 아니기 때문에 약간 벗어났습니다 forward_list. 두 목록 모두 틈새 응용 프로그램을위한 매우 특수한 컨테이너입니다.

이러한 차트를 작성하려면 두 가지 간단한 지침이 필요합니다.

• 시맨틱을 먼저 선택
• 몇 가지 선택이 가능할 때 가장 간단한 방법을 선택하십시오

성능에 대한 걱정은 일반적으로 처음에는 쓸모가 없습니다. 수천 가지 (또는 그 이상)의 아이템을 다루기 시작할 때 큰 O 고려 사항은 실제로 시작됩니다.

컨테이너에는 두 가지 큰 범주가 있습니다.

• 연관 컨테이너 : find작업이 있습니다
• 간단한 시퀀스 컨테이너

다음은 그 위에 여러 어댑터를 구축 할 수 있습니다 : stack, queue, priority_queue. 여기에 어댑터를 남겨두면 인식 할 수있을만큼 충분히 전문화되어 있습니다.

---

질문 1 : 연관성 ?

• 하나의 키로 쉽게 검색 해야하는 경우 연관 컨테이너가 필요합니다.
• 요소를 정렬해야하는 경우 정렬 된 연관 컨테이너가 필요합니다.
• 그렇지 않으면 질문 2로 이동하십시오.

질문 1.1 : 주문 ?

• 특정 주문이 필요하지 않은 경우 unordered_컨테이너를 사용하거나 그렇지 않으면 기존 주문을 사용하십시오.

질문 1.2 : 별도의 키 ?

• 키가 값 map과 다른 경우 a를 사용하고 그렇지 않으면 aset

질문 1.3 : 중복 ?

• 중복을 유지하려면을 사용하고 multi그렇지 않으면을 사용하십시오 .

예:

고유 한 ID를 가진 사람이 여러 명 있다고 가정하고 가능한 한 간단하게 ID에서 사람 데이터를 검색하려고합니다.

1. find함수, 따라서 연관 컨테이너를 원합니다.

   1.1. 나는 주문에 대해 신경 쓰지 않았으므로 unordered_컨테이너

   1.2. 내 키 (ID)는 연결된 값과 별개이므로map

   1.3. ID는 고유하므로 복제본이 들어오지 않아야합니다.

최종 답변은 다음과 같습니다 std::unordered_map<ID, PersonData>.

---

질문 2 : 메모리가 안정적 입니까?

• 요소가 메모리에서 안정적이어야하는 경우 (즉, 컨테이너 자체가 수정 될 때 움직이지 않아야 함) 일부를 사용하십시오. list
• 그렇지 않으면 질문 3으로 이동하십시오.

질문 2.1 : 어느 것 ?

• 에 정착 list; a forward_list는 적은 메모리 풋 프린트에만 유용합니다.

---

질문 3 : 동적 크기 ?

• 컨테이너 (컴파일 시간) 알려진 크기를 가지고있는 경우 와 이 크기는 프로그램의 과정에서 변경되지 않습니다, 그리고 요소가 작도 기본이다 또는 당신이합니다 (사용하여 전체 초기화 목록을 제공 할 수있는 { ... }구문을), 다음을 사용 array. 전통적인 C- 어레이를 대체하지만 편리한 기능으로 대체합니다.
• 그렇지 않으면 질문 4로 이동하십시오.

---

질문 4 : 더블 엔드 ?

• 앞면과 뒷면 모두에서 항목을 제거하려면을 사용하고 deque그렇지 않으면을 사용하십시오 vector.

---

기본적으로 연관 컨테이너가 필요하지 않은 경우 선택은 vector입니다. 그것은 Sutter and Stroustrup의 권장 사항 이기도 합니다 .

---

Matthieu의 답변이 마음에 들지만 다음과 같이 순서도를 다시 설명하겠습니다.

std :: vector를 사용하지 않는 경우

기본적으로 컨테이너가 필요한 경우을 사용하십시오 std::vector. 따라서 다른 모든 컨테이너는에 대한 일부 대체 기능을 제공함으로써 정당화됩니다 std::vector.

생성자

std::vector항목을 뒤섞을 수 있어야하기 때문에 내용물은 움직일 수 있어야합니다. 이는 (주 기본 생성자가되는 내용에 대한 장소 끔찍한 부담하지 않습니다 필요하지 않습니다 에, 감사 emplace등). 그러나 대부분의 다른 컨테이너에는 특정 생성자가 필요하지 않습니다 (다시 감사합니다 emplace). 따라서 이동 생성자 를 절대 구현할 수없는 객체가 있으면 다른 것을 선택해야합니다.

A std::deque would be the general replacement, having many of the properties of std::vector, but you can only insert at either ends of the deque. Inserts in the middle require moving. A std::list places no requirement on its contents.

Needs Bools

std::vector<bool> is... not. Well, it is standard. But it's not a vector in the usual sense, as operations that std::vector normally allows are forbidden. And it most certainly does not contain bools.

Therefore, if you need real vector behavior from a container of bools, you're not going to get it from std::vector<bool>. So you'll have to make due with a std::deque<bool>.

Searching

If you need to find elements in a container, and the search tag can't just be an index, then you may need to abandon std::vector in favor of set and map. Note the key word "may"; a sorted std::vector is sometimes a reasonable alternative. Or Boost.Container's flat_set/map, which implements a sorted std::vector.

There are now four variations of these, each with their own needs.

• Use a map when the search tag is not the same thing as the item you're looking for itself. Otherwise use a set.
• Use unordered when you have a lot of items in the container and search performance absolutely needs to be O(1), rather than O(logn).
• Use multi if you need multiple items to have the same search tag.

Ordering

If you need a container of items to always be sorted based on a particular comparison operation, you can use a set. Or a multi_set if you need multiple items to have the same value.

Or you can use a sorted std::vector, but you'll have to keep it sorted.

Stability

When iterators and references are invalidated is sometimes a concern. If you need a list of items, such that you have iterators/pointers to those items in various other places, then std::vector's approach to invalidation may not be appropriate. Any insertion operation may cause invalidation, depending on the current size and capacity.

std::list offers a firm guarantee: an iterator and its associated references/pointers are only invalidated when the item itself is removed from the container. std::forward_list is there if memory is a serious concern.

If that's too strong a guarantee, std::deque offers a weaker but useful guarantee. Invalidation results from insertions in the middle, but insertions at the head or tail causes only invalidation of iterators, not pointers/references to items in the container.

Insertion Performance

std::vector only provides cheap insertion at the end (and even then, it becomes expensive if you blow capacity).

std::list is expensive in terms of performance (each newly inserted item costs a memory allocation), but it is consistent. It also offers the occasionally indispensable ability to shuffle items around for virtually no performance cost, as well as to trade items with other std::list containers of the same type at no loss of performance. If you need to shuffle things around a lot, use std::list.

std::deque provides constant-time insertion/removal at the head and tail, but insertion in the middle can be fairly expensive. So if you need to add/remove things from the front as well as the back, std::deque might be what you need.

It should be noted that, thanks to move semantics, std::vector insertion performance may not be as bad as it used to be. Some implementations implemented a form of move semantic-based item copying (the so-called "swaptimization"), but now that moving is part of the language, it's mandated by the standard.

No Dynamic Allocations

std::array is a fine container if you want the fewest possible dynamic allocations. It's just a wrapper around a C-array; this means that its size must be known at compile-time. If you can live with that, then use std::array.

That being said, using std::vector and reserveing a size would work just as well for a bounded std::vector. This way, the actual size can vary, and you only get one memory allocation (unless you blow the capacity).

---

Here is the C++11 version of the above flowchart. [originally posted without attribution to its original author, Mikael Persson]

---

Here's a quick spin, although it probably needs work

Should the container let you manage the order of the elements?
Yes:
  Will the container contain always exactly the same number of elements? 
  Yes:
    Does the container need a fast move operator?
    Yes: std::vector
    No: std::array
  No:
    Do you absolutely need stable iterators? (be certain!)
    Yes: boost::stable_vector (as a last case fallback, std::list)
    No: 
      Do inserts happen only at the ends?
      Yes: std::deque
      No: std::vector
No: 
  Are keys associated with Values?
  Yes:
    Do the keys need to be sorted?
    Yes: 
      Are there more than one value per key?
      Yes: boost::flat_map (as a last case fallback, std::map)
      No: boost::flat_multimap (as a last case fallback, std::map)
    No:
      Are there more than one value per key?
      Yes: std::unordered_multimap
      No: std::unordered_map
  No:
    Are elements read then removed in a certain order?
    Yes:
      Order is:
      Ordered by element: std::priority_queue
      First in First out: std::queue
      First in Last out: std::stack
      Other: Custom based on std::vector????? 
    No:
      Should the elements be sorted by value?
      Yes: boost::flat_set
      No: std::vector

You may notice that this differs wildly from the C++03 version, primarily due to the fact that I really do not like linked nodes. The linked node containers can usually be beat in performance by a non-linked container, except in a few rare situations. If you don't know what those situations are, and have access to boost, don't use linked node containers. (std::list, std::slist, std::map, std::multimap, std::set, std::multiset). This list focuses mostly on small and middle sided containers, because (A) that's 99.99% of what we deal with in code, and (B) Large numbers of elements need custom algorithms, not different containers.

참고URL : https://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11