顺序容器与关联容器

C++ STL’s concepts and usage of sequential containers and associative containers.

Sequential Containers

Sequential containers are collections that hold objects of a specific type.
We have used a container called standard library vector, which is a sequential container, that gathers elements of a single type into a container, and then stores and accesses these elements based on their position. This is what a sequential container is.

Note: The arrangement order of elements in sequential containers is independent of the values of the elements and is determined by the order in which the elements are added to the container.

The standard library defines three types of sequential containers: vector, list, and deque (short for “double-ended queue”, pronounced “deck”).
They differ in terms of accessing elements and the running costs of adding or removing elements.

The standard library also provides three types of container adapters, which essentially adapt operations from the original container types by defining new interfaces to suit the underlying container types. The sequential container adapters include stack, queue, and priority_queue types.

Sequential Container Type	Data Organization Method
vector	Supports fast random access
list	Supports quick insertions/deletions
deque	Double-ended queue
Sequential Container Adapters	Data Organization Method
stack	Last In First Out (LIFO) stack
queue	First In First Out (FIFO) queue
priority_queue	Queue with priority management
Containers define a few operations; most additional operations are provided by the algorithm library, which we will study in the generic algorithms chapter.

The standard library imposes a common interface on the operations defined by containers. The difference among these containers lies in what operations they provide, but if two containers provide the same operations, their interfaces (names and number of parameters) should be the same.

The set of operations for containers forms the following hierarchy:

Some operations apply to all containers.
Others apply only to sequential or associative container types.
Some operations apply to a subset of both sequential and associative container types (map/set).

Definition of Sequential Containers

To define an object of a container type, the relevant header file must be included.
That is, one of the following header files:

1
2
3

#include <vector>
#include <list>
#include <deque>

All container types are class templates (allowing for any number of data types). To define a special data type, one must append a pair of angle brackets to the container name, providing the type of elements stored in the container inside the angle brackets:

1
2
3

vector<string> sevc;
list<int> ilist;
deque<pair<string,int>> strint;

All container types define a default constructor that creates an empty container object of a specified type when no explicit initialization is given. The default constructor takes no parameters.
The most commonly used constructor for container types is the default constructor. In most programs, using the default constructor achieves the best runtime performance and makes the container easier to use.

Initializing Container Elements

In addition to the default constructor, container types also provide other constructors that allow specifying the initial values of elements.

Container Constructor	Action	Applicable Scope
C c;	Creates an empty container named c. C is the container type name, such as vector, T is the element type, such as string and int.	All containers
C c(c2);	Creates a copy c of container c2; c and c2 must have the same container type and store elements of the same type.	All containers
C c(b,e);	Creates c, a copy of the elements in the range denoted by iterators b and e.	All containers
C c(n,t);	Creates container c with n elements, each initialized to value t, where value t must be compatible with or convertible to the type of container c.	Sequential containers
C c(n);	Creates a container c with n value-initialized elements.	Sequential containers

Initializing One Container as a Copy of Another Container

// Creates container testInitCopy and initializes it as a copy of container test
vector<int> testInitCopy(test);
cout<<"vector<int> testInitCopy(test):"<<endl
	<<"C<T> testInitCopy(test)"<<endl;
for(vector<int>::iterator textInitCopyIter=testInitCopy.begin();
	textInitCopyIter!=testInitCopy.end();textInitCopyIter++)
		cout<<*textInitCopyIter<<" ";

When copying one container to another, the types must match: both the container type and the element type must be the same.

Applies to all containers.

Initializing as a Copy of Elements in a Range

Note: When initializing a container using iterators, the container types do not need to match. The element types inside the containers can also differ as long as they are compatible, allowing the elements to be copied into a new container’s element type.

// The container testInitTwoIter is of the same type as container test, whereas the iterators used are test.begin() and test.end()
// Thus, in this instance, we also entirely copy container test to container testInitTwoIter
// (the result is the same as vector<int> testInitCopy(test) but uses a different implementation)
vector<int> testInitTwoIter(test.begin(),test.end());
cout<<"vector<int> testInitTwoIter(test.begin(),test.end()):"<<endl;
for(vector<int>::iterator testInitTwoIterBegin=testInitTwoIter.begin();
	testInitTwoIterBegin!=testInitTwoIter.end();testInitTwoIterBegin++)
	cout<<*testInitTwoIterBegin<<" ";

