[LLVMdev] llvm::DenseSet with reverse iterator

[Vassil Vassilev]

Thanks for the explanation Michael!

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

Vassil
On 07/12/2012 10:53 PM, Michael Ilseman wrote:
> 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
>>
>>