개발/C++

삽입 순서를 추적하는 std :: map?

MinorMan 2020. 9. 24. 00:37
반응형

<질문>

현재 std :: map이 있습니다. 고유 한 문자열 식별자에 정수 값을 저장하고 문자열을 검색합니다. 게재 신청서를 추적하지 않는다는 점을 제외하면 대부분 내가 원하는 작업을 수행합니다. 따라서 맵을 반복하여 값을 출력하면 문자열에 따라 정렬됩니다. 하지만 (첫 번째) 삽입 순서에 따라 정렬되기를 바랍니다.

나는 벡터를 사용하는 것에 대해 생각했다 > 대신 문자열을 찾고 정수 값을 약 10,000,000 번 증가시켜야하므로 std :: vector가 상당히 느릴 지 여부를 알 수 없습니다.

std :: map을 사용하는 방법이 있습니까 아니면 내 필요에 더 적합한 다른 표준 컨테이너가 있습니까?

[저는 GCC 3.4를 사용하고 있으며 std :: map에 50 쌍 이하의 값이있을 것입니다.]

감사.

<답변1>

std :: map에 50 개의 값만있는 경우 인쇄하기 전에 std :: vector에 복사하고 적절한 functor를 사용하여 std :: sort를 통해 정렬 할 수 있습니다.

또는 boost :: multi_index를 사용할 수 있습니다. 여러 인덱스를 사용할 수 있습니다. 귀하의 경우 다음과 같이 보일 수 있습니다.

struct value_t {
      string s;
      int    i;
};
struct string_tag {};
typedef multi_index_container<
    value_t,
    indexed_by<
        random_access<>, // this index represents insertion order
        hashed_unique< tag, member >
    >
> values_t;

<답변2>

std :: vector를 std :: tr1 :: unordered_map (해시 테이블)과 결합 할 수 있습니다. 다음은 unorder_map에 대한 Boost의 문서 링크입니다. 벡터를 사용하여 삽입 순서를 추적하고 해시 테이블을 사용하여 빈번한 조회를 수행 할 수 있습니다. 수십만 조회를 수행하는 경우 std :: map에 대한 O (log n) 조회와 해시 테이블에 대한 O (1) 간의 차이가 클 수 있습니다.

std::vector insertOrder;
std::tr1::unordered_map myTable;

// Initialize the hash table and record insert order.
myTable["foo"] = 0;
insertOrder.push_back("foo");
myTable["bar"] = 0;
insertOrder.push_back("bar");
myTable["baz"] = 0;
insertOrder.push_back("baz");

/* Increment things in myTable 100000 times */

// Print the final results.
for (int i = 0; i < insertOrder.size(); ++i)
{
    const std::string &s = insertOrder[i];
    std::cout << s << ' ' << myTable[s] << '\n';
}

<답변3>

병렬 목록 유지 insertionOrder.

인쇄 할 때가되면 목록을 반복하고지도를 조회합니다.

each element in insertionOrder  // walks in insertionOrder..
    print map[ element ].second // but lookup is in map

<답변4>

Tessil은 MIT 라이센스 인 주문형 맵 (및 세트)을 매우 훌륭하게 구현했습니다. 여기에서 찾을 수 있습니다 : ordered-map

지도 예

#include 
#include 
#include 
#include "ordered_map.h"

int main() {
tsl::ordered_map map = {{'d', 1}, {'a', 2}, {'g', 3}};
map.insert({'b', 4});
map['h'] = 5;
map['e'] = 6;

map.erase('a');


// {d, 1} {g, 3} {b, 4} {h, 5} {e, 6}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}


map.unordered_erase('b');

// Break order: {d, 1} {g, 3} {e, 6} {h, 5}
for(const auto& key_value : map) {
    std::cout << "{" << key_value.first << ", " << key_value.second << "}" << std::endl;
}
}

<답변5>

두 조회 전략이 모두 필요한 경우 두 개의 컨테이너로 끝납니다. 실제 값 (ints)이있는 벡터를 사용하고 그 옆에 map <string, vector <T> :: difference_type>을 배치하여 인덱스를 벡터에 반환 할 수 있습니다.

이 모든 것을 완료하려면 두 가지를 하나의 클래스로 캡슐화 할 수 있습니다.

하지만 부스트에는 여러 인덱스가있는 컨테이너가 있다고 생각합니다.

<답변6>

원하는 것은 (Boost에 의지하지 않고) 내가 "순서화 된 해시"라고 부르는 것인데, 이것은 본질적으로 해시와 문자열 또는 정수 키가있는 연결 목록 (또는 동시에 둘 다)의 매시업입니다. 정렬 된 해시는 해시의 절대 성능으로 반복하는 동안 요소의 순서를 유지합니다.