// The container testchar and the container testint are of different types
// Element assignment uses type conversion from char to int (ASCII values of character types)
vector<char> testchar;
for(char i='A';i!='K';i++){
	testchar.push_back(i);
}
// Iterate and output testchar
for(vector<char>::iterator testiter=testchar.begin();
	testiter!=testchar.end();testiter++)
	cout<<*testiter<<"  ";
cout<<endl;
// Initialize testint as a copy of testchar (with type conversion)
vector<int> testint(testchar.begin(),testchar.end());
// Iterate and output testint
for(vector<int>::iterator testintiter=testint.begin();
	testintiter!=testint.end();testintiter++){
	cout<<*testintiter<<" ";
}

Output:

1 2	A B C D E F G H I J 65 66 67 68 69 70 71 72 73 74

Or initializing a section of element copies:

vector<char>::iterator charIter1=testchar.begin()+2,charIter2=testchar.end()-2;
vector<int> testint(charIter1,charIter2);
// Iterate and output testint
for(vector<int>::iterator testintiter=testint.begin();
	testintiter!=testint.end();testintiter++){
	cout<<*testintiter<<" ";
}

Output result:

67 68 69 70 71 72

Allocating and Initializing a Specified Number of Elements (Only Applicable to Sequential Containers)

Creating a Container with a Specified Number of Elements and Providing Initialization

When creating a sequential container, one can explicitly specify the container size and a (optional) initialization for its elements.
The container size can be a constant or a non-constant expression, and the element initialization must be a value that is compatible with the type used for initializing its elements.

const vector<int>::size_type vectorSize=10;
// Create a vector<string> container with vectorSize elements, each initialized to the string "Hi"
vector<string> test(vectorSize,"Hi");
for(vector<string>::iterator testiter=test.begin();
	testiter!=test.end();testiter++){
	cout<<*testiter<<" ";
}

Output:

Hi Hi Hi Hi Hi Hi Hi Hi Hi Hi

Note: When creating a container, alongside specifying the number of elements, one may choose whether to provide an element initialization. It is also possible to specify only the container size without an initializer.

Creating a Container with a Specified Number of Elements but Not Providing Initialization

1 2	// Create a container with vectorSize elements, without explicitly providing an initializer (values initialized to 0) vector<int> testint(vectorSize);

Or like this:

1 2	extern unsigned get_word_count(const string &file_name); vector<string> test(get_word_count("Chimera"));

Rules for not providing an element initialization:

If no element initialization is provided, the standard library will implement value initialization for that container.
This type of initialization requires the element types to either be built-in or compound types, or classes that provide a default constructor.
If the element type does not have a default constructor, one must explicitly specify its initialization.

Knowledge Supplement:

Value Initialization: If no initial values for elements are given, the standard library will provide a generated initial value for value initialization. This generated initial value will be used to initialize every element in the container; the specific value will depend on the data type of the elements stored in the container.
Element types may be classes that do not define any constructors. In this case, the standard library still generates an object with initialized values, where each member undergoes value initialization.

Note: The constructor that accepts the container size as a parameter only applies to sequential containers, whereas associative containers do not support such initialization.

Type Constraints for Elements in Containers

In C++, most types can be used as element types in containers.
The element types of containers must satisfy the following two constraints:

The element type must support assignment operations.
Objects of the element type must be copyable.

Note: The key types of associative containers must also meet other constraints.

With the exception of reference types, all built-in and compound types can be used as element types.
References do not support assignment operations in the general sense; therefore, there are no containers with elements of reference types.

Except for standard library types related to input and output (which cannot be copied or assigned, thus cannot create containers storing IO type objects), all other standard library types are valid container element types.

Containers themselves meet the above requirements and can define elements where the element types are themselves container types.

Special Requirements for Container Operations

