값이 업데이트 될 때마다 맵을 표시합니다.

Question

기본적으로

map<std::string, int> 

• foo 5
• 막대 10
• 잭 3

지도에 표시하고 싶습니다. (역순으로 주목하십시오)

• 바 10
• foo 5
• 잭 3

그리고 업데이트 될 때마다 필자는 모든 요소를 ​​반복하여 값. 이를 구현하는 좋은 방법은 무엇입니까? 생성자에 비교자를 제공해야합니까?

맵의 값이 최소 1 억 번 업데이트되므로 효율성이 중요합니다. 추가 공간이 문제가되지 않는 경우

부스트 솔루션을 부탁드립니다 ... thx

Answer 1

struct keyval_t { std::string key; int val; }; 
int operator<(const keyval_t &a, const ketval_t &b) 
{ return a.val<b.val || (a.val==b.val && a.key<b.key); } 

은 그럼 당신은 하나 개의 맵과 한 세트가 필요합니다. 인쇄 할 때 세트를 반복하면됩니다. 이론적 인 시간 복잡도의 관점에서 보면 이것이 최적입니다. 그것은 기억을 두 배로 늘린다. 이것이 당신의 목표를 충족 시키는가? 카운터, 카운터 뭔가 어디 | (uint64_t) 발 < < 32 :

이

map<std::string,uint64_t>; set<uint64_t>; 

(또한 세트의 키)지도의 값은 다음과 같습니다

메모리를 줄이기 위해, 당신은 다음 고려할 수 있습니다 동일한 값을 구별합니다. 예를 들어 키를 삽입 할 때마다 카운터를 1 씩 늘립니다. 값을 업데이트 할 때 카운터를 업데이트 할 필요가 없습니다. uint64_t가 마음에 들지 않으면 대신 < int, int > 쌍을 사용하십시오. 이 솔루션은 문자열 간의 비교를 피하기 때문에 더 빠릅니다.

Answer 2

글쎄, 당신은 열쇠로 정렬해야합니다. "값순으로 정렬"하는 가장 쉬운 방법은 키와 값을 전환 한 상태로 멀티 맵을 사용하는 것입니다. 그래서 여기에 할 수있는 방법이다 (참고 -이 컴파일되지 않습니다 그래서 만약 내가 지금 컴파일러에 액세스 할 수없는, 미안 해요) :

#include <algorithm> 
#include <functional> 
#include <map> 
#include <string> 
#include <utility> 

typedef std::multimap<int, std::string, std::greater<int> > MapType; 
struct MapKeyOutput 
{ 
    void operator()(const MapType::value_type& val) 
    { 
     std::cout << val.second << " " << val.first << "\n"; 
    } 
} 

void display_insert(MapType& m, const std::string& str, int val) 
{ 
    m.insert(std::make_pair(val, str)); 
    std::for_each(m.begin(), m.end(), MapKeyOutput()); 
} 

int main() 
{ 
    MapType m; 
    display_insert(m, "Billy", 5); 
    display_insert(m, "Johnny", 10); 
} 

또한지도를 만들 수 내부적으로 멀티 맵을 사용하는 클래스는 입력하기를 원하지 않았습니다. 그러면 display_insert가 대신 일부 멤버 함수가됩니다. 이 점을 설명해야합니다. 관심 지점 :

typedef std::multimap<int, std::string, std::greater<int> > MapType; 

비교기는 내림차순으로 정렬하려면 greater<int>입니다. 우리는 하나 이상의 이름이 같은 번호를 가질 수 있도록 멀티 맵을 사용하고 있습니다.

struct MapKeyOutput 
{ 
    void operator()(const MapType::value_type& val) 
    { 
     std::cout << val.second << " " << val.first << "\n"; 
    } 
} 

지도에서 하나의 요소를 출력하는 함수 객체입니다. 두 번째는 먼저 출력되기 때문에 순서는 원하는 것입니다.

std::for_each(m.begin(), m.end(), MapKeyOutput()); 

