Tuesday, February 4, 2014

string stl container c++

Templates Parameter : Standard Template Library Tutorial, ccplusplus.com

Other STL Containers

The STL is a framework. In addition to the standard container classes it allows you to use other data structures as containers. You can use strings or ordinary arrays as STL containers, or you can write and use special containers that meet special needs. Doing this has the advantage that you can benefit from algorithms, such as sorting or merging, for your own type.

There are three different approaches to making containers "STL-able":
  1. The invasive approach
    You simply provide the interface that ah STL container requires. In particular, you need the usual member functions of containers such as begin() and end(). This approach is invasive because it requires that a container be written in a certain way.
  2. The noninvasive approach
    You write or provide special iterators that are used as an interface between the algorithms and special containers. This approach is noninvasive. All it requires is the ability to step through all of the elements of a container, an ability that any container provides in some way.
  3. The wrapper approach
    Combining the two previous approaches, you write a wrapper class that encapsulates any data structure with an STL container-like interface.
This subsection first discusses strings as a standard container, which is an example of the invasive approach. It then covers an important standard container that uses the noninvasive approach: ordinary arrays. 

However, you can also use the wrapper approach to access data of an ordinary array. Finally, this section subdiscusses some aspects of an important container that is not part of the standard: a hash table.

Whoever wants to write an STL container might also support the ability to get parameterized for different allocators. The C++ standard library provides some special functions and classes for programming with allocators and uninitialized memory.

Strings as STL Containers

The string classes of the C++ standard library are an example of the invasive approach of writing STL containers. Strings can be considered containers of characters. The characters inside the string build a sequence over which you can iterate to process the individual characters. Thus, the standard string classes provide the container interface of the STL. They provide the begin() and end() member functions, which return random access iterators to iterate over a string. They also provide some operations for iterators and iterator adapters. For example, push_back() is provided to enable the use of back inserters.

Note that string processing from the STL's point of view is a bit unusual. This is because normally you process strings as a whole object (you pass, copy, or assign strings). However, when individual character processing is of interest, the ability to use STL algorithms might be helpful. For example, you could read the characters with istream iterators or you could transform string characters, such as make them uppercase or lowercase. In addition, by using STL algorithms you can use a special comparison criterion for strings. The standard string interface does not provide that ability.

Ordinary Arrays as STL Containers

You can use ordinary arrays as STL containers. However, ordinary arrays are not classes, so they don't provide member functions such as begin() and end(), and you can't define member functions for them. Here, either the noninvasive approach or the wrapper approach must be used.

Using Ordinary Arrays Directly

Using the noninvasive approach is simple. You only need objects that are able to iterate over the elements of an array by using the STL iterator interface. Actually, such iterators already exist: ordinary pointers. It was a design decision of the STL to use the pointer interface for iterators so that you could use ordinary pointers as iterators. This again shows the generic concept of pure abstraction: Anything that behaves like an iterator is an iterator. In fact, pointers are random access iterators. The following example demonstrates how to use ordinary arrays as STL containers:

You must be careful to pass the correct end of the array, as it is done here by using coll+6. And, as usual, you have to make sure that the end of the range is the position after the last element.

The output of the program is as follows:

An Array Wrapper

In his book The C++ Programming Language, 3rd edition, Bjarne Stroustrup introduces a useful wrapper class for ordinary arrays. It is safer and has no worse performance than an ordinary array. It also is a good example of a user-defined STL container. This container uses the wrapper approach because it offers the usual container interface as a wrapper around the array.

The class carray (the name is short for "C array" or for "constant size array") is defined as follows:

Here is an example of the usage of the carray class:

As you can see, you can use the general container interface operations (begin(), end(), and operator [ ]) to manipulate the container directly. Therefore, you can also use different operations that call begin() and end(), such as algorithms and the auxiliary function PRINT_ELEMENTS(.

The output of the program is as follows:

Hash Tables

One important data structure for collections is not part of the C++ standard library: the hash table. There were suggestions to incorporate hash tables into the standard; however, they were not part of the original STL and the committee decided that the proposal for their inclusion came too late. (At some point you have to stop introducing features and focus on the details. Otherwise, you never finish the work.)

Nevertheless, inside the C++ community several implementations of hash tables are available. Libraries typically provide four kinds of hash tables: hash_set, hash_multiset, hash_map, and hash_multimap. According to the other associative containers, the multi versions allow duplicates and maps contain key/value pairs.

See Also:


No comments:

Post a Comment