Supporting copy and assignment functionalities is the minimum requirement for the element types of containers. Additionally, some container operations impose special requirements on the element types; if the element types do not support these special requirements, related container operations cannot be executed. It is possible to define a container of that type but not use certain specific operations.

Container Operations that Require Additional Type Constraints

Container operations that require additional type constraints: Constructors that specify the container size and provide a single initialization value. If the container stores objects of class types, the container can only use this constructor if the element types provide a default constructor.

Consider the following code:

// Assume class foo does not have a default constructor but provides a default constructor that requires an int parameter.

vector<foo> empty; // OK, no initialization needed, requires no default constructor
vector<foo> bad(10); // error, creates a container initialized with ten elements, but foo does not provide a default constructor
vector<foo> ok(10, 1); // ok, initializes ten int elements with 1, since the type of 1 is int, it uses the default constructor for int.

Note: The constructor that specifies the size of each element can only be used to create containers of the same type when each element’s initializer is also specified. Therefore, care should be taken in describing container operations with respect to the constraints on each operation concerning the element types.

Containers of Containers

Since containers are constrained by their element types, it is possible to define containers whose elements are container types.

Consider the following code:

1 2	// Use "> >" not ">>" vector< vector<string> > lines; // vector of vector

Note: It is necessary to use a space to separate the two adjacent > symbols to indicate they are two separate symbols; otherwise, the system may interpret >> as a single symbol, which is the right shift operator, resulting in a compilation error.

Exercises

Define a list object to store deque objects, where the deque object holds int type elements.
list<deque<int>> listDeque;

Why can’t we use containers to store iostream objects?
Because IO library types do not support copy and assignment operations.

Suppose there is a class named Foo which does not define a default constructor but provides a constructor that requires an int parameter. Define a list object to hold Foo objects with ten elements.
list<Foo> listFoo(10,0);

Iterators and Iterator Ranges

Whether a container is of const type determines whether its iterators are of const type.

Each container type provides several types of iterators that do not work together.
Like container types, all iterators have the same interface: If one type of iterator supports a certain operation, other iterators supporting that operation will do so in the same way.

For example: all iterators support reading an element from a container via dereference operations. Similarly, containers all provide increment and decrement operators to support accessing the next element from an element.

Operations provided by standard library container types

Operation	Meaning
*iter	Returns a reference to the element pointed to by iterator iter.
iter->mem	Dereferences iter to get the member named mem of the specified element. Equivalent to (*item).mem.
++iter / iter++	Increments iter, making it point to the next element in the container.
–iter / iter–	Decrements iter, making it point to the previous element in the container.
iter1=iter2 iter1!=iter2	Compares two iterators for equality (or inequality). When two iterators point to the same element, or both point to the next position beyond the end of the same container, the two iterators are equal.

Additional Operations Provided by Iterators of Vector and Deque Containers

Among the C++ defined containers, only vector and deque support the following two important sets of operations:

Arithmetic operations on iterators.
The ability to use operators other than != and == to compare two iterators (the != and == relational operators are valid for all containers).

Operation	Meaning
iter+n iter-n	Adds (or subtracts) an integer value n to (or from) the iterator, producing an iterator pointing to the n-th element before (or after) the iterator in the container.
iter+=iter2 iter-=iter2	Iterator addition and subtraction assignment: the result of adding or subtracting iter2 to or from iter1 is copied back to iter1.
iter1-iter2	The subtraction of two iterators provides the number of elements between them. Both iterators `must` point to elements in the same container or one position beyond the container’s end. Only valid for vector or deque containers.
>, >=, <, <=	Relational operators for iterators. When one iterator points to an element that precedes the element pointed to by another iterator in the container, the first iterator is less than the second. Both iterators must point to elements in the same container or one position beyond the container’s end. Only valid for vector or deque containers.

Note: The relational operators only apply to vector or deque containers because only these two types offer fast and random access to their elements. They ensure direct and effective access to specified container elements based on element positions. Both of these containers support random access via element positions, allowing their iterators to execute arithmetic and relational operations efficiently.

For example, calculating the midpoint position of a vector object:

vector<int>::iterator iter=vec.begin()+vec.size()/2;	// OK
// Error version
list<int> listint(vec.begin(),vec.end());
listint.begin()+listint.size()/2;	// list container iterators do not support addition

