tessil / ordered-map Goto Github PK
View Code? Open in Web Editor NEWC++ hash map and hash set which preserve the order of insertion
License: MIT License
C++ hash map and hash set which preserve the order of insertion
License: MIT License
This works:
tsl::ordered_map<int, int> map = { {0, 2}, {1, 3} };
tsl::ordered_map<int, int> map2 = { map.begin(), map.end() };
but these do not:
tsl::ordered_map<int, int> map = { {0, 2}, {1, 3} };
tsl::ordered_map<int, int> map2 = { map.cbegin(), map.cend() };
const tsl::ordered_map<int, int> map = { {0, 2}, {1, 3} };
tsl::ordered_map<int, int> map2 = { map.begin(), map.end() };
Tested under VS 2017 15.9.7. Here's the wall of text from the compiler in case you can't reproduce the issue:
ordered_map.h(280): error C2668: 'tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::KeySelect,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::insert': ambiguous call to overloaded function
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
Hash=std::hash<int>,
KeyEqual=std::equal_to<int>,
ValueTypeContainer=std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,
IndexType=uint_least32_t
]
ordered_hash.h(562): note: could be 'void tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::KeySelect,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::insert<InputIt>(InputIt,InputIt)'
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
Hash=std::hash<int>,
KeyEqual=std::equal_to<int>,
ValueTypeContainer=std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,
IndexType=uint_least32_t,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
c:\users\bo anderson\documents\repositories\bpvault\deps\ordered-map\include\tsl\ordered_hash.h(553): note: or 'tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::KeySelect,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ordered_iterator<false> tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::KeySelect,tsl::ordered_map<Key,T,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::insert<InputIt&>(tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::KeySelect,tsl::ordered_map<Key,T,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ordered_iterator<true>,P)'
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
Hash=std::hash<int>,
KeyEqual=std::equal_to<int>,
ValueTypeContainer=std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,
IndexType=uint_least32_t,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>,
P=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true> &
]
ordered_map.h(280): note: while trying to match the argument list '(InputIt, InputIt)'
with
[
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
ordered_map.h(167): note: see reference to function template instantiation 'void tsl::ordered_map<int,int,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::insert<InputIt>(InputIt,InputIt)' being compiled
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
ordered_map.h(167): note: see reference to function template instantiation 'void tsl::ordered_map<int,int,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::insert<InputIt>(InputIt,InputIt)' being compiled
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
test.cpp(419): note: see reference to function template instantiation 'tsl::ordered_map<int,int,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ordered_map<tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::KeySelect,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ordered_iterator<true>>(InputIt,InputIt,unsigned __int64,const Hash &,const KeyEqual &,const Allocator &)' being compiled
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
Hash=std::hash<int>,
KeyEqual=std::equal_to<int>,
ValueTypeContainer=std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,
IndexType=uint_least32_t,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
test.cpp(419): note: see reference to function template instantiation 'tsl::ordered_map<int,int,std::hash<int>,std::equal_to<Key>,std::allocator<std::pair<Key,T>>,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ordered_map<tsl::detail_ordered_hash::ordered_hash<std::pair<Key,T>,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::KeySelect,tsl::ordered_map<Key,T,std::hash<int>,std::equal_to<Key>,Allocator,std::deque<std::pair<Key,T>,Allocator>,uint_least32_t>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer,IndexType>::ordered_iterator<true>>(InputIt,InputIt,unsigned __int64,const Hash &,const KeyEqual &,const Allocator &)' being compiled
with
[
Key=int,
T=int,
Allocator=std::allocator<std::pair<int,int>>,
Hash=std::hash<int>,
KeyEqual=std::equal_to<int>,
ValueTypeContainer=std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,
IndexType=uint_least32_t,
InputIt=tsl::detail_ordered_hash::ordered_hash<std::pair<int,int>,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::KeySelect,tsl::ordered_map<int,int,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ValueSelect,std::hash<int>,std::equal_to<int>,std::allocator<std::pair<int,int>>,std::deque<std::pair<int,int>,std::allocator<std::pair<int,int>>>,uint_least32_t>::ordered_iterator<true>
]
Both std::map
and std::unordered_map
seem to work fine under this case.
Hi! Thank you for your numerous contributions, @Tessil !!
I know you are familiarized with nlohmann/json and Tessil/ordered-map interaction:
I need a ordered json and i am using your way. I have test this code in MinGW gcc 7.30 and it works!
This sample is the adaptacion of nlohmann/json sample to Tessil/ordered-map, I tried to follow your instruction. Sorry for my inexperience. :-|
#include <string>
#include <iostream>
#include <nlohmann/json.hpp>
#include <tsl/ordered_map.h>
#include <tsl/ordered_set.h>
template<class Key, class T, class Ignore, class Allocator,
class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
using ordered_map = tsl::ordered_map<Key, T, Hash, KeyEqual,
typename std::allocator_traits<Allocator>::template
rebind_alloc<std::pair<Key, T>>>;
using json = nlohmann::basic_json<ordered_map>; //It only works in MinGW 7.3.0 (the json is ordered :-))
//using json = nlohmann::json; //It works in MSVC2017 and MinGW 7.3.0
namespace ns {
// a simple struct to model a person
struct person {
std::string name;
std::string address;
int age;
};
//}
//namespace ns {
void to_json(json& j, const person& p) {
j = json{ { "name", p.name },{ "address", p.address },{ "age", p.age } };
}
void from_json(const json& j, person& p) {
p.name = j.at("name").get<std::string>();
p.address = j.at("address").get<std::string>();
p.age = j.at("age").get<int>();
}
} // namespace ns
int main()
{
// create a person
ns::person p{ "Ned Flanders", "744 Evergreen Terrace", 60 };
// conversion: person -> json
json j = p;
std::cout << j << std::endl;
// {"address":"744 Evergreen Terrace","age":60,"name":"Ned Flanders"}
// conversion: json -> person
ns::person p2 = j;
// that's it
//assert(p == p2);
}
I get the next error in Visual Studio 2017( 15.7.1 )
(Windows 10 x64)
1>------ Build started: Project: prueba, Configuration: Debug x64 ------
1>main.cpp
1>c:\program files (x86)\microsoft visual studio\2017\enterprise\vc\tools\msvc\14.14.26428\include\utility(293): error C2079: 'std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>::second' uses undefined class 'nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>'
1> with
1> [
1> StringType=std::string
1> ]
1>c:\program files (x86)\microsoft visual studio\2017\enterprise\vc\tools\msvc\14.14.26428\include\deque(967): note: see reference to class template instantiation 'std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>' being compiled
1> with
1> [
1> StringType=std::string
1> ]
1>p:\mis-proyectos\profesional\prueba\prueba\prueba\tsl\ordered_hash.h(215): note: see reference to class template instantiation 'std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>' being compiled
1> with
1> [
1> StringType=std::string,
1> Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>
1> ]
1>p:\mis-proyectos\profesional\prueba\prueba\prueba\tsl\ordered_map.h(106): note: see reference to class template instantiation 'tsl::detail_ordered_hash::ordered_hash<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,tsl::ordered_map<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,std::allocator<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>::KeySelect,tsl::ordered_map<Key,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,Allocator,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>::ValueSelect,Hash,KeyEqual,Allocator,ValueTypeContainer>' being compiled
1> with
1> [
1> StringType=std::string,
1> Key=std::string,
1> Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,
1> Hash=std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,
1> KeyEqual=std::equal_to<std::string>,
1> ValueTypeContainer=std::deque<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>>
1> ]
1>p:\mis-proyectos\profesional\prueba\prueba\prueba\nlohmann\json.hpp(12791): note: see reference to class template instantiation 'tsl::ordered_map<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>,std::hash<std::basic_string<char,std::char_traits<char>,std::allocator<char>>>,std::equal_to<Key>,std::allocator<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>,std::deque<std::pair<StringType,nlohmann::basic_json<ordered_map,std::vector,StringType,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>,Allocator>>' being compiled
1> with
1> [
1> StringType=std::string,
1> Key=std::string,
1> Allocator=std::allocator<std::pair<std::string,nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>>>
1> ]
1>p:\mis-proyectos\profesional\prueba\prueba\prueba\main.cpp(36): note: see reference to class template instantiation 'nlohmann::basic_json<ordered_map,std::vector,std::string,bool,int64_t,uint64_t,double,std::allocator,nlohmann::adl_serializer>' being compiled
1>Done building project "prueba.vcxproj" -- FAILED.
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========
Could you help me? Thanks!
DJuego
The below code is compiled just fine with previous version - when ordered_map, set, and hash are in the same file (ordered_map.h).
With latest library, the below code failed to compile if string is const
const tsl::ordered_map<int, const std::string> testmap{
{ 0, "Test1" },
{ 1, "Test2" },
};
The below code with no const compile just fine with latest library
const tsl::ordered_map<int, std::string> testmap{
{ 0, "Test1" },
{ 1, "Test2" },
};
Hi, the below codes cause the application to crash:
tsl::ordered_map<std::string, int32_t> m;
m["ABC"] = 1;
m["ccc"] = 2;
auto it = m.begin;
for (; it != m.end();)
{
m.erase(it++); // crashe
// it = m.erase(it); // this works fine
}
Doesn't ordered_map support the m.erase(it++); as well as the std::map?
Hello,
We are interesting in using your ordered map because it handle allocation better than standard std::map for very big data.
However, we do need lower_bound function in the map which seems not implemented. For now I'm not sure if I can use std::lower_bound over begin()/end() until there is one which seems to be extremely inefficient.
Do you plan to add this function? I'm not enough fluent with containers to propose a patch :(
Hello! Adding erase_if function would be great. Is it possible?
https://en.cppreference.com/w/cpp/container/map/erase_if
Dear developers of Tessil,
Would it be possible to add serialization functions or a way to get/set internal members for faster loading of map/set?
This is more of a question than an issue:
I have two tsl::ordered_map
objects with the same signature, e.g. tsl::ordered_map<std::string, std::shared_ptr<MyCustomType>>
I'd like to be able to find the intersection of common keys between them. When using a std::unordered_map
, I can use the ranges-v3 library to do this:
std::unordered_map<std::string, std::shared_ptr<MyCustomType>> = { {"key1", ...}, {"key2", ...} };
std::unordered_map<std::string, std::shared_ptr<MyCustomType>> = { {"key3", ...}, {"key2", ...} };
const auto common_keys =
ranges::views::set_intersection(cfg1 | ranges::views::keys, cfg2 | ranges::views::keys);
// common_keys will contain "key2"
When I do the same with a tsl::ordered_map
then common_keys
is empty. This makes sense per the readme indicating that insertion order matters for the equality operator. The question then is, how would I achieve the above?
$ ./test_ordered_map
libc++abi.dylib: terminating with uncaught exception of type boost::unit_test::framework::setup_error: test unit with name 'test_insert<tsl__ordered_map<long long, long long, std____1__hash<long long>, std____1__equal_to<long long>, std____1__allocator<std____1__pair<long long, long long> >, std____1__deque<std____1__pair<long long, long long>, std____1__allocator<std____1__pair<long long, long long> > > >>' registered multiple times
[1] 48387 abort ./test_ordered_map
Hi, thanks for this great library.
I realized iterator
doesn't have non-const variant of operator*()
, which is also explicitly stated in the README. value()
function is recommended instead, but it doesn't play well with range-loops where values need to be mutated.
Example code:
#include "tsl/ordered_map.h"
int main() {
tsl::ordered_map<int, int> m;
for (auto& v: m) {
int& value = v.second;
}
}
$ g++ --version
g++ (Debian 8.3.0-6) 8.3.0
Copyright (C) 2018 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ g++ -std=c++11 test.cpp -o test
test.cpp: In function ‘int main()’:
test.cpp:6:24: error: binding reference of type ‘int&’ to ‘const int’ discards qualifiers
int& value = v.second;
~~^~~~~~
Is there a specific reason for disallowing it or is it just that it's not implemented? Thanks.
Hi!
I'm using this project's ordered_map
. The values under the keys can change, but after the map is first populated, the keys always remain the same. In that situation, in a multithreaded program, is it safe to overwrite the value under one key from thread 1 while accessing another key from thread 2?
I took a look at https://tessil.github.io/ordered-map/classtsl_1_1ordered__map.html#details
insert, emplace, emplace_hint, operator[]: when a std::vector is used as ValueTypeContainer and if size() < capacity(), only end(). Otherwise all the iterators are invalidated if an insert occurs.
From that quote, is it correct that simply changing the value under one key isn't an "insertion" (as defined in something like cplusplus docs for std::unordered_map
: adding a new element to the map) and therefore even an ordered_map
using std::deque
isn't invalidating its iterators (and therefore, can access values under other keys from another thread safely)?
If my understanding is correct and you think it makes sense, I could try my hand at updating the docs to make them clearer on this point.
Cheers!
It's possible provide the value() method for reverse_iterator?
Thanks
Hello.
Whether it is possible to make that the library build with gcc flag: -fno-exceptions ?
Thank you.
The readme says it's possible to use the containers with std::vector
instead of std::deque
. However, after changing that in ordered_set.h
, the following code crashes under GCC 7.2.0, probably due to the strange specialization of std::vector<bool>
.
#include <iostream>
#include "include/tsl/ordered_set.h"
int main() {
tsl::ordered_set<bool> a;
a.insert(true);
tsl::ordered_set<bool> b;
b.insert(a.begin(), a.end());
std::cout << b.size() << std::endl;
}
There is also a warning:
lib/tsl/ordered_hash.h:387:43: warning: returning reference to temporary [-Wreturn-local-addr]
reference operator*() const { return *m_iterator; }
^~~~~~~~~~
A workaround is to keep std::deque
just for bool
.
class ValueTypeContainer = typename std::conditional<
std::is_same<Key, bool>::value,
typename std::deque<Key, Allocator>,
typename std::vector<Key, Allocator>>::type,
Is this the reason why std::deque
is used by default? I've found that std::vector
makes the containers somewhat faster (though they're much faster than the default unordered containers in STL anyway).
After clear() is called, nothing behave as it should be. My program even crashes sometimes.
Not sure if it also happens to ordered_map
tsl::ordered_set<int> test2;
test2.insert(6);
test2.clear();
test2.insert(104);
test2.insert(1099);
test2.insert(302);
test2.insert(208);
test2.insert(301);
test2.erase(301);
std::cout << "ordered_set: ";
for (auto & i : test2)
{
std::cout << i << " ";
}
std::cout <<"\n\n";
test2.erase(302);
test2.insert(302);
std::cout << "ordered_set: ";
for (auto & i : test2)
{
std::cout << i << " ";
}
std::cout <<"\n\n";
test2.erase(302);
test2.insert(302);
std::cout << "ordered_set: ";
for (auto & i : test2)
{
std::cout << i << " ";
}
std::cout <<"\n\n";
output:
ordered_set: 104 1099 302 208
ordered_set: 104 1099 302 208
ordered_set: 104 1099 302 208
ordered_set: 104 1099 302 208 301
should be:
ordered_set: 104 1099 302 208
ordered_set: 104 1099 208 302
ordered_set: 104 1099 208 302
ordered_set: 104 1099 208 301
From your documentation you have this:
For iterators, operator*() and operator->() return a reference and a pointer to const std::pair<Key, T> instead of std::pair<const Key, T> making the value T not modifiable. To modify the value you have to call the value() method of the iterator to get a mutable reference. Example:
Is this something that could be eliminated? I.e. the divergence between ordered_map and unordered_map? I have code that iterates over an unordered_map in parallel using std::for_each. I need to modify the T values but with ordered_map I can't do this because the callback provided to for_each receives the dereferenced iterator, i.e. I end up with a const std::pair<Key, T> and thus have no way of calling value to get a modifiable T.
It also pops up in using the ranged-for loops:
for(auto& foo : some_ordered_map)
foo here is again const std::pair<Key, T> and thus I can't possibly call value even if I wanted to, meaning I have to change all ranged-for loops to be the older, non-ranged style.
Hi,
I just discovered this project (and the related ones) and find it really cool! We are considering adopting it for the xframe project, in order to do that I need to package it for conda.
ordered-map
is a too much generic name, so I was thinking of tsl_ordered_map
, are you ok with that? Or do you prefer a different name?
Is there any reason for restricting it to 32 bit indexes?
Could 264 - 1 values be supported with just a trivial change?
in ordered_hash.h, the indexes are defined as 32 bit:
class bucket_entry
{
public:
using index_type = std::uint_least32_t;
using truncated_hash_type = std::uint_least32_t;
defining them as 64 bit would be:
using index_type = std::uint64_t;
using truncated_hash_type = std::uint64_t;
Besides additional memory usage, are there any implications of allowing 64 bit indexes?
I'm looking to serialize an ordered-map with boost_serialization
.
I have seen the below code for splitting into save and load, and using the serialize/deserialize methods of ordered_map, however being unfamiliar with lambdas I am not sure how to adapt this to work with C++11 or C++14.
template<class Archive, class Key, class T>
void serialize(Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int version) {
split_free(ar, map, version);
}
template<class Archive, class Key, class T>
void save(Archive & ar, const tsl::ordered_map<Key, T>& map, const unsigned int /*version*/) {
auto serializer = [&ar](const auto& v) { ar & v; };
map.serialize(serializer);
}
template<class Archive, class Key, class T>
void load(Archive & ar, tsl::ordered_map<Key, T>& map, const unsigned int /*version*/) {
auto deserializer = [&ar]<typename U>() { U u; ar & u; return u; };
map = tsl::ordered_map<Key, T>::deserialize(deserializer);
}
How would this be done without using templated parameters in the deserializer lambda?
Hi, I just found two issues related to the operators + of the iterator.
The first one is, the n + iterator
operator is missing, which is required in a random-access iterator. More specifically, this operator override is missing: ordered_iterator operator+(difference_type, const ordered_iterator&)
. As a consequence, this piece of code couldn't be compiled:
tsl::ordered_map<int, int> mymap = {{-1, 15}, {-2, 17}};
tsl::ordered_map<int, int>::iterator it = mymap.begin();
BOOST_CHECK_EQUAL(it->second, 15);
it = 1 + it;
BOOST_CHECK_EQUAL(it->second, 17);
The second issue is that, the iterator + iterator
operator shouldn't exist. As no standard iterator overrides this operator. So this code also doesn't work:
tsl::ordered_map<int, int> mymap = {{-1, 15}, {-2, 17}};
tsl::ordered_map<int, int>::iterator it = mymap.begin();
it + it;
tsl::ordered_set<int> test{1, 3, 5, 7, 9};
I want to insert number 6 into between 5 and 7.
Expected result: {1, 3, 5, 6, 7, 9}
The below code always inserts into last position.
tsl::ordered_set<int> test{1, 3, 5, 7, 9};
test.insert(test.begin() + 3, 6);
std::cout << "ordered_set: ";
for (auto & i : test)
{
std::cout << i << " ";
}
std::cout <<"\n\n";
output:
ordered_set: 1 3 5 7 9 6
Firstly, thank you @Tessil for your selection brilliant open source hash tables.
An example of my issue would be:
tsl::ordered_set<std::string_view> foo;
foo.emplace("kind");
foo.emplace("oldUri");
foo.emplace("newUri");
foo.insert_at_position(foo.begin(), "annotationId");
std::cout << foo.count("kind") << std::endl; // incorrectly prints "0"
Making further calls on the same set reveals that the "kind" key is actually present:
std::cout << foo.size() << std::endl; // correctly prints "4"
for (auto key : foo) {
std::cout << key << ", "; // correctly prints "annotationId, kind, oldUri, newUri, "
}
std::cout << std::endl;
And we can even get a duplicate key to appear in the map:
foo.emplace("kind");
std::cout << foo.count("kind") << std::endl; // prints "1"
std::cout << foo.size() << std::endl; // prints "5"
for (auto key : foo) {
std::cout << key << ", "; // prints "annotationId, kind, oldUri, newUri, kind, "
}
std::cout << std::endl;
That is with Apple clang version 14.0.0 (clang-1400.0.29.202)
using libc++.
ordered-map version: 1.0.0
Hi! It seems the following code example doesn't work due to the std::deque<std::pair<...>>
type used.
class foo {
tsl::ordered_map<foo, foo> map;
bool operator==(const foo&) const;
};
namespace std {
template <> struct hash<foo> {
.....
};
}
However, std::unordered_map
works in this situation. I use Visual Studio 2015 Update 3.
Using MinGW GCC 8 RC from here.
There is the compilation error when using the following code:
template<class Key, class T, class Ignore, class Allocator, class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
using ordered_map = tsl::ordered_map<Key, T, Hash, KeyEqual, Allocator>;
using namespace nlohmann;
using json_ord = basic_json<ordered_map>;
inline json_ord operator "" _json_ord(const char* s, std::size_t n)
{
return json_ord::parse(s, s + n);
}
inline json_ord::json_pointer operator "" _json_ord_pointer(const char* s, std::size_t n)
{
return json_ord::json_pointer(std::string(s, n));
}
void main()
{
auto js { R"({"3":null, "1":"the middle one...", "2":null})"_json_ord };
}
This is the following error:
In file included from C:/MinGW/include/c++/8.0.1/deque:64,
from ordered-map/tsl/ordered_map.h:29,
C:/MinGW/include/c++/8.0.1/bits/stl_deque.h: In instantiation of 'class std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, s
td::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > > >':
external/ordered-map/tsl/ordered_hash.h:213:97: required from 'class tsl::detail_ordered_hash::ordered_hash<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_j
son<ordered_map> >, tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash<std::__cxx11::basic_string<char> >, std::eq
ual_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque<std::pa
ir<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<nstd:
:ordered_map> > > > >::KeySelect, tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash<std::__cxx11::basic_string<char> >,
std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque
<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_js
on<ordered_map> > > > >::ValueSelect, std::hash<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const
std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > >, std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_ma
p> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> > > > >'
external/ordered-map/tsl/ordered_map.h:106:43: required from 'class tsl::ordered_map<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map>, std::hash
<std::__cxx11::basic_string<char> >, std::equal_to<std::__cxx11::basic_string<char> >, std::allocator<std::pair<const std::__cxx11::basic_string<char>, nlohmann::basic_jso
n<ordered_map> > >, std::deque<std::pair<std::__cxx11::basic_string<char>, nlohmann::basic_json<ordered_map> >, std::allocator<std::pair<const std::__cxx11::ba
sic_string<char>, nlohmann::basic_json<ordered_map> > > > >'
external/json/include/nlohmann/json.hpp:2970:15: required from 'class nlohmann::basic_json<ordered_map>'
json.hpp.cpp:40:79: required from here
C:/MinGW/include/c++/8.0.1/bits/stl_deque.h:847:21: error: static assertion failed: std::deque must have the same value_type as its allocator
static_assert(is_same<typename _Alloc::value_type, _Tp>::value,
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Hi,
How can I get an element by a random number?
Update: I think the nth method is it, right?
Thanks!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.