Using unordered_set or unordered_map to hold small array(s) of ints
Can someone please provide an example of how to best use unordered_map/set to store/lookup many small arrays of integers. e.g. unsigned int I[5] = {1000,3344455,12455222,8832232}; I'm guessing that there is no facility for using raw C++ arrays, and that one must wrap them in a struct. Thanks in advance.
On Fri, Aug 20, 2010 at 2:21 AM, B Hart <bhartsb@gmail.com> wrote:
Can someone please provide an example of how to best use unordered_map/set to store/lookup many small arrays of integers. e.g. unsigned int I[5] = {1000,3344455,12455222,8832232}; I'm guessing that there is no facility for using raw C++ arrays, and that one must wrap them in a struct.
I guess you mean C arrays and not C++ arrays as C++ arrays are probably std::vector's. C arrays or C++ vectors would work fine though, but you would need to supply your own comparison function, and if C arrays add an ending tag like zero or have a static length.
Just a comparison function? How is, for example, unordered set going to know the end of the array, to hash it? I don't know what is happening under-the-hood so I'm deferring to the list experts. Can you give me a simple example? On Fri, Aug 20, 2010 at 4:31 AM, OvermindDL1 <overminddl1@gmail.com> wrote:
On Fri, Aug 20, 2010 at 2:21 AM, B Hart <bhartsb@gmail.com> wrote:
Can someone please provide an example of how to best use unordered_map/set to store/lookup many small arrays of integers. e.g. unsigned int I[5] = {1000,3344455,12455222,8832232}; I'm guessing that there is no facility for using raw C++ arrays, and that one must wrap them in a struct.
I guess you mean C arrays and not C++ arrays as C++ arrays are probably std::vector's.
C arrays or C++ vectors would work fine though, but you would need to supply your own comparison function, and if C arrays add an ending tag like zero or have a static length. _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Please do not top-post. On Fri, Aug 20, 2010 at 4:07 PM, B Hart <bhartsb@gmail.com> wrote:
Just a comparison function? How is, for example, unordered set going to know the end of the array, to hash it? I don't know what is happening under-the-hood so I'm deferring to the list experts.
Can you give me a simple example?
How is it going to know the end? That depends on how you create your array and set up your hash function. If you have an end-of-array marker then you would stop at that (like how '\0' is the end-of-array marker for C strings), if it is a static length then you would just use that, etc...
well assuming an unsigned int array size of 5 what do you suggest for a reasonably good and fast hash? I was hoping that I could use the built in hash w/o having to invent one. On Fri, Aug 20, 2010 at 3:32 PM, OvermindDL1 <overminddl1@gmail.com> wrote:
Please do not top-post.
On Fri, Aug 20, 2010 at 4:07 PM, B Hart <bhartsb@gmail.com> wrote:
Just a comparison function? How is, for example, unordered set going to know the end of the array, to hash it? I don't know what is happening under-the-hood so I'm deferring to the list experts.
Can you give me a simple example?
How is it going to know the end? That depends on how you create your array and set up your hash function. If you have an end-of-array marker then you would stop at that (like how '\0' is the end-of-array marker for C strings), if it is a static length then you would just use that, etc... _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
FYI, the implementation of ar_hash doesn't look quite right On Fri, Aug 20, 2010 at 7:52 PM, Tim Moore <tim@montecito-software.com> wrote:
struct ar_hash : std::unary_function<small_array, std::size_t> { std::size_t operator()(small_array const& x) const { int init = 0; return boost::hash_value(std::accumulate(x.begin(), x.end(), init)); } };
Consider inputs: small_array one = {1,2,3,4}; small_array two = {1,2,2,5}; The sum of each is 10, which will result in the same hash. This will probably cause hash collisions and result in poorer performance than combining each hash value. Replacing the implementation with the following should give better results: return boost::hash_range(x.begin(), x.end()); Nate
On Fri, Aug 20, 2010 at 5:22 PM, B Hart <bhartsb@gmail.com> wrote:
well assuming an unsigned int array size of 5 what do you suggest for a reasonably good and fast hash?
I was hoping that I could use the built in hash w/o having to invent one.
boost::hash is actually very nicely extensible. It works with a number of containers (I was surprised it didn't support boost::array (or std::array) out of the box), and adding support for something like boost::array is pretty trivial. See below: #include <boost/array.hpp> #include <boost/functional/hash.hpp> #include <boost/unordered_set.hpp> typedef boost::array<int, 5> Array; namespace boost { template <typename T, std::size_t N> std::size_t hash_value(const boost::array<T,N>& arr) { return boost::hash_range(arr.begin(), arr.end()); }} int main(int argc, char* argv[]) { Array arr1 = {1000, 3344455, 12455222, 8832232, 1234}; Array arr2 = {2000, 4344455, 22455222, 16832232, 2345}; boost::unordered_set<Array> mySet; mySet.insert(arr1); assert(mySet.find(arr2) == mySet.end() && "Found wrong array"); assert(mySet.find(arr1) != mySet.end() && "Not finding correct array"); return 0; } HTH, Nate
AMDG B Hart wrote:
Can someone please provide an example of how to best use unordered_map/set to store/lookup many small arrays of integers. e.g. unsigned int I[5] = {1000,3344455,12455222,8832232}; I'm guessing that there is no facility for using raw C++ arrays, and that one must wrap them in a struct.
If the arrays are fixed size, you can use boost::array. In Christ, Steven Watanabe
Can you provide me a simple example? On Fri, Aug 20, 2010 at 8:34 AM, Steven Watanabe <watanabesj@gmail.com>wrote:
AMDG
B Hart wrote:
Can someone please provide an example of how to best use unordered_map/set to store/lookup many small arrays of integers. e.g. unsigned int I[5] = {1000,3344455,12455222,8832232}; I'm guessing that there is no facility for using raw C++ arrays, and that one must wrap them in a struct.
If the arrays are fixed size, you can use boost::array.
In Christ, Steven Watanabe
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
participants (5)
-
B Hart -
Nathan Crookston -
OvermindDL1 -
Steven Watanabe -
Tim Moore