The list container’s iterator supports neither arithmetic operations (addition or subtraction) nor relational operations (<=,<,>=,>); it only provides pre-increment and post-increment, as well as equality (inequality) operations.

Exercises

Where is the mistake in the following program? How would you correct it?

list<int> lst1;
list<int>::iterator iter1 = list1.begin(),
                    iter2 = list1.end();
while(iter1 < iter2)/*...*/

Answer: The list container does not support relational operations; the while loop can be modified to while(iter1 != iter2).

Assuming vec_iter is bound to an element of a vector object that contains elements of type string, what does the following statement achieve?

1	if(vec_iter->empty)/.../

Answer: If vec_iter is empty, it returns true and enters the if statement; otherwise, it returns false and does not enter the if statement.

Write a loop to output the elements of a list container in reverse order.

int one_ten[10]={0,1,2,3,4,5,6,7,8,9};
list<int> listInt(one_ten,one_ten+10);
list<int>::iterator beg=listInt.begin(),
                    end=listInt.end();
while(end!=beg)
	cout<<*--end<<endl;

Which of the following uses of iterators are incorrect (if any)?

const vector<int> ivec(10);
vector<string> sevc(10);
list<int> ilist(10);

(a)vector<int>::iterator 	it=ivec.begin();
// The container ivec is const, the iterator should also be const; non-const can modify its value via the iterator
(b)list<int> iterator 		it=ilist.begin()+2;
// list container iterators do not support arithmetic operations
(c)vector<string>::iterator it=&sevc[0];// OK
(d)for(vector<string>::iterator it = sevc.begin(); it != 0; ++it)/*...*/
// The iterator is a pointer and will never equal 0; should be changed to it != sevc.end().

Iterator Ranges

C++ uses a pair of iterators to denote an iterator range, with these two iterators pointing to two elements within the same container or one position beyond the end. They are generally named first and last, or beg and end, and denote the range of elements within a container.

Note: The second iterator last (end) never points to the last element of the range but rather to the position right after the last element. The elements included in the range span from the element pointed to by the first iterator (beg) to one element before the position pointed to by last (end).
If first (beg) and last (end) are equal, the iterator range is empty.
Such a range of elements is called a left-closed interval, which is denoted by: $[first,last)$, indicating that the range starts from first and ends at last, not including last.
An iterator lst can either equal first (if the container is empty) or point to some element after the one marked by first (if the container is non-empty), but it absolutely cannot point to an element before the one marked by first.

Requirements for Iterators Forming an Iterator Range

If the first and last iterators meet the following conditions, they can form an iterator range:

They point to elements in the same container or to one position beyond the end.
If the two iterators are not equal, repeatedly incrementing the first iterator must allow reaching the last (i.e., last cannot fall before first in the container).

The compiler cannot ensure the above requirements on its own; it does not inherently know which container the iterators are associated with or how many elements are in that container. Failing to meet the above requirements can lead to undefined behavior at runtime.

Programming Significance of Left-Closed Intervals

The left-closed intervals have two convenient properties, which is why the standard library uses such intervals.
Assuming first and last mark a valid iterator range:

When first equals last, the iterator range is empty.
When first does not equal last, there is at least one element in the iterator range, and first points to the first element of that interval. Through repeated increments, the value of first may continue to increase until first==last is reached.

These two properties mean we can safely write the following loop:

while(first != last){
	// safe to use *first because we know there is at least one element
	++first;
}

Exercises

What constraints must iterators meet to mark a valid iterator range?
(a) Point to elements of the same container or one position beyond the end.
(b) If the two iterators are not equal, first must be able to reach last through repeated increments.
Write a function whose parameters include a pair of iterators and an int data, designed to search for the specified int value within the range marked by the iterators, returning a bool result to indicate whether the specified data was found.

bool find_int(vector<int>::const_iterator first,
              vector<int>::const_iterator last, int find_num){
	while(first != last){
		if(*first == find_num)
			return true;
		else
            first++;
	}
}

Rework the program to search for an element’s value and return the iterator of the found element. Ensure the program works properly even when the sought element does not exist.

