Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

C++ unordered_set of vectors

Tags:

c++

c++11

vector

Can I create a unordered_set of vectors in C++? something like this

std::unordered_set<std::vector<int>> s1; 

because I know that is possible with the "set" class of the std lib but seems that it doesn't work for the unordered version thanks

Update: this is the exactly code that I'm trying to use

typedef int CustomerId; typedef std::vector<CustomerId> Route; typedef std::unordered_set<Route> Plan;  // ... in the main Route r1 = { 4, 5, 2, 10 }; Route r2 = { 1, 3, 8 , 6 }; Route r3 = { 9, 7 }; Plan p = { r1, r2 }; 

and it's all right if I use set, but I receive a compilation error when try to use the unordered version

main.cpp:46:11: error: non-aggregate type 'Route' (aka 'vector<CustomerId>') cannot be initialized with an initializer list     Route r3 = { 9, 7 }; 
like image 395
Cattani Simone Avatar asked Apr 24 '15 19:04

Cattani Simone


People also ask

What is the difference between unordered set and vector?

Unordered Set: Does not follow any order and the elements are randomly distributed. Vectors: Vectors are similar to a dynamic array as they automatically get reshaped or resized along with insertion or deletion of elements. The elements of a vector are stored in contiguous memory units.

What is unordered set in Python?

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value. In an unordered_set, the value of an element is at the same time its key, that identifies it uniquely.

What are the set of vectors in C++?

Set of vectors in C++ 1 Sequence containers: array, vectors, list, etc. 2 Container adaptors: stack, queue, priority_queue, etc. 3 Associative containers: sets, map, multiset, multimap, etc More ...

What is set of vectors in STL?

Vector elements are placed in contiguous storage so that they can be accessed and traversed using iterators. Set of Vectors in STL: Set of Vectors can be very efficient in designing complex data structures. Syntax: set<vector<datatype>> set_of_vector; For example: Consider a simple problem where we have to print all the unique vectors.


2 Answers

Sure you can. You'll have to come up with a hash though, since the default one (std::hash<std::vector<int>>) will not be implemented. For example, based on this answer, we can build:

struct VectorHash {     size_t operator()(const std::vector<int>& v) const {         std::hash<int> hasher;         size_t seed = 0;         for (int i : v) {             seed ^= hasher(i) + 0x9e3779b9 + (seed<<6) + (seed>>2);         }         return seed;     } }; 

And then:

using MySet = std::unordered_set<std::vector<int>, VectorHash>; 

You could also, if you so choose, instead add a specialization to std::hash<T> for this type (note this could be undefined behavior with std::vector<int>, but is definitely okay with a user-defined type):

namespace std {     template <>     struct hash<std::vector<int>> {         size_t operator()(const vector<int>& v) const {             // same thing         }     }; }  using MySet = std::unordered_set<std::vector<int>>; 
like image 175
Barry Avatar answered Oct 17 '22 02:10

Barry


As an alternative to a custom-written hasher, Boost provides a hasher for many standard library types. This should work in your case:

#include <boost/container_hash/hash.hpp>  std::unordered_set<   std::vector<int>,   boost::hash<std::vector<int>> > s1; 

Reference: https://www.boost.org/doc/libs/1_78_0/doc/html/hash/reference.html

In older Boost versions, the header file was boost/functional/hash.hpp.

like image 20
Daniel Langr Avatar answered Oct 17 '22 02:10

Daniel Langr