Is Cstring In The Standard Template Librarty

STL: The Standard Template Library

(See libcp.htm for information about the header files and namespaces used below.)

A container is actually a handle that manages a potentially complicated C-style data construction such equally an AVL tree, hash tabular array, or doubly linked list (see the Handle-Body idiom discussed in chapter iv). Fortunately, implementing these data structures is largely an bookish do these days (just a skilful ane). This is considering the standard C++ library now comes with a collection of container templates chosen the Standard Template Library.

Containers can be roughly divided into 2 types: sets and sequences. Retrieve from mathematics that a sequence is an ordered set. Thus, the sequence (a, b, c) is unlike from the sequence (c, b, a), while the set {a, b, c} is the same as the ready {c, b, a}. Call back also that multiple occurrences of an element are disregarded in a fix, but not a sequence. So the sequence (a, a, b, c) is different from the sequence (a, b, c), while the set {a, a, b, c} is the same as the set {a, b, c}.

Here is a list of the STL containers:

Sequences
vector<Storable> (random admission shop)
string (derived from vector<char>)
list<Storable> (sequential access store)
deque<Storable> (base form shop for stacks and queues)
pair<Key, Storable> (elements of a map)
Sequence Adaptors (temporal access stores)
stack<Storable> (LIFO store)
queue<Storable> (FIFO store)
priority_queue<Storable> (uses Storable::operator<())
Sets
set up<Storable>
multiset<Key> (multiple occurences allowed)
map<Primal, Storable> (a set of pairs)
multimap<Fundamental, Storable> (a multiset of pairs)

Here are some of the header files you need to include if you want to utilize STL containers:

#include <string>
#include <vector>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <map>
using namespace std;

C++ Strings

A C string is simply a static or dynamic assortment of characters:

typedef char String80[80]; // static arrays
typedef char* String; // pointers to dynamic arrays

A C string literal is a sequence of characters bracketed by double quotes (backslash is the escape character):

String path = "c:\\data\\info.doc";
String80 prompt = "Type \"q\" to quit\n";

C strings are always terminated by the NUL character (i.due east., ASCII lawmaking 0). The standard C library provides functions for manipulating C strings. These are declared in <cstring>:

int strcmp( const char* string1, vonst char* string2 );
size_t strlen( const char* cord );
char* strcpy( char* dest, char* source );
char* strcat( char* dest, char* source );
// etc.

Because C strings don't bank check for out-of-range indices, and because they don't classify and deallocate retentivity for themselves, programmers should use C++ strings instead. C++ strings are instances of the string grade declared in <string>, which is role of the std namespace:

#include <string>
using namespace std;

Nosotros can use C strings to initialize C++ strings:

cord s1("California"), s2, s3;
s2 = " Nevada ";

The third C++ string, s3, is currently empty:

cout << boolalpha << s3.empty() << endl; // prints "true"

C++ strings tin be read from an input stream using the extraction operator and written to an output stream using the insertion operator.

cout << "Enter 3 strings separated past white infinite: ";
cin >> s1 >> s2 >> s3;
cout << "You lot entered: " << s1 << ' ' << s2 << ' ' << s3 << endl;

The size() and length() fellow member functions both render the number of characters in a C++ cord:

cout << s1.length() + s2.size() << endl; // prints 16

In that location are several means to access the characters in a C++ string. One manner is to use the subscript operator:

for(int i = 0; i < s1.size(); i++) cout << s1[i] << ' ';

Unfortunately, the subscript operator doesn't cheque for index range errors. For this we must employ the at() fellow member function, which throws an out_of_range exception when the index is too big:

try
{
cout << s1.at(500) << endl; // oops, index besides big!
}
grab(out_of_range e)
{
cerr << due east.what() << endl; // prints "invalid string position"
}

Assigning s2 to s3:

s3 = s2;

automatically copies s2 to s3. We can verify this past modifying the showtime character of s3:

s3[0] = 'n'; // alter 'N' to 'north'

then printing s2 and noticing that it is unchanged:

cout << s2 << endl; // prints " Nevada "