이렇게하면 m의 모든 요소에 함수 객체가 적용됩니다.

Answer 3

이전 응답에는 초기 요구 사항 (키는 std :: string이고 값은 int 임)을 고려하지 않아도된다는 불편 함이 있습니다.

편집 : 코멘트에 따라, 나는 :)

그래서 여기에 우리가 오른쪽, 이동 더 나은 Bimap에 직접 제시하는 것은 가정!

#include <boost/bimap.hpp> 

class MyMap 
{ 
    struct name {}; 
    struct value {}; 

    typedef boost::tagged<name, std::string> tagged_name; 
    typedef boost::tagged<value, int> tagged_value; 

    // unordered_set_of: guarantees only unicity (not order) 
    // multi_set_of: guarantees only order (not unicity) 
    typedef boost::bimap< boost::unordered_set_of<tagged_name>, 
         boost::multi_set_of< tagged_value, 
              std::greater<tagged_value> 
              > 
         > impl_type; 
public: 
    // Redefine all usual types here 
    typedef typename impl_type::map_by<name>::const_iterator const_iterator; 
    typedef typename impl_type::value_type value_type; 


    // Define the functions you want 
    // the bimap will not allow mutators because the elements are used as keys 
    // so you may want to add wrappers 

    std::pair< iterator, bool > insert(const value_type & x) 
    { 
    std::pair< iterator, bool > result = m_impl.insert(x); 
    if (result.second) this->display(); 
    return result; 
    } // insert 

    iterator insert(iterator position, const value_type & x) 
    { 
    iterator result = m_impl.insert(x); 
    this->display(); 
    return result; 
    } // insert 

    template< class InputIterator > 
    void insert(InputIterator first, InputIterator last) 
    { 
    m_impl.insert(first, last); 
    this->display(); 
    } // insert 

private: 
    void display() const 
    { 
    // Yeah I know about std::for_each... 
    typedef typename impl_type::map_by<value>::const_iterator const_it; 

    for (const_it it = m_impl.begin(), end = m_impl.end(); it != end; ++it) 
    { 
     // Note the inversion of the 'second' and 'first', 
     // we are looking at it from the right 
     std::cout << it->second << " " << it->first << std::endl; 
    } 
    } 

    impl_type m_impl; 
}; // class MyMap 

여기 있습니다.

필자는 bimap 설명서를 참고할 것을 강력히 제안합니다.저장 (set_of, unordered_set_of, unconstrained_set_of, 다중 변형, list_of 변형 ...)에 대한 많은 가능성이 있으므로 원하는 것을 할 수있는 가능성이 있습니다.

그런 다음 당신은 또한 당신이 표시마다 분류 할 수있을 :

#include <set> 
#include <map> 

// Just use a simple std::map<std::string,int> for your impl_type 
// Mutators are allowed since the elements are sorted each time you display 

struct Comparator 
{ 
    bool operator(const value_type& lhs, const value_type& rhs) const 
    { 
    return lhs.second < rhs.value; 
    } 
}; 

void display() const 
{ 
    typedef std::multi_set<value_type, Comparator> sort_type; 
    sort_type mySet; 

    std::copy(m_impl.begin(), m_impl.end(), std::inserter(mySet, mySet.end())); 

    for (sort_type it = mySet.begin(), end = mySet.end(); it != end; ++it) 
    { 
    std::cout << it->first<< " " << it->second << std::endl; 
    } 
} 

지금 내 점을 이해 :)

Answer 4

을 둘 다 키에 의해 정렬 된 성능이 좋은지도를 원하는 경우에 쉽게해야한다 및 값을 원하는 경우 Boost MultiIndex을 원할 때마다 수동으로 수행해야하는 모든 업데이트에서 업데이트되고 (재검토 됨) 좋은 설명서가 제공됩니다.

map<std::string, int>; set<keyval_t>; 

갱신에, 당신은 키 - 값 쌍을 결정하기 위해 먼저지도를 검색하고지도와 설정을 모두 업데이트해야합니다