저는 C ++ 라이브러리 개발자를위한 C ++ 언어의 허점으로 보는 것을 채우는 비교적 새로운 C ++ 스 니펫 라이브러리를 모았습니다. 여기로 가십시오 :

https://github.com/cubiclesoft/cross-platform-cpp

붙잡다:

templates/detachable_ordered_hash.cpp
templates/detachable_ordered_hash.h
templates/detachable_ordered_hash_util.h

사용자 제어 데이터가 해시에 배치되는 경우 다음을 원할 수도 있습니다.

security/security_csprng.cpp
security/security_csprng.h

그것을 호출하십시오 :

#include "templates/detachable_ordered_hash.h"
...
// The 47 is the nearest prime to a power of two
// that is close to your data size.
//
// If your brain hurts, just use the lookup table
// in 'detachable_ordered_hash.cpp'.
//
// If you don't care about some minimal memory thrashing,
// just use a value of 3.  It'll auto-resize itself.
int y;
CubicleSoft::OrderedHash TempHash(47);
// If you need a secure hash (many hashes are vulnerable
// to DoS attacks), pass in two randomly selected 64-bit
// integer keys.  Construct with CSPRNG.
// CubicleSoft::OrderedHash TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode *Node;
...
// Push() for string keys takes a pointer to the string,
// its length, and the value to store.  The new node is
// pushed onto the end of the linked list and wherever it
// goes in the hash.
y = 80;
TempHash.Push("key1", 5, y++);
TempHash.Push("key22", 6, y++);
TempHash.Push("key3", 5, y++);
// Adding an integer key into the same hash just for kicks.
TempHash.Push(12345, y++);
...
// Finding a node and modifying its value.
Node = TempHash.Find("key1", 5);
Node->Value = y++;
...
Node = TempHash.FirstList();
while (Node != NULL)
{
  if (Node->GetStrKey())  printf("%s => %d\n", Node->GetStrKey(), Node->Value);
  else  printf("%d => %d\n", (int)Node->GetIntKey(), Node->Value);

  Node = Node->NextList();
}

나는 연구 단계 에서이 SO 스레드를 만져서 대량 라이브러리에 들일 필요없이 OrderedHash와 같은 것이 이미 존재하는지 확인했습니다. 나는 실망 했어. 그래서 직접 썼습니다. 그리고 지금 나는 그것을 공유했습니다.

<답변7>

맵으로는 그렇게 할 수 없지만 맵과 벡터라는 두 개의 개별 구조를 사용하여 동기화 된 상태로 유지할 수 있습니다. 즉, 맵에서 삭제하고 벡터에서 요소를 찾아서 삭제할 수 있습니다. 또는지도를 만들 수 있습니다. >-그리고 당신의 쌍에 int의 값과 함께 위치를 기록하기 위해 삽입 할 때 맵의 size ()를 저장하고 인쇄 할 때 위치 멤버를 사용하여 정렬하십시오.

<답변8>

이를 구현하는 또 다른 방법은 벡터 대신지도를 사용하는 것입니다. 이 접근 방식을 보여주고 차이점에 대해 논의하겠습니다.

배후에 두 개의 맵이있는 클래스를 만드십시오.

#include 
#include 

using namespace std;

class SpecialMap {
  // usual stuff...

 private:
  int counter_;
  map insertion_order_;
  map data_;
};

그런 다음 적절한 순서로 data_를 통해 반복기를 반복기에 노출 할 수 있습니다. 이를 수행하는 방법은 insertion_order_를 반복하고 해당 반복에서 얻은 각 요소에 대해 insertion_order_의 값으로 data_에서 조회를 수행하는 것입니다.

insertion_order_를 직접 반복하는 것을 신경 쓰지 않기 때문에 insertion_order에 더 효율적인 hash_map을 사용할 수 있습니다.

삽입하려면 다음과 같은 방법을 사용할 수 있습니다.

void SpecialMap::Insert(const string& key, int value) {
  // This may be an over simplification... You ought to check
  // if you are overwriting a value in data_ so that you can update
  // insertion_order_ accordingly
  insertion_order_[counter_++] = key;
  data_[key] = value;
}

디자인을 더 좋게 만들고 성능에 대해 걱정할 수있는 많은 방법이 있지만이 기능을 직접 구현할 수있는 좋은 스켈레톤입니다. 템플릿으로 만들 수 있으며, 실제로 insert_order_의 항목을 쉽게 참조 할 수 있도록 data_에 값으로 쌍을 저장할 수 있습니다. 그러나 나는 이러한 디자인 문제를 연습으로 남겨 둡니다. :-).