One of the best features of C++ strings is that they automatically grow to accommodate actress characters:

s3 = "Nevada is in the USA ";

We don't need to bother with the awkward C library string manipulation functions. C++ strings can be compared and concatenated using infix operators:

s1 == s2; // = false
s1 != s2; // = true
s1 <= s2; // = true
s3 = s1 + ' ' + "is next to" + ' ' + s2;
// etc.

There are as well many member functions that can be used to find, extract, erase, and supercede substrings:

int pos = s1.find("for"); // pos = 4
s3 = s1.substr(pos, 3); // s3 = "for"
s3 = s1.substr(pos, string::npos); // s3 = "fornia"
s1.replace(pos, 3, "Xx"); // s1 = "CaliXXnia"
s1.erase(pos, 2); // s1 = "Calinia"

The c_str() fellow member function returns an equivalent C string which tin exist used by C library functions:

printf("%s\north", s1.c_str());

There are many more C++ string member functions. The reader should consult online documentation or [STR] for a complete list.

Iterators

Iterators are similar to the smart pointers discussed in Chapter 4, merely an iterator is an object that "points" to an element in a container, cord, or stream. Similar pointers, iterators can exist incremented, decremented, compared, or dereferenced.

For example, we can traverse an assortment using alphabetize numbers:

char msg[] = "Hello Earth";
for (int i = 0; i < strlen(msg); i++)
cout << msg[i] << ' ';

but we could but as hands utilize a pointer to traverse the assortment:

for(char* p = msg; p != msg + strlen(msg); p++)
cout << *p << ' ';

We can traverse a C++ string using index numbers, too:

string msg = "Hello World";
for (int i = 0; i < msg.length(); i++)
cout << msg[i] << ' ';

Just we can't traverse a C++ string using an ordinary pointer, because a cord is but a handle that encapsulates a C string. Instead, we must utilize an iterator to "point" at elements inside of a string.

for(string::iterator p = msg.brainstorm(); p != msg.end(); p++)
cout << *p << ' ';

Iterator declarations must be qualified by the appropriate container class:

string::iterator p;

This is because the iterator grade for a container class is declared inside the container grade annunciation. For instance:

class string
{
public:
course iterator { ... };
class const_iterator { ... };
iterator brainstorm();
iterator end();
// etc.
};

This is done because iterators for strings might be quite unlike for iterators for lists, maps, and deques.

All container classes provide begin() and end() functions. The begin() office returns an iterator that points to the showtime element in the container. The end() part returns an iterator that points to a location just across the concluding chemical element of the container.

C++ iterators tin be regarded as an instantiation of the more general iterator design pattern:

Iterator [Go4]

Other Names

Cursor

Problem

Sharing a data structure such as a linked listing or file is difficult, considering plainly non destructive operations, such as printing the list, can actually be destructive if they motility the list's internal cursor (i.e., the list's pointer to its current chemical element).

Solution

An iterator is an external cursor owned by a client. Modifying an iterator has no consequence on iterators owned by other clients.

Basic Container Operations

Assume c is an STL container, x is a potential container chemical element, and p is an iterator. Here are some of the virtually common operations:

c.begin() = iterator "pointing" to starting time element of c
c.stop() = iterator "pointing" to one past last chemical element
c.front() = kickoff element of c
c.dorsum() = concluding element of c
c.size() = number of elements in c
c.empty() = true if container is empty

c.push_back(x) inserts 10 at end of c
c.push_front(x) inserts x at beginning of c
c.insert(p, x) inserts ten in c before *p

c.pop_front() removes beginning element of c
c.pop_back() removes concluding chemical element of c
c.erase(p) removes *p

Vectors

STL vectors encapsulate dynamic arrays (run across chapter iv). They automatically abound to accommodate any number of elements. The elements in a vector can be accessed and modified using iterators or indices.

To begin, allow's provide a template for press vectors, this will make a nice addition to our utility library. We use a constant iterator:

