Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > When is std::list more effective than the other containers?

Reply
Thread Tools

When is std::list more effective than the other containers?

 
 
Niklas Norrthon
Guest
Posts: n/a
 
      12-13-2005
"Axter" <(E-Mail Removed)> writes:

> Robbie Hatley wrote:
> > "Josh Mcfarlane" <(E-Mail Removed)> wrote:
> >
> > > When would using std::list be more efficient / effective than using
> > > other containers such as vector, deque, etc?

> >
> > std::list is best any time you have one or more of the
> > following situations:
> >
> > 1. Wildly variable amount of data.

> Should not be a factor in considering using std::list instead of
> std::vector


Except that once vector has reserved some memory it's not returned
to the memory manager until the entire vector is destroyed, while
memory used by a list node is returned as soon as that node is
erased.

> > 3. Data needs to be sorted frequently.

> If data needs to be frequently sorted, then consider using std::set or
> std::map instead.


Except when data needs to be sorted in different ways each time.

> Most experts, (like Herb Sutters and Scott Meyers) recommend using
> std::vector as the default container.
> The Official C++ standard also recommends using std::vector as the
> default container.
> In most container requirements, std::vector will out perform std::list.


I agree, use vector as the default container, but don't forget about
the alternatives, and their usage.

/Niklas Norrthon
 
Reply With Quote
 
 
 
 
Niklas Norrthon
Guest
Posts: n/a
 
      12-13-2005
"g" <(E-Mail Removed)> writes:

> >It's optimized for insertions and sorting. Since the
> >order of elements is based on links, elements don't
> >have to be moved to sort or insert, which drastically
> >speeds those processes.

>
> >Try doing that with a vector! Oh, lordy...
> >You'd need to move thousands of bytes of data around,
> >possibly repeatedly re-allocating huge memory blocks.
> >Very inefficient.

>
> not if you use pointers........


But then I have other problems, like ownership and lifetime
to worry about...

/Niklas Norrthon
 
Reply With Quote
 
 
 
 
Alf P. Steinbach
Guest
Posts: n/a
 
      12-13-2005
* Niklas Norrthon:
>
> ... once vector has reserved some memory it's not returned
> to the memory manager until the entire vector is destroyed, while
> memory used by a list node is returned as soon as that node is
> erased.


You can (in practice) "compact" a vector by copying and swapping,
something like

template< typename T >
void compact( std::vector<T>& v )
{
std::vector<T> copy( v.size() );
copy.assign( v.begin(), v.end() );
v.swap( copy );
}

Disclaimer: untested code.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
 
Reply With Quote
 
Axter
Guest
Posts: n/a
 
      12-13-2005
Niklas Norrthon wrote:
> "Axter" <(E-Mail Removed)> writes:
>
> > pepp wrote:
> > > The runtime of list for
> > > deletion and insertion operation is better than vectors.
> > >
> > > When you delete anything from vector, all the iterators after that item
> > > must be reassigned. no such thing wtih list.

> >
> > That's not entirely correct.
> > This only happens when deleting from the center or beginning of the
> > vector.
> >
> > deleting from the end of the vector does not cause this.

>
> Wrong:
>
> #include <vector>
> using std::vector;
>
> typedef vector<int> Vec;
> typedef Vec::const_iterator Const_Iter;
>
> int main()
> {
> /* first we set up things */
> Vec foo;
> foo.push_back(1);
> foo.push_back(2);
>
> /* get an iterator to after the last item of the vector: */
> Const_iter last = foo.end();
>
> /* now it's time to delete from the end of the vector */
> foo.pop_back();
>
> /* if pepp's statement had been correct the following
> * would be ok, but last is invalidated by the pop_back
> * and this is UB */
>
> for (Const_Iter i = foo.begin(); i != last; ++i) {
> /* do something here */
> }
> return 0;
>


Niklas Norrthon,
Exactly what was wrong?
Your code doesn't seem to prove anything related to my comment.
Are you sure you replied to the right post?

I stand my initial post, in the it's incorrect to say that "When you
delete anything from vector, all the iterators after that item must be
reassigned".
Because if you delete from the end, there are no more iterators after
that item.
Moreover, if you're using a std::deque, and you delete from the end or
beginning, you also don't have the reassignment issue.

 
Reply With Quote
 
Axter
Guest
Posts: n/a
 
      12-13-2005

Niklas Norrthon wrote:
> "g" <(E-Mail Removed)> writes:
>
> > >It's optimized for insertions and sorting. Since the
> > >order of elements is based on links, elements don't
> > >have to be moved to sort or insert, which drastically
> > >speeds those processes.

> >
> > >Try doing that with a vector! Oh, lordy...
> > >You'd need to move thousands of bytes of data around,
> > >possibly repeatedly re-allocating huge memory blocks.
> > >Very inefficient.

> >
> > not if you use pointers........

>
> But then I have other problems, like ownership and lifetime
> to worry about...
>


You can fix ownership and lifetime problem by using smart pointers like
boost::shared_ptr, clone smart pointers, or COW smart pointers:
http://www.boost.org/libs/smart_ptr/shared_ptr.htm (boost::shared_ptr)
http://code.axter.com/copy_ptr.h (A clone smart pointer)
http://code.axter.com/cow_ptr.h (COW Copy On Write)

Don't try using auto_ptr on STL containers, because it's usage in
containers is not portable, and when fully implemented, not compilable.

 
Reply With Quote
 
Diego Martins
Guest
Posts: n/a
 
      12-13-2005
this is better:

template< typename T >
void compact( std::vector<T>& v )
{ std::vector<T>(v).swap(v); }

chapter 17 - Effective STL - Scott Meyers

 
Reply With Quote
 
roberts.noah@gmail.com
Guest
Posts: n/a
 
      12-13-2005

Kai-Uwe Bux wrote:

> a) A vector is not just "almost" guaranteed to be contiguous. It is
> contiguous. The standard implies that.