업데이트 : insert_order_에 대한 맵 대 벡터 사용의 효율성에 대해 말해야한다고 생각합니다.

  • 데이터를 직접 조회합니다. 두 경우 모두 O (1)
  • 벡터 접근 방식의 삽입은 O (1), 맵 접근 방식의 삽입은 O (logn)
  • 벡터 접근법에서 삭제는 제거 할 항목을 스캔해야하기 때문에 O (n)입니다. 맵 접근 방식에서는 O (logn)입니다.

삭제를 많이 사용하지 않으려면 벡터 접근 방식을 사용해야합니다. 게재 순서 대신 다른 순서 (예 : 우선 순위)를 지원하는 경우지도 접근 방식이 더 좋습니다.

<답변9>

다음은 boost의 멀티 인덱스를 사용하지 않고 표준 템플릿 라이브러리 만 필요한 솔루션입니다. std :: map을 사용할 수 있습니다. ; 및 벡터 ; 지도에서 데이터 위치의 인덱스를 벡터에 저장하고 벡터는 삽입 순서로 데이터를 저장합니다. 여기서 데이터에 대한 액세스는 O (log n) 복잡도를 갖습니다. 삽입 순서로 데이터를 표시하는 데는 O (n) 복잡성이 있습니다. 데이터 삽입은 O (log n) 복잡도를 갖습니다.

예를 들면 :

#include
#include
#include

struct data{
int value;
std::string s;
}

typedef std::map MapIndex;//this map stores the index of data stored 
                                           //in VectorData mapped to a string              
typedef std::vector VectorData;//stores the data in insertion order

void display_data_according_insertion_order(VectorData vectorData){
    for(std::vector::iterator it=vectorData.begin();it!=vectorData.end();it++){
        std::cout<value<s<second;
    else return -1;//it signifies that key does not exist in map
}
int insert_value(data d,mapIndex,vectorData){
    if(mapIndex.find(d.s)==mapIndex.end()){
        mapIndex.insert(std::make_pair(d.s,vectorData.size()));//as the data is to be
                                                               //inserted at back 
                                                               //therefore index is
                                                               //size of vector before
                                                               //insertion
        vectorData.push_back(d);
        return 1;
    }
    else return 0;//it signifies that insertion of data is failed due to the presence
                  //string in the map and map stores unique keys
}

<답변10>

이것은 Faisals 답변과 다소 관련이 있습니다. 지도와 벡터 주위에 래퍼 클래스를 만들고 쉽게 동기화 할 수 있습니다. 적절한 캡슐화를 통해 액세스 방법을 제어 할 수 있으므로 사용할 컨테이너 (벡터 또는지도)를 사용할 수 있습니다. 이것은 Boost 또는 이와 유사한 것을 사용하지 않습니다.

<답변11>

고려해야 할 한 가지는 사용중인 데이터 요소의 수가 적다는 것입니다. 벡터 만 사용하는 것이 더 빠를 수 있습니다. 맵에 약간의 오버 헤드가있어 단순한 벡터보다 작은 데이터 세트에서 조회하는 데 더 많은 비용이들 수 있습니다. 따라서 항상 동일한 수의 요소를 사용한다는 것을 알고 있다면 몇 가지 벤치마킹을 수행하고 맵과 벡터의 성능이 실제로 생각하는 것과 같은지 확인하십시오. 50 개의 요소 만있는 벡터에서 조회가지도와 거의 동일하다는 것을 알 수 있습니다.

<답변12>

//이 남자와 같아야합니다!

// 삽입의 복잡성이 O (logN)이고 삭제도 O (logN)임을 유지합니다.

class SpecialMap {
private:
  int counter_;
  map insertion_order_;
  map insertion_order_reverse_look_up; // <- for fast delete
  map data_;
};

<답변13>

map 및 list 인덱스와 함께 boost :: multi_index를 사용합니다.

<답변14>

삽입 호출시 증가하는 쌍 (str, int) 및 정적 int의 맵은 데이터 쌍을 색인화합니다. 인덱스 () 멤버와 함께 정적 int val을 반환 할 수있는 구조체를 넣으십시오.

반응형

'개발 > C++' 카테고리의 다른 글

Qt Creator 프로젝트에 외부 라이브러리 추가  (0) 2020.09.24
C ++ 템플릿 Turing-complete?  (0) 2020.09.24
C ++ 맵 액세스가 한정자를 버림 (const)  (0) 2020.09.24
libpng 경고 : iCCP : 알려진 잘못된 sRGB 프로필  (0) 2020.09.24

'개발/C++'의 다른글

  • 현재글삽입 순서를 추적하는 std :: map?

관련글

티스토리툴바