Sequential Containers

Overview of the Sequential Containers

except vector, string and array, there are some new sequential containers: deque, list and forward_list. Their characteristics show in next table:

Type	Characteristics
deque	Double-end queue, support random access
list	Doubly linked list, only support sequential access
forward_list	Singly linked list, only support sequential access

With the exception of array, which is a fixed-size container, the containers provide efficient, flexible memory management. We can add and remove elements, growing and shrinking the size of the container. string and vector hold their elements in contiguous memory. Because elements are contiguous, it is fast to compute the address of an element from its index. However, adding or removing elements in the middle of one of these containers need take more time. The list and forward_list containers are designed to make it fast to add or remove an element anywhere in the container. In exchange, these types do not support random access to elements. A deque is a more complicated data structure. Like string and vector, deque supports fast random access and adding or removing elements in the middle of a deque is a (potentially) expensive operation. However, adding or removing elements at either end of the deque is a fast operation, comparable to adding an element to a list or forward_list.

Container Library Overview

The operations on the container types form a kind of hierarchy, this table show the type of container:

member type	definition
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)
reference	value_type&
pointer	allocator_traits<allocator_type>::pointer
iterator	a random access iterator to value_type
const_(reference\	pointer\	iterator)	~
difference_type	a signed integral type, identical to distance between two iterator
size_type	an unsigned integral type that can represent any non-negative value of difference_type

This table show the normal operation:

method	definition
begin	Return iterator to beginning
end	Return iterator to end
cbegin	Return const iterator to beginning
cend	Return const iterator to end
swap	swap elements in two containers
size	the number of elements in container
max_size	the max number of elements container can hold
capacity	Return size of allocated storage capacity

The containers are class templates. As with vectors, we must supply additional information to generate a particular container type. Almost any type can be used as the element type of a sequential container. In particular, we can define a container whose element type is itself another container. We define such containers exactly as we do any other container type: We specify the element type (which in this case is a container type) inside angle brackets:

vector<vector<string>> lines; // vector of vectors
vector<vector<string> >;
//Older compilers may require a space between the angle brackets

Iterators

An iterator range is denoted by a pair of iterators each of which refers to an element, or to one past the last element, in the same container. These two iterators, often referred to as begin and end—or (somewhat misleadingly) as first and last—mark a range of elements from the container. The name last, although commonly used, is a bit misleading, because the second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element.

This element range is called a left-inclusive interval. The standard mathematical notation for such a range is [begin, end).

begin and end Members

The begin and end operations yield iterators that refer to the first and one past the last element in the container. These iterators are most often used to form an iterator range that encompasses all the elements in the container. The versions with an r return reverse iterators. Those that start with a c return the const version of the related iterator:

list<string> a = {"Milton", "Shakespeare", "Austen"};
auto it1 = a.begin(); // list<string>::iterator
auto it2 = a.rbegin(); // list<string>::reverse_iterator
auto it3 = a.cbegin(); // list<string>::const_iterator
auto it4 = a.crbegin();// list<string>::const_reverse_iterator

Assignment and swap

The assignment-related operators act on the entire container. The assignment operator replaces the entire range of elements in the left hand container with copies of the elements from the right-hand operand:

int main() {
    vector<int> k(10, 20);
    vector<int> m(5, 40);
    k = m;
    for (auto i = k.begin(); i != k.cend(); i++) {
        cout << *i << " ";
    }
    return 0;
}
//output
40 40 40 40 40 

The assignment operator requires that the left-hand and right-hand operands have the same type. It copies all the elements from the right-hand operand into the left-hand operand. The sequential containers (except array) also define a member named assign that lets us assign from a different but compatible type, or assign from a subsequence of a container.