template <typename Storable>
ostream& operator<<(ostream& os, const vector<Storable>& 5)
{
os << "( ";
vector<Storable>::const_iterator p;
for( p = v.begin(); p != v.stop(); p++)
bone << *p << ' ';
bone << ')';
return os;
}

Hither's how we declare an integer vector:

vector<int> vec;

It'due south piece of cake to add elements to the back of a vector:

vec.push_back(7);
vec.push_back(42);
vec.push_back(19);
vec.push_back(100);
vec.push_back(-xiii);
cout << vec << endl; // prints (7 42 19 100 –13)

It'south also easy to remove elements from the back of a vector:

vec.pop_back(); // removes -13

Of course nosotros tin use the subscript operator to access and modify vector elements:

for(int i = 0; i < vec.size(); i++)
vec[i] = 2 * vec[i]; // double each element

The subscript operator is unsafe. It doesn't check for out of range indices. As with strings, we must u.s.a. the vec.at(i) fellow member function for safe access.

To insert or remove an item from any position in a vector other than the last, we must showtime obtain an iterator that volition point to the insertion or removal position:

vector<int>::iterator p = vec.brainstorm();

Next, we position p:

p = p + two;

Finally, nosotros insert the item using the insert() fellow member function:

vec.insert(p, 777);
cout << vec << endl; // prints (14 84 777 38 200)

Nosotros follow the same procedure to remove an element:

p = vec.begin() + 1;
vec.erase(p);
cout << vec << endl; // prints (14 777 38 200)

Lists

STL lists encapsulate and manage linked lists. Every bit before, nosotros begin with a useful list writer. Only 2 changes are needed from the vector author:

template <typename Storable>
ostream& operator<<(ostream& os, const list<Storable>& v)
{
os << "( ";
list<Storable>::const_iterator p;
for( p = 5.begin(); p != v.cease(); p++)
os << *p << ' ';
os << ")";
render os;
}

Here is how we declare two lists of strings:

list<string> vals1, vals2;

We can add together items to the front or rear of a listing:

vals1.push_back("golf");
vals1.push_back("judo");
vals1.push_back("pool");
vals1.push_back("boxing");
cout << vals1 << endl; // prints (golf judo pool boxing)

vals2.push_front("motorcar");
vals2.push_front("gunkhole");
vals2.push_front("aeroplane");
vals2.push_front("horse");
cout << vals2 << endl; // prints (horse plane boat car)

As with vectors, to insert an detail into a list we first need an iterator pointing to the signal of insertion:

list<string>::iterator p = vals1.begin();
p++; p++; // p + two not allowed!
vals1.insert(p, "yoga");
cout << vals1 << endl; // prints (golf judo yoga pool boxing)

Inserting an item into a list is more than efficient than inserting an particular into a vector. This is considering logically consecutive elements of a dynamic array are also physically consecutive, while linked lists decouple logical and physical order. Therefore, inserting an particular into a vector involves moving all elements higher up the insertion betoken to make space, while inserting an detail into a listing merely involves adjusting a few links.

On the other manus, pointing a vector iterator at an insertion indicate can be done by a unmarried functioning:

p = vals.begin() + n;

While pointing a list iterator at an insertion point involves multiple operations:

for(int i = 0, p = vals1.begin(); i < due north; i++) p++;

In general, C++ iterators belong to categories. While not classes, iterator categories are organized into a specialization hierarchy that can be described by the following form diagram:

Listing iterators are bidirectional. They inherit the ability to be incremented (by 1), compared, and dereferenced. In addition, they can be decremented (past 1). Vector iterators are random access. They inherit all of the functionality of bidirectional iterators, just they can be incremented or decremented by arbitrary amounts.

Removing an item from a linked list can also exist washed by pointing an iterator at the item to be removed:

p = vals2.begin();
p++;
vals2.erase(p);
cout << vals2 << endl; // prints (equus caballus boat automobile)

But we can also remove the first occurrence of an particular in the list by just specifying the item to be removed:

vals1.remove("golf");

The list<> template provides fellow member functions for various useful listing operations:

vals2.reverse();
vals1.sort();
vals1.merge(vals2);
cout << vals1 << endl;
// prints (battle car gunkhole equus caballus judo puddle yoga)

