STL Containers - Revision history

Jim: minor

2011-11-23T03:47:25Z

minor

← Older revision		Revision as of 03:47, 23 November 2011
Line 29:		Line 29:

	====List====		====List====
-	A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do ~~now~~ allow for random access via an index like arrays/vectors.	+	A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do not allow for random access via an index like arrays/vectors.

	Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes. Lists can append elements indefinitely without the need for reallocation.		Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes. Lists can append elements indefinitely without the need for reallocation.

Skrach: /* Introduction */

2011-11-11T18:41:35Z

Introduction

← Older revision		Revision as of 18:41, 11 November 2011
Line 7:		Line 7:
	We have also provided a [[#Stack\|stack]] and a [[#Queue\|queue]], which are specialized containers with a more specific purpose in mind.		We have also provided a [[#Stack\|stack]] and a [[#Queue\|queue]], which are specialized containers with a more specific purpose in mind.

-	Stl containers can hold both string and numeric values, as well as [[#References]] to either type. References are similar to pointers in C/C++ type languages, where the container element will actually "point to" the specified variable. That is, if you add a reference to a variable to a container, if that variable subsequently changes in your program, the value within the container will change as well.	+	Stl containers can hold both string and numeric values, as well as [[#References\|references]] to either type. References are similar to pointers in C/C++ type languages, where the container element will actually "point to" the specified variable. That is, if you add a reference to a variable to a container, if that variable subsequently changes in your program, the value within the container will change as well.

	===Initialization===		===Initialization===

Skrach: /* Introduction */

2011-11-11T18:41:18Z

Introduction

← Older revision		Revision as of 18:41, 11 November 2011
Line 6:		Line 6:

	We have also provided a [[#Stack\|stack]] and a [[#Queue\|queue]], which are specialized containers with a more specific purpose in mind.		We have also provided a [[#Stack\|stack]] and a [[#Queue\|queue]], which are specialized containers with a more specific purpose in mind.
		+
		+	Stl containers can hold both string and numeric values, as well as [[#References]] to either type. References are similar to pointers in C/C++ type languages, where the container element will actually "point to" the specified variable. That is, if you add a reference to a variable to a container, if that variable subsequently changes in your program, the value within the container will change as well.

	===Initialization===		===Initialization===

Skrach: /* Iteration */

2011-11-11T00:29:55Z

Iteration

← Older revision		Revision as of 00:29, 11 November 2011
Line 50:		Line 50:

	Unfortunately, due to the internal implementation of the STL containers, although you will iterate over every element in the collection, an order cannot be guaranteed. Also, if the container is modified during iteration, the iterator cannot be guaranteed to still be valid. If you modify the container during iteration, you must start the iteration process over in order to be sure every element is accessed.		Unfortunately, due to the internal implementation of the STL containers, although you will iterate over every element in the collection, an order cannot be guaranteed. Also, if the container is modified during iteration, the iterator cannot be guaranteed to still be valid. If you modify the container during iteration, you must start the iteration process over in order to be sure every element is accessed.
		+
		+	In general iteration is used to aggregate all of the data within a container (calculate a total, average, etc), or maybe to see if a certain value exists within the collection.

	===[[STL Container IB Reference\|IB Reference]]===		===[[STL Container IB Reference\|IB Reference]]===
	Internet Basic function reference.		Internet Basic function reference.

Skrach at 00:24, 11 November 2011

2011-11-11T00:24:44Z

← Older revision		Revision as of 00:24, 11 November 2011
Line 20:		Line 20:
	'''<values>''' (Optional) All containers can be declared with initial values, separated by semi-colons (';'). These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected. Maps require both a key and value, separated by a comma (','), for initialization.		'''<values>''' (Optional) All containers can be declared with initial values, separated by semi-colons (';'). These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected. Maps require both a key and value, separated by a comma (','), for initialization.

-	===Vector===	+	===General Usage===
		+	====Vector====
	A vector is an indexable, sequence container that behaves like an array, but will grow as required. Like arrays, vectors store their data in contiguous memory, which is why access with a numeric index is so efficient, but unlike arrays you get all of the robust functionality of an STL container.		A vector is an indexable, sequence container that behaves like an array, but will grow as required. Like arrays, vectors store their data in contiguous memory, which is why access with a numeric index is so efficient, but unlike arrays you get all of the robust functionality of an STL container.

	When a vector is created, it has an initial size (either declared in the program or a default specified by the library implementation). Reads/Writes in this space are all very efficient, until the vector fills up and a new value is added. When this happens, the vector automatically allocates another contiguous memory block, and copies the current values. This means that ''most'' of the time, adding to a vector is very efficient, but every once in a while this reallocation will take place. Note that a performance hit will only be noticeable on very large vectors.		When a vector is created, it has an initial size (either declared in the program or a default specified by the library implementation). Reads/Writes in this space are all very efficient, until the vector fills up and a new value is added. When this happens, the vector automatically allocates another contiguous memory block, and copies the current values. This means that ''most'' of the time, adding to a vector is very efficient, but every once in a while this reallocation will take place. Note that a performance hit will only be noticeable on very large vectors.

-	===List===	+	====List====
	A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors.		A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors.

	Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes. Lists can append elements indefinitely without the need for reallocation.		Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes. Lists can append elements indefinitely without the need for reallocation.

-	===Map===	+	====Map====
	A map is an associative container consisting of key/value pairs. A string index is "mapped" to the value specified, making the syntax similar to arrays and vectors.		A map is an associative container consisting of key/value pairs. A string index is "mapped" to the value specified, making the syntax similar to arrays and vectors.

	Maps are designed for efficient access to values using their key, unlike sequence containers which are more efficient at accessing elements by their position (index). Keys are unique - that is there will never be two values associated with the same key.		Maps are designed for efficient access to values using their key, unlike sequence containers which are more efficient at accessing elements by their position (index). Keys are unique - that is there will never be two values associated with the same key.

-	===Stack===	+	====Stack====
	Internally, stacks utilize deque (double-ended queue) containers to provide LIFO (Last In, First Out) access, which means that you are adding and removing elements at the "back" of the container. A stack should be used when the last element you added to the container is the first one you want back out again.		Internally, stacks utilize deque (double-ended queue) containers to provide LIFO (Last In, First Out) access, which means that you are adding and removing elements at the "back" of the container. A stack should be used when the last element you added to the container is the first one you want back out again.

	Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.		Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.

-	===Queue===	+	====Queue====
	Internally, queues utilize deque (double-ended queue) containers to provide FIFO (First In, First Out) access, which means that you are adding elements at the "back" of the container, and removing them from the "front" of the container. A queue should be used when the first element you added is the first one you want back out again.		Internally, queues utilize deque (double-ended queue) containers to provide FIFO (First In, First Out) access, which means that you are adding elements at the "back" of the container, and removing them from the "front" of the container. A queue should be used when the first element you added is the first one you want back out again.

	Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.		Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.
		+
		+	===Iteration===
		+	All STL Containers provide a standard iteration interface that allows you to step through each element in the collection. That is, using the same functions, you can iterate through any STL container. Think of iterating through a container as reading records from a file. First the iterator is initialized, then you can move it through the container one element at a time. At each position, you can read or write the element.
		+
		+	Unfortunately, due to the internal implementation of the STL containers, although you will iterate over every element in the collection, an order cannot be guaranteed. Also, if the container is modified during iteration, the iterator cannot be guaranteed to still be valid. If you modify the container during iteration, you must start the iteration process over in order to be sure every element is accessed.

	===[[STL Container IB Reference\|IB Reference]]===		===[[STL Container IB Reference\|IB Reference]]===
	Internet Basic function reference.		Internet Basic function reference.

Skrach at 23:45, 10 November 2011

2011-11-10T23:45:51Z

← Older revision		Revision as of 23:45, 10 November 2011
Line 44:		Line 44:

	Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.		Deques are a sort of vector-list hybrid that allow for random access via an index (like arrays/vectors), and also allow for efficient addition/removal of elements at the beginning or end of the container. Insertions/removals from the middle of the container are not as efficient as lists.
		+
		+	===[[STL Container IB Reference\|IB Reference]]===
		+	Internet Basic function reference.

Skrach: /* List */

2011-11-10T23:35:47Z

List

← Older revision		Revision as of 23:35, 10 November 2011
Line 28:		Line 28:
	A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors.		A list is a sequence container in which each value points to the next value. This way, lists allow for fast insertion and deletion anywhere in the container, but do now allow for random access via an index like arrays/vectors.

-	Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes.	+	Lists are implemented as doubly-linked lists, and since each value points to other values, the data does not need to be in contiguous storage like vectors. Thus unlike vectors, lists are more efficient for programs that require consistent insertion/removal functionality, as a vector will have to perform dynamic reallocation (described above) as its size changes. Lists can append elements indefinitely without the need for reallocation.

	===Map===		===Map===

Skrach: /* Initialization */

2011-11-10T23:34:09Z

Initialization

← Older revision		Revision as of 23:34, 10 November 2011
Line 10:		Line 10:
	STL containers are defined in the declarative section, using a similar syntax to formats with some extra options. Containers can be declared empty, with an initial size (except maps), or with initial values. You must provide the name you will use to reference the container, as well as the type of container it will be.		STL containers are defined in the declarative section, using a similar syntax to formats with some extra options. Containers can be declared empty, with an initial size (except maps), or with initial values. You must provide the name you will use to reference the container, as well as the type of container it will be.

-	<container-name>: <container-type>[(<size>)] [value1; value2; ...]	+	<container-name>: <container-type>[(<size>)] [<value1>; <value2>; ...]

	'''<container-name>''' (Required) Name used to reference this container in your program.		'''<container-name>''' (Required) Name used to reference this container in your program.

Skrach: /* Initialization */

2011-11-10T23:33:51Z

Initialization

← Older revision		Revision as of 23:33, 10 November 2011
Line 18:		Line 18:
	'''<size>''' (Optional) All containers except maps can be declared with an initial size. The container will initialize with the specified size, containing empty values for uninitialized values.		'''<size>''' (Optional) All containers except maps can be declared with an initial size. The container will initialize with the specified size, containing empty values for uninitialized values.

-	'''~~Initial Values~~''' All containers can be declared with initial values. These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected.	+	'''<values>''' (Optional) All containers can be declared with initial values, separated by semi-colons (';'). These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected. Maps require both a key and value, separated by a comma (','), for initialization.

	===Vector===		===Vector===

Skrach: /* Initialization */

2011-11-10T23:31:52Z

Initialization

← Older revision		Revision as of 23:31, 10 November 2011
Line 10:		Line 10:
	STL containers are defined in the declarative section, using a similar syntax to formats with some extra options. Containers can be declared empty, with an initial size (except maps), or with initial values. You must provide the name you will use to reference the container, as well as the type of container it will be.		STL containers are defined in the declarative section, using a similar syntax to formats with some extra options. Containers can be declared empty, with an initial size (except maps), or with initial values. You must provide the name you will use to reference the container, as well as the type of container it will be.

-	~~'''Initial Values''' All containers can be declared with initial values.~~ ~~These values will be automatically inserted into the~~ container ~~at the beginning of the program, and the~~ container's size ~~will be accurately reflected~~.	+	<container-name>: <container-type>[(<size>)] [value1; value2; ...]

-	'''~~Initial Size~~''' All containers except maps can be declared with an initial size. The container will initialize with the specified size, ~~but will contain blank~~ values.	+	'''<container-name>''' (Required) Name used to reference this container in your program.
		+
		+	'''<container-type>''' (Required) One of the following: vector, list, map, stack, queue.
		+
		+	'''<size>''' (Optional) All containers except maps can be declared with an initial size. The container will initialize with the specified size, containing empty values for uninitialized values.
		+
		+	'''Initial Values''' All containers can be declared with initial values. These values will be automatically inserted into the container at the beginning of the program, and the container's size will be accurately reflected.

	===Vector===		===Vector===