현재 std::map<std::string,int>고유 한 문자열 식별자에 정수 값을 저장하는이 있으며 문자열을 검색합니다. 게재 신청서를 추적하지 않는다는 점을 제외하면 대부분 내가 원하는 작업을 수행합니다. 따라서 맵을 반복하여 값을 출력하면 문자열에 따라 정렬됩니다. 하지만 (첫 번째) 삽입 순서에 따라 정렬되기를 바랍니다.
vector<pair<string,int>>대신 a 를 사용하려고 생각 했지만 문자열을 찾아서 정수 값을 약 10,000,000 번 늘려야하므로 a std::vector가 상당히 느려질 지 여부를 알 수 없습니다 .
사용 방법이 있습니까, std::map아니면 std제 필요에 더 적합한 다른 용기가 있습니까?
[저는 GCC 3.4를 사용 중이며 아마도 내 값이 50 쌍 이하일 것 std::map입니다.].
감사.
답변
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<string_tag>, member<value_t, string, &value_t::s> >
>
> values_t;답변
a std::vector와 std::tr1::unordered_map(해시 테이블)을 결합 할 수 있습니다 . 여기에 링크의 부스트의 문서 에 대한이 unordered_map. 벡터를 사용하여 삽입 순서를 추적하고 해시 테이블을 사용하여 빈번한 조회를 수행 할 수 있습니다. 수십만 조회를 수행 std::map하는 경우 해시 테이블에 대한 O (log n) 조회 와 O (1)의 차이가 클 수 있습니다.
std::vector<std::string> insertOrder;
std::tr1::unordered_map<std::string, long> 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';
}답변
평행을 유지하십시오 list<string> insertionOrder.
인쇄 할 시간이되면 목록을 반복 하고 지도를 조회합니다 .
each element in insertionOrder // walks in insertionOrder..
print map[ element ].second // but lookup is in map답변
Tessil은 MIT 라이센스 인 주문형 맵 (및 세트)을 매우 훌륭하게 구현했습니다. 여기에서 찾을 수 있습니다 : ordered-map
지도 예
#include <iostream>
#include <string>
#include <cstdlib>
#include "ordered_map.h"
int main() {
tsl::ordered_map<char, int> 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;
}
}답변
두 조회 전략이 모두 필요한 경우 두 개의 컨테이너로 끝납니다. vector실제 값 ( ints) 과 함께 a 를 사용 하고map< string, vector< T >::difference_type> 옆 인덱스를 벡터에 반환 할 수 있습니다.
이 모든 것을 완료하려면 두 가지를 하나의 클래스로 캡슐화 할 수 있습니다.
답변
당신이 원하는 것은 (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<int> 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<int> TempHash(47, Key1, Key2);
CubicleSoft::OrderedHashNode<int> *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와 같은 것이 이미 존재하는지 확인했습니다. 나는 실망 했어. 그래서 직접 썼습니다. 그리고 지금 나는 그것을 공유했습니다.
답변
맵으로는 그렇게 할 수 없지만 맵과 벡터라는 두 개의 개별 구조를 사용하여 동기화 된 상태로 유지할 수 있습니다. 즉, 맵에서 삭제하고 벡터에서 요소를 찾아서 삭제할 수 있습니다. 또는 map<string, pair<int,int>>-를 만들고 쌍에 삽입시지도의 size ()를 int의 값과 함께 위치를 기록하고 인쇄 할 때 위치 멤버를 사용하여 정렬 할 수 있습니다.