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
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
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 > > >