Being guaranteed and being implied are two very different things. An
implementation is free to implement a vector any way they want. The
requirements of the interface mean that there will probably never be
anything but a contiguous vector but there could be if an
implementation could meet those requirements without being contiguous.

In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
standard to be fixed in the future. So, someday maybe it will be
guaranteed but today it is not. Frankly I don't agree; if a vector
could be better made non-contiguous then it doesn't bother me one bit
so long as it appears to be to me (assuming I don't try direct access
to the memory *p = &vect[0]).

 
Reply With Quote
 
roberts.noah@gmail.com
Guest
Posts: n/a
 
      12-13-2005

Axter wrote:
> (E-Mail Removed) wrote:


> > I don't agree. Every container serves a particular purpose. It could
> > be that in YOUR case most development domains seem to be least served
> > by the list container there are certainly a lot of cases when a list is
> > a very appropriate choice. The best thing is to understand the
> > implementations of the different containers and where those kind of
> > algorithms are best used. Take a class or read a book on data
> > structures and implement your own list, vector, map, etc...and then you
> > will be able to understand their value and when to use what.

>
> As a contractor, I've worked in many locations, and it's been my
> experience when finding std::list used in code, that 9 out of 10 times,
> std::list is being used inappropriately, and std::vector or std::deque
> would have done the same job faster.


I'm sorry but I just don't buy your "credentials". Anyone that would
call that dynamic_array class of yours an example of how TO do
something doesn't meet my requirements of an expert. Judging by the
single code example I have seen from you I am not at all impressed.

 
Reply With Quote
 
Alf P. Steinbach
Guest
Posts: n/a
 
      12-13-2005
* Diego Martins:
> this is better:
>
> template< typename T >
> void compact( std::vector<T>& v )
> { std::vector<T>(v).swap(v); }
>
> chapter 17 - Effective STL - Scott Meyers


A too smart implementation is free, I believe, to simply not copy
anything here, and with no actual copying, no memory usage reduction.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
 
Reply With Quote
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      12-13-2005
http://www.velocityreviews.com/forums/(E-Mail Removed) wrote:

>
> Kai-Uwe Bux wrote:
>
>> a) A vector is not just "almost" guaranteed to be contiguous. It is
>> contiguous. The standard implies that.

>
> Being guaranteed and being implied are two very different things. An
> implementation is free to implement a vector any way they want. The
> requirements of the interface mean that there will probably never be
> anything but a contiguous vector but there could be if an
> implementation could meet those requirements without being contiguous.


From the standard:

[23.2.4/1]

[...] The elements of a vector are stored contiguously, meaning that if v is
a vector<T, Allocator> where T is some type other than bool, then it obeys
the identity &v[n] == &v[0] + n for all 0 <= n < v.size().


> In Thinking in C++ V2, Bruce Eckel claims this is a shortsight of the
> standard to be fixed in the future. So, someday maybe it will be
> guaranteed but today it is not. [snip]


That book seems to be outdated.


Best regards

Kai-Uwe Bux
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com Java 0 03-06-2008 08:11 AM
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com C++ 0 03-05-2008 08:41 AM
Like all great travelers, I have seen more than I remember andremember more than I have seen. shenrilaa@gmail.com C Programming 0 03-05-2008 03:26 AM
How to access web.sitemap file from other virtual directories other than the current application root folder? hvajja@gmail.com ASP .Net 0 08-07-2006 08:26 PM
What other produces other than "PC Anywhere"? JnlSeb Computer Information 4 01-08-2004 06:12 PM



Advertisments