llvm::DenseSet with reverse iterator

Hi,
   I need a data structure which has fast search and I can walk it forward and backward. Is there something like that in LLVM ADT which am not aware of? And if not can I implement it in llvm::DenseSet?
Vassil

Reverse iteration doesn't really make sense for DenseSet, since its iteration order isn't meaningful to begin with...

--Owen

Something that might interest you is the SetVector, which as its name
implies is both a set and a vector paired together. You get the
advantage of doing set-like operations (search) on the set and
vector-like operations (iteration, random access) on the vector, but
at the cost of paying the price for both data structures when
modifying the structure (and double the memory). This seems like it
might be more heavy-weight than you needed, but it might serve your
purposes. The iteration order is the insertion order; if you want some
other ordering and stronger iterators, you might have to consider
std::set.

[1] http://llvm.org/doxygen/SetVector_8h_source.html
[2] http://llvm.org/docs/ProgrammersManual.html#dss_setvector

Hi,
   Thanks a lot for the help!
   It seems that the SmallSetVector is the ADT I need (interface-wise). Is more efficient than llvm::UniqueVector?
   In my use case I have to insert a new element in the structure only if the element is unique. I hardly expect more than 32 elements. Do you think I gain a lot if I use the SmallSetVector instead of using SmallVector + slow searching on every push_back?
Vassil

Hi,
   Oh! Good point :slight_smile:
Vassil

UniqueVector is an stl map coupled with an stl vector[1], which seems
very undesirable for you. As far as SmallVector + slow search, I
believe that is precisely what the implementation of SmallSet does
until it has to grow, after which it uses an stl set[2]. If you're
always staying within your small number, SmallSetVector would be
wasteful as the SmallSet would itself also have a SmallVector.

If you need to access in insertion order then go with SmallVector +
slow search. If you need sorted order then go with stl set. If you
don't care, pick which one makes the most sense for your constraints:
SmallVector uses less memory, better locality, and is faster while
pretty small, and the stl set is simpler to use and better when large.
I don't have a good feel for what exactly is "pretty small", but a lot
of the LLVM code chooses 4 or 8.

[1] http://llvm.org/docs/doxygen/html/UniqueVector_8h_source.html
[2] http://llvm.org/docs/doxygen/html/SmallSet_8h_source.html#l00048

Thanks for the explanation Michael!

I am actually using the SmallVector, but I thought there is something better "out there" :slight_smile:
BTW I am curious what is "pretty small", too...

Vassil