int main() {
    vector<char> k(10, 'A');
    vector<int> m(5, 40);
    k.assign(m.begin(), m.end());
    for (auto i = k.begin(); i != k.cend(); i++) {
        cout << *i << "";
    }
    return 0;
}
//output
( ( ( ( ( 

A second version of assign takes an integral value and an element value. It replaces the elements in the container with the specified number of elements, each of which has the specified element value:

list<string> slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya !

The swap operation exchanges the contents of two containers of the same type. After the call to swap, the elements in the two containers are interchanged:

int main() {
    vector<int> k(5, 20);
    vector<int> m(5, 40);
    k.swap(m);
    for (auto i = k.begin(); i != k.cend(); i++) {
        cout << *i << " ";
    }
    for (auto i = m.begin(); i != m.cend(); i++) {
        cout << *i << " ";
    }
    return 0;
}
//output
40 40 40 40 40 
    20 20 20 20 20 

Sequential Container Operations

Add elements

Excepting array, all of the library containers provide flexible memory management. We can add or remove elements dynamically changing the size of the container at run time.

push_back appends an element to the back of a vector. Aside from array and forward_list, every sequential container (including the string type) supports push_back. The call to push_back creates a new element at the end of container, increasing the size of container by 1. The value of that element is a copy of word. The type of container can be any of list, vector, or deque. Because string is just a container of characters, we can use push_back to add characters to the end of the string:

int main() {
    string s1 = "hell";
    s1.push_back('o'); // s1 is hello
    return 0;
}

In addition to push_back, the list, forward_list, and deque containers support an analogous operation named push_front. This operation inserts a new element at the front of the container:

int main() {
    deque<int> k(1, 5);
    k.push_back(6);
    k.push_front(4);
    return 0;
}
// k is a deque with elemrnts 4,5,6

More generally, the insert members let us insert zero or more elements at any point in the container. The insert members are supported for vector, deque, list, and string. Each of the insert functions takes an iterator as its first argument. The iterator indicates where in the container to put the element(s).

int main() {
    vector<int> k = { 1,2,4,5 };
    auto it = k.begin();
    it += 2;
    k.insert(it, 3);
    return 0;
}
//k is a vector with elements 1,2,3,4,5

The arguments to insert that appear after the initial iterator argument are analogous to the container constructors that take the same parameters. The version that takes an element count and a value adds the specified number of identical.

int main() {
    vector<int> k;
    // k = {1}
    k.insert(k.end(), 1, 1);
    // k = {1,2,3}
    k.insert(k.end(), { 2,3 });
    // k = {1,2,3,4,5}
    vector<int> t = { 4,5 };
    k.insert(k.end(), t.begin(), t.end());
    return 0;
}

Under the new standard, the versions of insert that take a count or a range return an iterator to the first element that was inserted. (In prior versions of the library, these operations returned void.) We can use the value returned by insert to repeatedly insert elements at a specified position in the container:

int main() {
    vector<int> k;
    auto iter = k.begin();
    for (int i = 0; i < 5; i++) {
        iter = k.insert(iter, i);
    }
    return 0;
}
// k = {4,3,2,1,0}

The new standard introduced three new members—emplace_front, emplace, and emplace_back—that construct rather than copy elements. These operations correspond to the push_front, insert, and push_back operations in that they let us put an element at the front of the container, in front of a given position, or at the back of the container, respectively.

c.emplace_back("978-0590353403", 25, 15.99);
c.push_back(Sales_data("978-0590353403", 25, 15.99));

The call to emplace_back and the second call to push_back both create new Sales_data objects. In the call to emplace_back, that object is created directly in space managed by the container. The call to push_back creates a local temporary object that is pushed onto the container.

Accessing Elements

Each sequential container, including array, has a front member, and all except forward_list also have a back member. These operations return a reference to the first and last element, respectively:

if (!c.empty()) {
    // val and val2 are copies of the value of the first element in c
    auto val = *c.begin(), val2 = c.front();
    // val3 and val4 are copies of the of the last element in c
    auto last = c.end();
    auto val3 = *(--last); // can't decrement forward_list iterators
    auto val4 = c.back(); // not supported by forward_list
}

The containers that provide fast random access (string, vector, deque, and array) also provide the subscript operator []. As we’ve seen, the subscript operator takes an index and returns a reference to the element at that position in the container. The index must be “in range” (i.e., greater than or equal to 0 and less than the size of the container). It is up to the program to ensure that the index is valid; the subscript operator does not check whether the index is in range. Using an out-of-range value for an index is a serious programming error, but one that the compiler will not detect.

If we want to ensure that our index is valid, we can use the at member instead. The at member acts like the subscript operator, but if the index is invalid, at throws an out_of_range exception.

Erasing Elements

Just as there are several ways to add elements to a (no-array) container there are also several ways to remove elements.

The pop_front and pop_back functions remove the first and last elements, respectively. Just as there is no push_front for vector and string, there is also no pop_front for those types. Similarly, forward_list does not have pop_back. Like the element access members, we may not use a pop operation on an empty container.

int main() {
    deque<int> k = { 1,1,2,3,3 };
    k.pop_back();
    k.pop_front();
    return 0;
}
// k = {1,2,3}

The erase members remove element(s) at a specified point in the container. We can delete a single element denoted by an iterator or a range of elements marked by a pair of iterators. Both forms of erase return an iterator referring to the location after the (last) element that was removed.

int main() {
    list<int> lst = { 0,1,2,3,4,5,6,7,8,9 };
    auto it = lst.begin();
    while (it != lst.end())
        if (*it % 2) // if the element is odd
            it = lst.erase(it); // erase this element
    else
        ++it;
    return 0;
}

delete a range of elements:

int main() {
    vector<int> lst = { 0,1,2,3,4,5,6,7,8,9 };
    auto it_beg = lst.begin();
    auto it_end = lst.begin() + 5;
    lst.erase(it_beg, it_end);
    return 0;
}
// lst = {5,6,7,8,9}

Resizing a Container

With the usual exception of arrays, we can use resize, to make a container larger or smaller. If the current size is greater than the requested size, elements are deleted from the back of the container; if the current size is less than the new size, elements are added to the back of the container:

list<int> ilist(10, 42); // ten ints: each has value 42
ilist.resize(15); // adds five elements of value 0 to the back of ilist
ilist.resize(25, -1); // adds ten elements of value -1 to the back of ilist
ilist.resize(5); // erases 20 elements from the back of ilist

How a vector Grows

To support fast random access, vector elements are stored contiguously—each element is adjacent to the previous element. If there is no room for the new element, the container can’t just add an element
somewhere else in memory—the elements must be contiguous. Instead, the container must allocate new memory to hold the existing elements plus the new one, move the elements from the old location into the new space, add the new element, and deallocate the old memory. If vector did this memory allocation and deallocation each time we added an element, performance would be unacceptably slow.

To avoid these costs, library implementors use allocation strategies that reduce the number of times the container is reallocated. It is important to understand the difference between capacity and size. The size of a container is the number of elements it already holds; its capacity is how many elements it can hold before more space must be allocated.

A vector may be reallocated only when the user performs an insert operation when the size equals capacity or by a call to resize or reserve with a value that exceeds the current capacity. How much memory is allocated beyond the specified amount is up to the implementation.

int main() {
    vector<int> ivec(50, 1);
    cout << ivec.capacity() << endl;
    ivec.push_back(1);
    cout << ivec.capacity() << endl;
    return 0;
}
// in my computer the output is
// 50
// 100

Additional string Operations

Substring And Replace

The substr operation returns a string that is a copy of part or all of the original string. We can pass substr an optional starting position and count:

string s("hello world");
string s2 = s.substr(0, 5); // s2 = hello
string s3 = s.substr(6); // s3 = world
string s4 = s.substr(6, 11); // s3 = world
string s5 = s.substr(12); // throws an out_of_range exception

The string type supports the sequential container assignment operators and the assign, insert, and erase operations, It also defines additional versions of insert and erase. string provides versions that take an index. The index indicates the starting element to erase or the position before which to insert the given values:

string s = "hello";
// insert five exclamation points at the end of s
// s = “Hello!!!!!!”
s.insert(s.size(), 5, '!');
s.erase(s.size() - 5, 5); // erase the last five characters from s

The string class defines two additional members, append and replace, that can change the contents of a string. The append operation is a shorthand way of inserting at the end:

int main() {
    string s("C++ Primer"); // initialize s and s2 to "C++Primer
    s.append(" 4th Ed.");
    cout << s << endl;
    s.replace(11, 3, "5th");
    cout << s << endl;
    return 0;
}
// output
// C++ Primer 4th Ed.
// C++ Primer 5th Ed.

Find function

The string class provides six different search functions, each of which has four overloaded versions. The next table describes the search members and their definition. Each of these search operations returns a string::size_type value that is the index of where the match occurred. If there is no match, the function returns a static member (§ 7.6, p. 300) named string::npos. The library defines npos as
a const string::size_type initialized with the value -1. Because npos is an unsigned type, this initializer means npos is equal to the largest possible size any string could have.

method	definition
find	Find first occurrence of content in string
rfind	Find last occurrence of content in string
find_first_of	Find any character match in string
find_last_of	Find character in string from the end
find_first_not_of	Find absence of character in string
find_last_not_of	Find non-matching character in string from the end

int main() {
    string s("AA BB AA DD AA BB AA");
    // return the first match position
    auto pos = s.find("AA");
    cout << pos << s.substr(pos) << endl;
    //return the last match position
    pos = s.rfind("AA");
    cout << pos << s.substr(pos) << endl;
    // return the first char match position
    pos = s.find_first_of("DB");
    cout << pos << s.substr(pos) << endl;
    // return the last char match position
    pos = s.find_last_of("DB");
    cout << pos << s.substr(pos) << endl;
    // return the first char not in metch string
    pos = s.find_first_not_of("AB ");
    cout << pos << s.substr(pos) << endl;
    // return the last char not in metch string
    pos = s.find_last_not_of("AD ");
    cout << pos << s.substr(pos) << endl;
    return 0;
}
//output
//0AA BB AA DD AA BB AA
//18AA
//3BB AA DD AA BB AA
//16B AA
//9DD AA BB AA
//16B AA

We can pass an optional starting position to the find operations. This optional argument indicates the position from which to start the search. By default, that position is set to zero. One common programming pattern uses this optional argument to loop through a string finding all occurrences:

string::size_type pos = 0;
// each iteration finds the next number in name
while ((pos = name.find_first_of(numbers, pos))!= string::npos) {
    cout << "found number at index: " << pos << " element is " << name[pos] << endl;
    ++pos; // move to the next character
}

Compare

In addition to the relational operators, the string library provides a set of compare functions that are similar to the C library strcmp function. The function compare returns zero or a positive or negative value depending on whether s is equal to, greater than, or less than the string formed from the given arguments.

int main() {
    std::string str1("green apple");
    std::string str2("red apple");

    if (str1.compare(str2) != 0)
        std::cout << str1 << " is not " << str2 << endl;

    if (str1.compare(6, 5, "apple") == 0)
        std::cout << "still, " << str1 << " is an apple" << endl;

    if (str2.compare(str2.size() - 5, 5, "apple") == 0)
        std::cout << "and " << str2 << " is also an apple" << endl;

    if (str1.compare(6, 5, str2, 4, 5) == 0)
        std::cout << "therefore, both are apples" << endl;

    return 0;
}
//output
//green apple is not red apple
//still, green apple is an apple
//and red apple is also an apple
//therefore, both are apples

previous code show the most common usage, more details you can check this website.

Numeric Conversions

Strings often contain characters that represent numbers. In c++ 11 the new standard introduced several functions that convert between numeric data and library strings:

int main() {
    // converts the double i to its character representation
    // note output the i and s is different
    double i = 42.97538045793466769837795;
    string s = to_string(i);
    cout << i << endl;
    cout << s << endl;
    // converts a string to double
    string k = "1999.9";
    double tod = stod(k);
    // converts a string to int
    string j = "6745";
    int toi = stoi(k);
    return 0;
}

the function that string to numeric type can be think prefix sto add a suffix represent the numeric type, stoi means string to int, stof means string to float. etc…

Container Adaptors

In addition to the sequential containers, the library defines three sequential container adaptors: stack, queue, and priority_queue. An adaptor is a general concept in the library. There are container, iterator, and function adaptors. Essentially, an adaptor is a mechanism for making one thing act like another. A container adaptor takes an existing container type and makes it act like a different type.

Defining an Adaptor

Each adaptor defines two constructors: the default constructor that creates an empty object, and a constructor that takes a container and initializes the adaptor by copying the given container.

deque<int> mydeque = { 1,2,3,4,5 };
// empty stack
stack<int> myst1;
// copies elements from deq into stk
stack<int> myst2(mydeque);

By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector. We can override the default container type by naming a sequential container as a second type argument when we create the adaptor:

int main() {
    vector<string> svec = { "1","2","3","4","5" };
    // empty stack implemented on top of vector
    stack<string, vector<string>> str_stk;
    // str_stk2 is implemented on top of vector and initially holds a copy of svec
    stack<string, vector<string>> str_stk2(svec);
    return 0;
}

1. A stack requires only push_back, pop_back, and back operations, so we can use any of the remaining container types for a stack.
2. A queue adaptor requires back, push_back, front, and push_front, so it can be built on a
   list or deque but not on a vector.
3. A priority_queue requires random access in addition to the front, push_back, and pop_back operations; it can be built on a vector or a deque but not on a list.

Stack Adaptor

The three most common methods in stack are push, pop, top, the push add a element to the top of stack, the pop remove a element to the top of stack, the top return the top of stack.

int main() {
    stack<int> m;
    // add 1,2,3,4,5 by sequential
    for (int i = 0; i < 5; i++) {
        m.push(i);
    }
    // pop elemrnt
    for (int i = 0; i < 5; i++) {
        cout << m.top() << " ";
        m.pop();
    }
    cout << endl;
    return 0;
}
//output
//4 3 2 1 0 

The Queue Adaptors

The queue and priority_queue adaptors are defined in the queue header. The library queue uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back and objects leaving the queue are removed from the front. A restaurant that seats people in the order in which they arrive is an example of a FIFO queue.

The four most common methods in queue are push, pop, front, back, top

1. push: add a element to end of queue
2. pop: remove a element in the head of queue
3. front: return a element from the head of queue
4. back: return a element in the end of queue (only valid in queue)
5. top: return the most priority element in priority_queue (only valid in priority_queue)

A priority_queue lets us establish a priority among the elements held in the queue. Newly added elements are placed ahead of all the elements with a lower priority. A restaurant that seats people according to their reservation time, regardless of when they arrive, is an example of a priority queue. By default, the library uses the < operator on the element type to determine relative priorities. However we can override the default.

int main() {
    queue<int> m;
    // add 1,2,3,4,5 by sequential
    for (int i = 0; i < 5; i++) {
        m.push(i);
    }
    // pop elemrnt
    for (int i = 0; i < 5; i++) {
        cout << m.front() << " ";
        m.pop();
    }
    cout << endl;
    return 0;
}
//0 1 2 3 4