[LLVMdev] llvm::DenseSet with reverse iterator

[Michael Ilseman]

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


On Thu, Jul 12, 2012 at 11:43 AM, Vassil Vassilev <vvasilev at cern.ch> wrote:
> 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
>
> On 7/12/12 6:23 PM, Michael Ilseman wrote:
>>
>> 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
>>
>> On Thu, Jul 12, 2012 at 10:04 AM, Owen Anderson <resistor at mac.com> wrote:
>>>
>>> Reverse iteration doesn't really make sense for DenseSet, since its
>>> iteration order isn't meaningful to begin with...
>>>
>>> --Owen
>>>
>>> On Jul 12, 2012, at 8:20 AM, Vassil Vassilev wrote:
>>>
>>>> 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
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>