Solved

Can push_back() and end() be made to be efficient within vectors?

Posted on 2000-03-25
4
252 Views
Last Modified: 2013-12-14
//  This code can be found at:  http://waldo.wi.mit.edu/~kstanley/STL/ex4.cc
//
//  I am not sure whether my set of objects of class Contig (defined
//  below) will require efficient removal.  If not, I would like to
//  avoid the linked list overhead and just store them as a vector.
//  Hence I wrote the following code which uses a common subset of
//  list and vector:  push_back(), end() and erase().
//
//  My hope is that if erase() is sufficiently infrequent (possibly
//  never used) that this will generate efficient vector code.
//  But, if it turns out that I need to use erase(), I can switch to
//  lists effortlessly.
//
//  I look forward to your thoughts on this.  Do you think that
//  this can be made to run efficiently when I use vectors?
//
//  I have compiled this with and without -DUSELISTS on gcc 2.8.1,
//  cxx V6.2-024 and a copy of stlport downloaded within the past week.
//

class Contig {
 public:
};

#ifdef USELISTS
#include <list>
#define STL_TYPE list
#else
#include <vector>
#define STL_TYPE vector
#endif

main(){

  STL_TYPE<Contig> AllContigs;   // STL_TYPE is vector or list

  AllContigs.push_back( Contig() ) ;
  STL_TYPE<Contig>::iterator a = ((AllContigs.end())) ; a--;
 
  AllContigs.push_back( Contig() ) ;
  Contig Ca = *a;

  AllContigs.erase( (a) );
}




Thanks,
  Ken
0
Comment
Question by:klopter
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
4 Comments
 

Author Comment

by:klopter
ID: 2656493
Is there an STL container class which
will only offer me to intersection of
the vector and list container classes?

Thanks,
  Ken
0
 
LVL 22

Expert Comment

by:nietod
ID: 2656585
First of all, what I usually like to do in this case is to make the container a data member of a class that I defined.  I find that gives you the most amount to encapsulation.  Then if I need to change the container, I just change the data member and some of the class's member functions, I don't have to change any of the code that uses the class.  Does that make sense?
0
 
LVL 22

Accepted Solution

by:
nietod earned 75 total points
ID: 2656603
So I would do something more like

class ContigContainer
{
  list<Contig> CntLst;
public:
   void AddContig(const Contig &C) { CntLst.push_back(C); };
};

But my 2nd concern is the statement

>> I would like to avoid the linked list overhead and
>> just store them as a vector.
It is not necesserally true tha a vector will have less overhead.   A vector will usually use less memory, but not necessarily have less overhead.  A vector will defintely give you better random access than a list, i.e you can quickly get to the xth item in a vector, while in a list that requires sequentially searching the list.  However it is usually faster to add to or delete from a list than a vector  (Especialy if you don't know ahead of time the ultimate size the vector will reach.)  So which is better will definitely depend on what you are going to be doing?  The main considerations are do youi need random (as oposed to sequential) access and will you be doing a lot of additions and deletions (especially if you can't figure out the total number of additions before doing them.)
0
 

Expert Comment

by:maxd128
ID: 2657686
If you use container only as a set of objects without care about order you can remove objects by replacing deleted object with object from the end of vector.
If you need ordering use set or multiset with comparison operator based on sequence in which objects were added.

Note about code: after adding to container new element presaved iterator can become invalid.
0

Featured Post

Enroll in July's Course of the Month

July's Course of the Month is now available! Enroll to learn HTML5 and prepare for certification. It's free for Premium Members, Team Accounts, and Qualified Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

623 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question