STL containers

What are the types of STL containers?


• deque

• hash_map

• hash_multimap

• hash_multiset

• hash_set

• list

• map

• multimap

• multiset

• set

• vector



Sequence containers are: vector deque list

Associative containers are: set multiset map and multimap.

Containers adapters: stack queue and priority_queue.

No hash containers are defined in the current C++ STL standard. However other STL implementation might have some hash based containers (ie STL SGI implementation).



The primary idea in the STL is the container (also known as a collection), which is just what it sounds like: a place to hold things. You need containers because objects are constantly marching in and out of your program and there must be someplace to put them while they’re around. You can’t make named local objects because in a typical program you don’t know How many, or what type, or the lifetime of the objects you’re working with. So you need a container that will expand whenever necessary to fill your needs. All the containers in the STL hold objects and expand themselves. In addition, they hold your objects in a particular way.

A vector is a linear sequence that allows rapid random access to its elements. However, it’s expensive to insert an element in the middle of the sequence, and is also expensive when it allocates additional storage. A deque is also a linear sequence, and it allows random access that’s nearly as fast as vector, but it’s significantly faster when it needs to allocate new storage, and you can easily add new elements at either end (vector only allows the addition of elements at its tail). A list the third type of basic linear sequence, but it’s expensive to move around randomly and cheap to insert an element in the middle. Thus list, deque and vector are very similar in their basic functionality (they all hold linear sequences), but different in the cost of their activities. So for your first shot at a program, you could choose any one, and only experiment with the others if you’re tuning for efficiency.

All three have a member function push_back( ) which you use to insert a new element at the back of the sequence (deque and list also have push_front( )).

An iterator is a class that abstracts the process of moving through a sequence. It allows you to select each element of a sequence without knowing the underlying structure of that sequence.This is a powerful feature, partly because it allows us to learn a single interface that works with all containers, and partly because it allows containers to be used interchangeably.



class Shape {

public:

virtual void draw() = 0;

virtual ~Shape() {};

};

class Circle : public Shape {

public:

void draw() { cout << "Circle::draw\n"; }

~Circle() { cout << "~Circle\n"; }

};

class Triangle : public Shape {

public:

void draw() { cout << "Triangle::draw\n"; }

~Triangle() { cout << "~Triangle\n"; }

};

class Square : public Shape {

public:

void draw() { cout << "Square::draw\n"; }

~Square() { cout << "~Square\n"; }

};

typedef std::vector Container;

typedef Container::iterator Iter;

int main() {

Container shapes;

shapes.push_back(new Circle);

shapes.push_back(new Square);

shapes.push_back(new Triangle);

for(Iter i = shapes.begin();

i != shapes.end(); i++)

(*i)->draw();

// ... Sometime later:

for(Iter j = shapes.begin();

j != shapes.end(); j++)

delete *j;

} ///:~