• Choose a category
• All
• Classic-Fiction

By Root 1059 0

vector will go out of scope at the end of the function, C++11 will use move semantics to avoid copying. This makes returning the vector by value in C++11 very efficient.

Here is some code that tests find_all(). The type of the all variable will be vector::iterator>. After finding iterators to all the elements, the test code counts the number of elements found, which is the number of iterators in all. Then, it iterates through the returned iterators, printing each element:

vector vec = {3, 4, 5, 4, 5, 6, 5, 8};

auto all = find_all(vec.begin(), vec.end(), [](int i){return i==5;});

cout << "Found " << all.size() << " matching elements: ";

for (auto it : all) {

cout << *it << " ";

}

Code snippet from WritingAlgorithms\FindAll.cpp

The output is as follows:

Found 3 matching elements: 5 5 5

Iterator Traits

Some algorithm implementations need additional information about their iterators. For example, they might need to know the type of the elements referred to by the iterator in order to store temporary values, or perhaps they want to know whether the iterator is bidirectional or random access.

C++ provides a class template called iterator_traits that allows you to find this info. You instantiate the iterator_traits class template with the iterator type of interest, and access one of five typedefs: value_type, difference_type, iterator_category, pointer, and reference. For example, the following template function declares a temporary variable of the type to which an iterator of type IteratorType refers. Note the use of the typename keyword in front of the iterator_traits line. Chapter 12 explains that you must specify typename explicitly whenever you access a type based on one or more template parameters. In this case, the template parameter IteratorType is used to access the value_type type:

#include

template

void iteratorTraitsTest(IteratorType it)

{

typename std::iterator_traits::value_type temp;

temp = *it;

cout << temp << endl;

}

Code snippet from WritingAlgorithms\IteratorTraitsTest.cpp

This function can be tested with the following test code:

vector v;

v.push_back(5);

iteratorTraitsTest(v.begin());

With this test code, the variable temp in the iteratorTraitsTest() function will be of type int. The output is as follows:

5

The C++11 auto keyword can be used to simplify the previous example. The variable temp will still be of type int:

#include

template

void iteratorTraitsTest(IteratorType it)

{

auto temp = *it;

cout << temp << endl;

}

Code snippet from WritingAlgorithms\IteratorTraitsTest.cpp

Writing an STL Container

The C++ standard contains a list of requirements that any container must fulfill in order to qualify as an STL container.

Additionally, if you want your container to be sequential (like a vector), associative (like a map), or unordered associative (like an unordered_map) it must conform to supplementary requirements.

Our suggestion when writing a new container is to write the basic container first following the general STL rules such as making it a class template, but without worrying too much about the specific details of STL conformity. After you’ve developed the implementation, you can add the iterator and methods so that it can work with the STL framework. This section takes that approach to develop a hashmap.

A Basic Hashmap

C++11 supports unordered associative containers, also called hash tables. These are discussed in Chapter 12. However, previous versions of C++ did not include hash tables. Unlike the STL map and set, which provide logarithmic insertion, lookup, and deletion times, a hash table provides constant time insertion, deletion, and lookup in the average case, linear in the worst case. Instead of storing elements in sorted order, it hashes, or maps, each element to a particular bucket. As long as the number of elements stored isn’t significantly greater than the number of buckets, and the hash function distributes the elements uniformly between