#include <iostream>
#include <vector>
using namespace std;
vector<int>::const_iterator find_int(vector<int>::const_iterator first,
									 vector<int>::const_iterator last,
									 int find_num){
	while(first != last){
		if(*first == find_num)
			return first;
		else
            first++;
	}
	if(first == last)
        return last;
}
int main(void){
int one_ten[10]={0,1,2,3,4,5,6,7,8,9};
vector<int> vecInt(one_ten,one_ten+10);
if(find_int(vecInt.begin(),vecInt.end(),9)!=vecInt.end())
    cout<<"Yes"<<endl;
else
    cout<<"No"<<endl;
return 0;
}

Use iterators to write a program that reads several string objects from standard input and stores them in a vector object, then outputs all elements in that vector.

Associative Containers

Associative containers differ essentially from sequential containers in that:

Associative containers store and retrieve elements using keys.
Sequential containers store and access elements based on the order of their positions in the container.

Most behaviors of associative containers are similar to those of sequential containers, but they uniquely support the use of keys.

Associative containers support efficient lookups and retrievals of elements based on keys.

There are two basic types of associative containers: map and set:

Elements in a map are organized in a key-value (key-value) format: keys serve as indices for elements in the map.

A set contains only keys and effectively supports queries as to whether a certain key exists.

Applicability:

map: When there is a need to store (and even modify) each key associated with its value.

set: Efficiently storing a collection of distinct values.

Associative Container Type	Purpose
map	Associative array, elements stored and retrieved using keys.
set	A variable-sized collection, enabling fast retrieval via keys.
multimap	A map type that supports multiple entries for the same key.
multiset	A set type that supports multiple entries for the same key.
Elements contained in objects of set and map types have distinct keys and do not allow the addition of a second element for the same key.
Note: If a key must correspond to multiple instances, use the `multimap` and `multiset` types.

Introduction to Pair Type

A simple standard library type—pair type, related to associative containers, is defined in the utility header file.

Pair Type	Provided Operations
pair<T1,T2> p1	Creates an empty pair type with two elements of types T1 and T2, initialized to value initialization.
pair<T1,T2> p1(v1,v2)	Creates an empty pair type with two elements of types T1 and T2, where the first member is initialized to v1, and the second member is initialized to v2.
make_pair(v1,v2)	Creates a new pair object with types corresponding to v1 and v2 values.
p1 < p2	Performs a less-than comparison between two pair objects, following dictionary order: if p1.first < p2.first or !(p2.first < p1.first) && p1.second < p2.second, it returns true.
p1 = p2	If the first and second members of two pair objects are equal, the objects are considered equal, using their elements’ == operator.
p.first	Returns the public data member named first from p.
p.second	Returns the public data member named second from p.

Creating and Initializing Pairs

Pair contains two data values. Like containers, a pair is also a template type.
When creating a pair object, two type names must be provided: the type names for the two data members in the pair, and these types do not have to be the same.

// first is string, second is int.
pair<string,int> strint;
// first and second are int.
pair<int,int> twoint;
// first is string, second is vector<int>
pair<string,vector<int>> line;

Note: If no initialization is provided during the creation of the pair object, the default constructor is called, applying value initialization to its members.
Alternatively, each member can be initialized during definition:

1 2	// Initializes twostr.first to "vision" and twostr.second to "smile". pair<string,string> twoste("vision","smile");

Using pair types can be quite cumbersome; if multiple identical pair objects need to be defined, typedef can simplify the declaration:

1
2
3

typedef pair<string,string> twostr;
twostr VS("vision","smile");
twostr HelloWorld("Hello","World");

Generating New Pair Objects

In addition to constructors, the standard library defines a make_pair function that generates a new pair object from the two arguments passed to it.

Example: Creating a new pair object and assigning it to an existing pair object:

// Create a pair object
pair<string,string> next_twostr;
// Create two string objects for input (parameters of make_pair)
string first,second;
// Read two string objects and create a new pair object using make_pair and assign it to next_twostr.
while(cin >> first >> second)
	next_twostr = make_pair(first,second);

