Introduction
The Standard C++ library is the back-bone of most modern C++ applications. It provides elegant, efficient and portable classes, templates and functions to handle a wide variety of development needs ranging from strings and mathematical operations to stream support, complex collection types and locale-aware data processing requirements. Many C++ applications divide functionality between core business-logic components built on the Standard C++ library and compiled across multiple operating systems and OS-specific presentation layers built using control libraries which vary from one platform to another.
As C++ programming moves towards a new standard in the now anachronistically-named C++ 0x (0x indicated that the standard was expected to be finalized in the 200x timeframe), changes to the Standard Library related to the new standard continue to flow into Visual C++, with Visual C++ 2010 shipping with a host of additions to the Standard C++ library. While all the changes are evolutionary rather than revolutionary in nature, they represent an important trend in C++ programming of keeping the language synchronized with industry-standard libraries like Boost. As with previous versions of the Standard C and Standard C++ libraries that ship with Visual C++, the libraries are licensed from Dinkumware.
While it is not documented in the MSDN library, the Standard C++ library additions that ship with Visual C++ 2010 can be disabled by setting #define _HAS_CPP0X
to 0. This is useful if the code needs to be compiled using other C++ compilers that do not have the C++ 0x additions available.
New <Algorithm> Functionality
Visual C++ 2008 had 67 documented algorithms (excluding the Microsoft-specific checked_*
and unchecked_*
extensions), and this has been increased significantly by the addition on 17 new algorithms, as listed below. The MSDN documentation for the algorithm members does a great of describing the behaviour of the newly-introduced functions, but it’s worth calling out some of the particularly useful new algorithms.
New <algorithm> members for Visual C++ 2010
- all_of
- any_of
- copy_if
- copy_n
- find_if_not
- is_heap
- is_heap_until
- is_partitioned
- is_sorted
- is_sorted_until
- minmax
- minmax_element
- move
- move_backwards
- none_of
- partition_copy
- partition_point
The is_sorted
template function is quite useful in determining whether other optimized algorithms such as binary_search and std::includes
can be applied to a particular collection. The binary_search algorithm has a logarithmic complexity (assuming the collection has random-access iterators) compared to the linear complexity of std::search, so for large collections, the performance advantages of binary_search are significant. If a large number of items need to be searched for in a collection, taking the once-off hit to determine if the collection is sorted (and potentially producing a sorted version if the original collection isn’t sorted) can produce a significant performance improvement.
While not as generally applicable as sorted collections, heaped collections are computationally efficient for a number of important tasks such as efficient graph navigation. For those whose fundamental data structures knowledge is a little rusty, a heap is tree structure where the children of each node are less than (in the case of a max-heap) than the parent. The STL uses a heap for implementing the priority_queue
, which provides a queue data structure where the element at the front of the queue is always the largest (or highest priority) element. Heaps are represented as arrays by sequentially including each tree level in the collection, so for the heap shown in Figure 1, the array representation is { 70,55,68,11,29,26,27}.
Figure 1. Max Heap
The new is_heap
function can be used to check whether a particular collection represents a heap:
using namespace std; int v1[] = { 70,55,68,11,29,26,27} ; bool isV1Heap = is_heap(begin(v1), end(v1)); //true int v2[] = { 70,55,71,11,29,26,27} ; bool isV2Heap = is_heap(begin(v2), end(v2)); //false - 71 is greater than 70, //and should be higher in the heap
STL Forward_List
The art of using the STL correctly is choosing the collection that most elegantly and efficiently models the real-world collection that the application is describing. Prior to C++ 0x, the STL had not implemented a signally-linked list, with the std::list
template maintaining both a forward and backward pointer to each element within the list. While this is not a problem outside performance-critical scenarios, for the usage scenario where a forward-only list is needed, a doubly-linked list is inefficient both from a performance perspective during element insertion and removal (as both a back and forward pointer need to be modified for each operation), and from a storage perspective. The introduction of the forward_list
introduces no new functionality, and exists solely for performance reasons.
The criteria for using the forward_list
collection are:
- Random element access is not required, or required very infrequently.
- Frequent element insertion or removal is required at many locations across the collection. The queue and dequeue collection are preferable if element insertion and removal are limited to either end of the collection.
- Forward-only element navigation is required. In addition to some minor difference between member function from the list template, the obvious limitation is the lack of the–operator on the
forward_list::iterator
class.
The insert and erase member function of list cannot be efficiently implemented in forward_list
, as the lack of backward navigation prevents efficient in-place insertion or removal–its only possible to insert after the current iterator location– not at it. To emphasise that insert and erase behave differently, the member functions have been renamed to insert_after
and erase_after
in forward_list
. The code snippet below demonstrates the difference in element insertion between list and forward_list
.
forward_list<int>::iterator fli = fl.begin(); ++fli; fl.insert_after(fli, 4); //1,2,4,3 list<int> l; l.push_front(3); l.push_front(2); l.push_front(1); list<int>::iterator li = l.begin(); ++li; l.insert(li, 4); //1,4,2,3
Conclusion
Keeping Visual C++ up to date with advances in the C++ is a critical element in maintaining the products relevance to the C++ community. Microsoft copped justified criticism in the 90s and early 2000s for first focusing on their own toolkits like MFC and then ATL, and after that neglecting C++ while focusing on managed compliers such as C#. Visual C++ 2008 and onward has seen this perceived trend of neglect fully addressed, and Visual C++ 2010 is a great tool for Standard C++ development. The additions to algorithm and the STL collections that ship with Visual C++ 2010 address a number of specific development requirements, and can be used to improve both the performance and readability of a C++ application.