Consult your online documentation or [STR] for a complete list.

Deques, Stacks, and Queues

By themselves, deques (rhymes with "wrecks") are relatively useless. They are optimized for inserting and removing elements at either end, hence are ideal adaptees for stacks and queues. See the discussion on adapters in chapter 4 for details.

Maps

I of the almost mutual and useful information structures is a table. For instance, we used save and load tables in our persistence framework, and we used a image tabular array in our implementation of the Paradigm pattern. (See chapter 5 for details.)

A tabular array is but a listing of pairs (i.e., the rows of the table) of the class:

(Cardinal, VALUE)

Key and VALUE can exist any type, but no 2 pairs in a table take the same fundamental. This requirement allows us to associatively search tables for a pair with a given primal.

For case, a concordance is a tabular array that alphabetically lists every discussion that appears in a document, together with the number of occurrences of that word. For instance, The Harvard Concordance to Shakespeare lists every word e'er written past the Bard. It is ii.5 inches thick and lists well-nigh 29,000 different words! (The King James Bible simply uses 6000 different words.) Nigh ane/12 of the words only occur once, and, opposite to pop belief, the word "gadzooks" never occurs!

Tables tin can be represented in C++ programs by STL maps. A map is a sequence of pairs, where pair is an STL blazon that just binds 2 elements together:

template <typename Key, form VALUE>
struct pair
{
Cardinal first;
VALUE 2nd;
};

For example, hither is a cyclopedia for a certificate containing the single phrase, "to be or not to be":

Here is one way we could build this cyclopedia in C++:

map<string, int> cyclopedia;
concordance["to"] = 2;
concordance["be"] = 2;
cyclopedia["or"] = 1;
concordance["non"] = 1;

Notice that we can use the array subscript operator to insert entries. In a way, a map is like an array indexed by an arbitrary blazon. In fact, if the index isn't a central in the table, a new pair is created with this primal associated to the default or null value of the respective value blazon, and the new pair is inserted into the table. Since the "zero" value for the integer type is 0, we tin can use this fact to create our concordance in a different way:

map<string, int> concordance;
concordance["to"]++;
cyclopedia["be"]++;
cyclopedia["or"]++;
concordance["non"]++;
concordance["to"]++;
concordance["be"]++;

Here are useful template functions for writing pairs and maps:

template <typename Fundamental, typename Value>
ostream& operator<<(ostream& os, const pair<Key, Value>& p)
{
os << '(' << p.first << ", " << p.2nd << ')';
return bone;
}

template <typename Key, typename Value>
ostream& operator<<(ostream& bone, const map<Key, Value>& m)
{
map<Fundamental, Value>::const_iterator p;
for( p = thousand.brainstorm(); p != m.end(); p++) bone << *p << endl;
return os;
}

For example,

cout << concordance;

prints:

(exist, two)
(not, one)
(or, i)
(to, 2)

Putting this together, here's how we tin implement a concordance generator that reads a document from standard input and writes the cyclopedia to standard output (we tin can utilize file redirection to read and write to files):

int primary()
{
string southward;
map<cord, int> concordance;
while (cin >> s) concordance[southward]++;
cout << concordance;
return 0;
}

Unfortunately, searching a tabular array is a trivial awkward using the map<> member functions. If chiliad is a map and k is a primal, then 1000.find(one thousand) returns an iterator pointing to the first pair in m having central == yard, otherwise m.terminate() is returned. We can brand this job easier with the following template function that can be used to discover the value associated with a item primal. The function returns false if the search fails:

template <typename Key, typename Value>
bool notice(Key k, Value& v, const map<Key, Value>& m)
{
map<Key, Value>::iterator p;
p = m.find(k);
if (p == m.end())
render false;
else
{
v = (*p).second;
return truthful;
}
}

Here's how we could learn the word count for a string in our concordance:

int count = 0;
string discussion = "be";
if (find(word, count, concordance))
cout << word << " count = " << count << endl;
else
cout << give-and-take << " not found\n";