Since the pair’s data is public, it can be directly read via input.

1 2	pair<string,string> next_twostr; cin >> next_twostr.first >> next_twostr.second;

Exercises

10.1 Write a program that reads a series of string objects and int data, storing each pair in a pair object, then stores these pair objects in a vector object.

#include <iostream>
#include <vector>
#include <string>
#include <utility>
using namespace std;
int main(void)
{
	pair<string,int> strint;
	vector< pair<string,int> > vectwostr;
	while(cin >> strint.first >> strint.second){
	    vectwostr.push_back(strint);
	    if(strint.second == 0)
            break;
	}
	cout << "Output:" << endl;
	for(vector< pair<string,int> >::iterator begin = vectwostr.begin(); 
	    begin != vectwostr.end(); begin++){
		//(*begin).first, before using the dot operator on an iterator, we need to dereference it
		//because the dot operator has higher precedence than dereference, use parentheses or begin->first.
		cout << (*begin).first << " " << (*begin).second << endl;
	}
	return 0;
}

10.2 In the previous exercise, at least three methods can be used to create pair objects. Write three versions of the program, each using a different method to create pair objects. Which method do you think is easier to write and understand, and why?

string teststr = "Hello";
int testint = 11;
pair<string,int> one;
pair<string,int> two(teststr,testint);
pair<string,int> three = make_pair(teststr,testint);

Answer: I find the third method, pair<string,int> three = make_pair(teststr,testint);, to be easier to write and understand because it explicitly calls the make_pair function, clearly generating a pair object.

Associative Containers

Associative containers share most—but not all—of the operations available in sequential containers.

Associative containers do not offer front, push_front, pop_front, back, push_back, and pop_back operations.

Arranging Elements Based on Keys

The same operations provided for sequential containers have been redefined their meanings and return types in associative containers, where the difference lies in the use of keys.

Container elements are arranged based on their keys: When traversing an associative container, we can ensure that elements are accessed in order of their keys, completely independent of the positions in which elements are stored in the container.

Exercises

10.3 Describe the difference between associative containers and sequential containers.

Answer: The essential difference between associative containers and sequential containers is that associative containers use keys to store and retrieve elements, while sequential containers do so based on the order of their positions within the container.

10.4 Provide examples of situations suitable for using the types list, vector, deque, map, and set.

List is suitable when rapid and efficient insertion and deletion of elements are needed at any location (without moving any other elements) but does not require random access (accessing an element requires traversing from the head).
Vector is suitable when random access (via index) is needed and does not require random insertion or deletion.
Deque is suitable for operations requiring rapid insertion and deletion from both ends of the queue but also does not require random insertion/deletion while supporting random access to all elements.
Map is suitable for storing associated data, such as names and phone numbers.
Set is suitable for situations involving collections of keys, such as blacklists.

Map Containers

A map is a pair of keys and values.
Map types are typically understood as associative arrays: they use keys to retrieve a value, much like built-in array types do.
The association lies in the fact that the value of the elements is associated with a specific key, rather than obtained through the position of the element in the array.

Defining Map Objects

To use map objects, one must include the map header file.

When defining map objects, it is necessary to specify both the key and value types.

1 2	// Define a map object named strint, indexed by key of type string, with an associated value of type int. map<string,int> strint;

Key Type Constraints

When using associative containers, each key has a type as well as an associated comparison function. By default, the standard library uses the < operator defined for the key types for comparison.
We will introduce how to override the default operator and provide custom operator functions in the Object-Oriented Programming: Using Handles section.

Note: The comparison function must define strict weak ordering on the key types.
Understanding strict weak ordering involves the “less-than” relationship defined for key type data. However, the comparison function can be designed more complex if needed.

When a key is compared to itself, it will always yield a false result.
There must be no mutual “less-than” situations when comparing two keys.
If k1 < k2, k2 < k3, then k1 must be less than k3.
For two keys, if there is no “less-than” relationship between them, the container will treat them as identical keys.

Any key values used as keys in a map object can access their associated data.

Note:
The key type must define the < operator, and it must work “properly”.
The only constraint on key types is that they must support the < operator, while support for other relational or equality operators is not required.