인덱싱 된 주문형지도 만들기

Question

나는 지난 며칠 동안 이곳을 돌아 다니며 비슷한 사이트를 둘러 보았고 많은 시간을 들여 해결책을 찾았으며 조언을 구하고 싶습니다.

저는 C++의 라이브러리를 향상시키지 않으면 인덱싱 된 순서를 유지하는 연관 컨테이너를 만들 수 없다는 실망스러운 결론에 도달했습니다.

좀 더 명확하고 구체적으로 내가 필요로하는 것은 연산자 [key]를 사용하여 검색 할 수 있지만 반복 목적으로 요소가 추가 된 순서로 색인이 생성되는지도입니다.

나는 오늘 아침에 내가 직접 써야 할 필요가 있다고 결정했다.지도와지도 쌍 벡터지도를 사용하여 몇 가지 접근법을 시도했다. 그러나 실제로는 아무 것도 실제로 작동하지 않았으며 내가 찾고있는 모든 기능을 사용하고있다. 놀랍게도이 언어로는 쉽게 달성 할 수 없습니다. 필자는 잘못 됐어? 다른 사람이이 기능을 필요로하거나이 개념을 잘 알고있는 경험이 있었기 때문에 내가 찾는 대상의 올바른 방향으로 나를 가리킬 수 있습니까?

미리 감사드립니다. 모두 새해 복 많이 받으세요.

Answer 1

경고 : 이것은 입니다. 거친 모형을 원하는 동작으로 처리했습니다. 이것은 좋은 코드에 가깝지는 않지만 빠른 속도이며이를 수행하는 기술을 보여 주어야합니다.

자신의 롤링을 고려하기 전에 Boost의 multi_index과 같은 기존 솔루션을 사용해야합니다. 더 쉽고, 빠르며, 오류가 발생하기 쉽고, 더 잘 설계 될 것입니다.

template<typename Key, typename Val> 
class OrderedMap 
{ 
private: 
    std::vector<std::pair<Key, Val>> ordered; 
    std::map<Key, std::size_t> lookup; 

public: 
    void insert(Key k, Val v) 
    { 
     ordered.push_back(std::pair<Key, Val>(k, v)); 
     lookup.emplace(k, ordered.size() - 1); 
    } 

    Val find(Key k) 
    { 
     std::size_t index = lookup[k]; 
     return ordered[index].second; 
    } 
    // "typename" needed as the "iterator" is a dependent type 
    typename std::vector<std::pair<Key, Val>>::iterator begin() 
    { 
     return ordered.begin(); 
    } 
    typename std::vector<std::pair<Key, Val>>::iterator end() 
    { 
     return ordered.end(); 
    } 
}; 

---

우리가 필요한 것은 삽입 된 요소의 실제 순서를 추적하는 std::vector<std::pair<Key, Val>>이며, std::map<Key, std::size_t> 키와 값 인덱스 간의 연관성을 추적하도록. 그런 다음이 클래스에서 원하는 기능을 이러한 내부 백업/조회 구조의 기능에 위임 할 수 있습니다.

이 클래스가 원하는 동작과 내부 컨테이너 사이에서 제공하는 인터페이스는 사용자가 원하는대로 견고 할 수 있습니다. 여기서는 데모에 필요한 못생긴 뼈만 잡아 먹었습니다.

---

See a quick demo here.

OrderedMap<std::string, int> m; 
m.insert("1", 1); 
m.insert("2", 2); 
m.insert("3", 3); 

std::cout << m.find("2") << std::endl << std::endl; 

for (auto i = m.begin(); i != m.end(); i++) 
    std::cout << i->first << " " << i->second << std::endl; 
std::cout << std::endl; 

출력 나타냅니다 :

물론

2 

1 1 
2 2 
3 3