vector Overview

vector is defined in the <vector> header file as a class template with two type parameters: the element type to store and an allocator type.

template <class T, class Allocator = allocator<T>> class vector;

The Allocator parameter specifies the type for a memory allocator object that the client can set in order to use custom memory allocation. This template parameter has a default value.

vector<double> doubleVector(10); // Create a vector of 10 doubles.

// Initialize max to smallest number
double max = -numeric_limits<double>::infinity();

for (size_t i = 0; i < doubleVector.size(); i++) {
    cout << "Enter score " << i + 1 << ": ";
    cin >> doubleVector[i];
    if (doubleVector[i] > max) {
        max = doubleVector[i];
    }
}

max /= 100.0;
for (auto& element : doubleVector) {
    element /= max;
    cout << element << " ";
}

vector<double> doubleVector; // Create a vector with zero elements.

// Initialize max to smallest number
double max = -numeric_limits<double>::infinity();

for (size_t i = 1; true; i++) {
    double temp;
    cout << "Enter score " << i << " (-1 to stop): ";
    cin >> temp;
    if (temp == -1) {
        break;
    }
    doubleVector.push_back(temp);
    if (temp > max) {
        max = temp;
    }
}

max /= 100.0;
for (auto& element : doubleVector) {
    element /= max;
    cout << element << " ";
}

vector Details

Now that you’ve had a taste of vectors, it’s time to delve into their details.

vector<int> intVector; // Creates a vector of ints with zero elements

vector<int> intVector(10, 100); // Creates vector of 10 ints with value 100

vector<string> stringVector(10, "hello");

class Element
{
    public:
        Element() {}
        virtual ~Element() = default;
};
…
vector<Element> elementVector;

vector<int> intVector({ 1, 2, 3, 4, 5, 6 });

vector<int> intVector1 = { 1, 2, 3, 4, 5, 6 };
vector<int> intVector2{ 1, 2, 3, 4, 5, 6 };

auto elementVector = make_unique<vector<Element>>(10);

vector<int> intVector(10);
// Other code …
intVector.assign(5, 100);

intVector.assign({ 1, 2, 3, 4 });

vector<int> vectorOne(10);
vector<int> vectorTwo(5, 100);
vectorOne.swap(vectorTwo);
// vectorOne now has 5 elements with the value 100.
// vectorTwo now has 10 elements with the value 0.

vector<int> vectorOne(10);
vector<int> vectorTwo(10);

if (vectorOne == vectorTwo) {
    cout << "equal!" << endl;
} else {
    cout << "not equal!" << endl;
}

vectorOne[3] = 50;

if (vectorOne < vectorTwo) {
    cout << "vectorOne is less than vectorTwo" << endl;
} else {
    cout << "vectorOne is not less than vectorTwo" << endl;
}

equal!
vectorOne is not less than vectorTwo

for (vector<double>::iterator iter = begin(doubleVector);
    iter != end(doubleVector); ++iter) {
    *iter /= max;
    cout << *iter << " ";
}

vector<double>::iterator iter = begin(doubleVector);

iter != end(doubleVector);

*iter /= max;
cout << *iter << " ";

for (auto iter = begin(doubleVector);
    iter != end(doubleVector); ++iter) {
    *iter /= max;
    cout << *iter << " ";
}

vector<string> stringVector(10, "hello");
for (auto it = begin(stringVector); it != end(stringVector); ++it) {
    it->append(" there");
}

vector<string> stringVector(10, "hello");
for (auto& str : stringVector) {
    str.append(" there");
}

vector<type>::const_iterator it = begin(myVector);

vector<type>::iterator it = begin(myVector);

vector<string> stringVector(10, "hello");
for (auto iter = begin(stringVector); iter != end(stringVector); ++iter) {
    cout << *iter << endl;
}

vector<string> stringVector(10, "hello");
for (auto iter = cbegin(stringVector); iter != cend(stringVector); ++iter) {
    cout << *iter << endl;
}

vector<string> stringVector(10, "hello");
for (const auto& element : stringVector) {
    cout << element << endl;
}

vector<int> intVector;
auto iter = end(intVector);
*iter = 10; // BUG! iter doesn't refer to a valid element.

vector<int> vectorOne(10);
vector<int> vectorTwo(10);

// Fill in the vectors.

// BUG! Possible infinite loop
for (auto iter = begin(vectorTwo); iter != end(vectorOne); ++iter) {
    // Loop body
}

vector<int> intVector(10);
auto it = begin(intVector);
it += 5;
--it;
*it = 4;

string str1 = "Hello";
string str2 = "World";

// Create a vector of references to strings.
vector<reference_wrapper<string>> vec{ ref(str1) };
vec.push_back(ref(str2));  // push_back() works as well.

// Modify the string referred to by the second reference in the vector.
vec[1].get() += "!";

// The end result is that str2 is actually modified.
cout << str1 << " " << str2 << endl;

template<typename T>
void printVector(const vector<T>& v)
{
    for (auto& element : v) { cout << element << " "; }
    cout << endl;
}

vector<int> vectorOne = { 1, 2, 3, 5 };
vector<int> vectorTwo;

// Oops, we forgot to add 4. Insert it in the correct place
vectorOne.insert(cbegin(vectorOne) + 3, 4);

// Add elements 6 through 10 to vectorTwo
for (int i = 6; i <= 10; i++) {
    vectorTwo.push_back(i);
}
printVector(vectorOne);
printVector(vectorTwo);

// Add all the elements from vectorTwo to the end of vectorOne
vectorOne.insert(cend(vectorOne), cbegin(vectorTwo), cend(vectorTwo));
printVector(vectorOne);

// Now erase the numbers 2 through 5 in vectorOne
vectorOne.erase(cbegin(vectorOne) + 1, cbegin(vectorOne) + 5);
printVector(vectorOne);

// Clear vectorTwo entirely
vectorTwo.clear();

// And add 10 copies of the value 100
vectorTwo.insert(cbegin(vectorTwo), 10, 100);

// Decide we only want 9 elements
vectorTwo.pop_back();
printVector(vectorTwo);

1 2 3 4 5
6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 6 7 8 9 10
100 100 100 100 100 100 100 100 100

vectorOne.insert(cend(vectorOne), cbegin(vectorTwo), cend(vectorTwo));

vector<int> createVectorOfSize(size_t size)
{
    vector<int> vec(size);
    int contents = 0;
    for (auto& i : vec) {
        i = contents++;
    }
    return vec;
}
…
vector<int> myVector;
myVector = createVectorOfSize(123);

vector<string> vec;

string myElement(5, 'a');  // Constructs the string "aaaaa"
vec.push_back(myElement);

vec.push_back(move(myElement));

vec.push_back(string(5, 'a'));

vec.emplace_back(5, 'a');

vec.push_back(string(5, 'a'));
// Or
vec.emplace_back(5, 'a');

vector<int> vec{ 1,2,3 };
cout << size(vec) << endl;
cout << empty(vec) << endl;

vector<int> vec{ 1,2,3 };
int* data1 = vec.data();
int* data2 = data(vec);

vector Example: A Round-Robin Class

A common problem in computer science is distributing requests among a finite list of resources. For example, a simple operating system could keep a list of processes and assign a time slice (such as 100ms) to each process to let the process perform some of its work. After the time slice is finished, the OS suspends the process and the next process in the list is given a time slice to perform some of its work. One of the simplest algorithmic solutions to this problem is round-robin scheduling. When the time slice of the last process is finished, the scheduler starts over again with the first process. For example, in the case of three processes, the first time slice would go to the first process, the second slice to the second process, the third slice to the third process, and the fourth slice back to the first process. The cycle would continue in this way indefinitely.

Suppose that you decide to write a generic round-robin scheduling class that can be used with any type of resource. The class should support adding and removing resources, and should support cycling through the resources in order to obtain the next one. You could use a vector directly, but it’s often helpful to write a wrapper class that provides more directly the functionality you need for your specific application. The following example shows a RoundRobin class template with comments explaining the code. First, here is the class definition:

// Class template RoundRobin
// Provides simple round-robin semantics for a list of elements.
template <typename T>
class RoundRobin
{
    public:
        // Client can give a hint as to the number of expected elements for
        // increased efficiency.
        RoundRobin(size_t numExpected = 0);
        virtual ~RoundRobin() = default;

        // Prevent assignment and pass-by-value
        RoundRobin(const RoundRobin& src) = delete;
        RoundRobin& operator=(const RoundRobin& rhs) = delete;

        // Explicitly default a move constructor and move assignment operator
        RoundRobin(RoundRobin&& src) = default;
        RoundRobin& operator=(RoundRobin&& rhs) = default;

        // Appends element to the end of the list. May be called
        // between calls to getNext().
        void add(const T& element);

        // Removes the first (and only the first) element
        // in the list that is equal (with operator==) to element.
        // May be called between calls to getNext().
        void remove(const T& element);

        // Returns the next element in the list, starting with the first,
        // and cycling back to the first when the end of the list is
        // reached, taking into account elements that are added or removed.
        T& getNext();
    private:
        std::vector<T> mElements;
        typename std::vector<T>::iterator mCurrentElement;
};

As you can see, the public interface is straightforward: only three methods plus the constructor and destructor. The resources are stored in the vector called mElements. The iterator mCurrentElement always refers to the element that will be returned with the next call to getNext(). If getNext() hasn’t been called yet, mCurrentElement is equal to begin(mElements). Note the use of the typename keyword in front of the line declaring mCurrentElement. So far, you’ve only seen that keyword used to specify template parameters, but there is another use for it. You must specify typename explicitly whenever you access a type based on one or more template parameters. In this case, the template parameter T is used to access the iterator type. Thus, you must specify typename. This is another example of arcane C++ syntax.

The class also prevents assignment and pass-by-value because of the mCurrentElement data member. To make assignment and pass-by-value work, you would have to implement an assignment operator and copy constructor and make sure mCurrentElement is valid in the destination object.

The implementation of the RoundRobin class follows with comments explaining the code. Note the use of reserve() in the constructor, and the extensive use of iterators in add(), remove(), and getNext(). The trickiest aspect is handling mCurrentElement in the add() and remove() methods.

template <typename T> RoundRobin<T>::RoundRobin(size_t numExpected)
{
    // If the client gave a guideline, reserve that much space.
    mElements.reserve(numExpected);

    // Initialize mCurrentElement even though it isn't used until
    // there's at least one element.
    mCurrentElement = begin(mElements);
}

// Always add the new element at the end
template <typename T> void RoundRobin<T>::add(const T& element)
{
    // Even though we add the element at the end, the vector could
    // reallocate and invalidate the mCurrentElement iterator with
    // the push_back() call. Take advantage of the random-access
    // iterator features to save our spot.
    int pos = mCurrentElement - begin(mElements);

    // Add the element.
    mElements.push_back(element);

    // Reset our iterator to make sure it is valid.
    mCurrentElement = begin(mElements) + pos;
}

template <typename T> void RoundRobin<T>::remove(const T& element)
{
    for (auto it = begin(mElements); it != end(mElements); ++it) {
        if (*it == element) {
             // Removing an element invalidates the mCurrentElement iterator
             // if it refers to an element past the point of the removal.
             // Take advantage of the random-access features of the iterator
             // to track the position of the current element after removal.
            int newPos;

            if (mCurrentElement == end(mElements) - 1 &&
                mCurrentElement == it) {
                 // mCurrentElement refers to the last element in the list,
                 // and we are removing that last element, so wrap back to
                 // the beginning.
                newPos = 0;
            } else if (mCurrentElement <= it) {
                 // Otherwise, if mCurrentElement is before or at the one
                 // we're removing, the new position is the same as before.
                newPos = mCurrentElement - begin(mElements);
            } else {
                 // Otherwise, it's one less than before.
                newPos = mCurrentElement - begin(mElements) - 1;
            }

             // Erase the element (and ignore the return value).
            mElements.erase(it);

             // Now reset our iterator to make sure it is valid.
            mCurrentElement = begin(mElements) + newPos;

            return;
        }
    }
}

template <typename T> T& RoundRobin<T>::getNext()
{
    // First, make sure there are elements.
    if (mElements.empty()) {
        throw std::out_of_range("No elements in the list");
    }

    // Store the current element which we need to return.
    auto& toReturn = *mCurrentElement;

    // Increment the iterator modulo the number of elements.
    ++mCurrentElement;
    if (mCurrentElement == end(mElements)) {
        mCurrentElement = begin(mElements);
    }

    // Return a reference to the element.
    return toReturn;
}

Here’s a simple implementation of a scheduler that uses the RoundRobin class template, with comments explaining the code:

// Simple Process class.
class Process final
{
    public:
        // Constructor accepting the name of the process.
        Process(string_view name) : mName(name) {}

        // Implementation of doWorkDuringTimeSlice() would let the process
        // perform its work for the duration of a time slice.
        // Actual implementation omitted.
        void doWorkDuringTimeSlice() {
            cout << "Process " << mName
                 << " performing work during time slice." << endl;
        }

        // Needed for the RoundRobin::remove() method to work.
        bool operator==(const Process& rhs) {
            return mName == rhs.mName;
        }
    private:
        string mName;
};

// Simple round-robin based process scheduler.
class Scheduler final
{
    public:
        // Constructor takes a vector of processes.
        Scheduler(const vector<Process>& processes);

        // Selects the next process using a round-robin scheduling
        // algorithm and allows it to perform some work during
        // this time slice.
        void scheduleTimeSlice();

        // Removes the given process from the list of processes.
        void removeProcess(const Process& process);
    private:
        RoundRobin<Process> mProcesses;
};

Scheduler::Scheduler(const vector<Process>& processes)
{
    // Add the processes
    for (auto& process : processes) {
        mProcesses.add(process);
    }
}

void Scheduler::scheduleTimeSlice()
{
    try {
        mProcesses.getNext().doWorkDuringTimeSlice();
    } catch (const out_of_range&) {
        cerr << "No more processes to schedule." << endl;
    }
}

void Scheduler::removeProcess(const Process& process)
{
    mProcesses.remove(process);
}

int main()
{
    vector<Process> processes = { Process("1"), Process("2"), Process("3") };

    Scheduler scheduler(processes);
    for (int i = 0; i < 4; ++i)
        scheduler.scheduleTimeSlice();

    scheduler.removeProcess(processes[1]);
    cout << "Removed second process" << endl;

    for (int i = 0; i < 4; ++i)
        scheduler.scheduleTimeSlice();

    return 0;
}

The output should be as follows:

Process 1 performing work during time slice.
Process 2 performing work during time slice.
Process 3 performing work during time slice.
Process 1 performing work during time slice.
Removed second process
Process 3 performing work during time slice.
Process 1 performing work during time slice.
Process 3 performing work during time slice.
Process 1 performing work during time slice.

Accessing Elements

The only methods provided by a list to access elements are front() and back(), both of which run in constant time. These methods return a reference to the first and last elements in a list. All other element access must be performed through iterators.

A list supports begin(), returning an iterator referring to the first element in the list, and end(), returning an iterator referring to one past the last element in the list. It also supports cbegin(), cend(), rbegin(), rend(), crbegin(), and crend(), similar to a vector.

Iterators

A list iterator is bidirectional, not random access like a vector iterator. That means that you cannot add and subtract list iterators from each other, or perform other pointer arithmetic on them. For example, if p is a list iterator, you can traverse through the elements of the list by doing ++p or --p, but you cannot use the addition or subtraction operator; p+n and p-n do not work.

Adding and Removing Elements

A list supports the same add element and remove element methods as a vector, including push_back(), pop_back(), emplace(), emplace_back(), the five forms of insert(), the two forms of erase(), and clear(). Like a deque, it also provides push_front(), emplace_front(), and pop_front(). All these methods (except for clear()) run in constant time, once you’ve found the correct position. Thus, a list could be appropriate for applications that perform many insertions and deletions from the data structure, but do not need quick index-based element access. And even then, a vector might still be faster. Use a performance profiler to make sure.

list Size

Like deques, and unlike vectors, lists do not expose their underlying memory model. Consequently, they support size(), empty(), and resize(), but not reserve() or capacity(). Note that the size() method on a list has constant complexity, which is not the case for the size() method on a forward_list (discussed later).

Special list Operations

A list provides several special operations that exploit its quick element insertion and deletion. This section provides an overview and examples. Consult a Standard Library Reference for a thorough reference of all the methods.

// Store the a words in the main dictionary.
list<string> dictionary{ "aardvark", "ambulance" };
// Store the b words.
list<string> bWords{ "bathos", "balderdash" };
// Add the c words to the main dictionary.
dictionary.push_back("canticle");
dictionary.push_back("consumerism");
// Splice the b words into the main dictionary.
if (!bWords.empty()) {
    // Get an iterator to the last b word.
    auto iterLastB = --(cend(bWords));
    // Iterate up to the spot where we want to insert b words.
    auto it = cbegin(dictionary);
    for (; it != cend(dictionary); ++it) {
        if (*it > *iterLastB)
            break;
    }
    // Add in the b words. This action removes the elements from bWords.
    dictionary.splice(it, bWords);
}
// Print out the dictionary.
for (const auto& word : dictionary) {
    cout << word << endl;
} 

aardvark
ambulance
bathos
balderdash
canticle
consumerism

list Example: Determining Enrollment

Suppose that you are writing a computer registration system for a university. One feature you might provide is the ability to generate a complete list of enrolled students in the university from lists of the students in each class. For the sake of this example, assume that you must write only a single function that takes a vector of lists of student names (as strings), plus a list of students that have been dropped from their courses because they failed to pay tuition. This method should generate a complete list of all the students in all the courses, without any duplicates, and without those students who have been dropped. Note that students might be in more than one course.

Here is the code for this method, with comments explaining the code. With the power of Standard Library lists, the method is practically shorter than its written description! Note that the Standard Library allows you to “nest” containers: in this case, you can use a vector of lists.

// courseStudents is a vector of lists, one for each course. The lists
// contain the students enrolled in those courses. They are not sorted.
//
// droppedStudents is a list of students who failed to pay their
// tuition and so were dropped from their courses.
//
// The function returns a list of every enrolled (non-dropped) student in
// all the courses.
list<string> getTotalEnrollment(const vector<list<string>>& courseStudents,
                                const list<string>& droppedStudents)
{
    list<string> allStudents;

    // Concatenate all the course lists onto the master list
    for (auto& lst : courseStudents) {
        allStudents.insert(cend(allStudents), cbegin(lst), cend(lst));
    }

    // Sort the master list
    allStudents.sort();

    // Remove duplicate student names (those who are in multiple courses).
    allStudents.unique();

    // Remove students who are on the dropped list.
    // Iterate through the dropped list, calling remove on the
    // master list for each student in the dropped list.
    for (auto& str : droppedStudents) {
        allStudents.remove(str);
    }

    // done!
    return allStudents;
}

queue Operations

The queue interface is extremely simple: there are only eight methods plus the constructor and the normal comparison operators. The push()and emplace() methods add a new element to the tail of the queue, while pop() removes the element at the head of the queue. You can retrieve references to, without removing, the first and last elements with front() and back(), respectively. As usual, when called on const objects, front() and back() return const references; and when called on non-const objects, they return non-const (read/write) references.

The queue also supports size(), empty(), and swap().

queue Example: A Network Packet Buffer

When two computers communicate over a network, they send information to each other divided up into discrete chunks called packets. The networking layer of the computer’s operating system must pick up the packets and store them as they arrive. However, the computer might not have enough bandwidth to process all of them at once. Thus, the networking layer usually buffers, or stores, the packets until the higher layers have a chance to attend to them. The packets should be processed in the order they arrive, so this problem is perfect for a queue structure. The following is a small PacketBuffer class, with comments explaining the code, which stores incoming packets in a queue until they are processed. It’s a class template so that different layers of the networking layer can use it for different kinds of packets, such as IP packets or TCP packets. It allows the client to specify a maximum size because operating systems usually limit the number of packets that can be stored, so as not to use too much memory. When the buffer is full, subsequently arriving packets are ignored.

template <typename T>
class PacketBuffer
{
    public:
        // If maxSize is 0, the size is unlimited, because creating
        // a buffer of size 0 makes little sense. Otherwise only
        // maxSize packets are allowed in the buffer at any one time.
        PacketBuffer(size_t maxSize = 0);

        virtual ~PacketBuffer() = default;

        // Stores a packet in the buffer.
        // Returns false if the packet has been discarded because
        // there is no more space in the buffer, true otherwise.
        bool bufferPacket(const T& packet);

        // Returns the next packet. Throws out_of_range
        // if the buffer is empty.
        T getNextPacket();
    private:
        std::queue<T> mPackets;
        size_t mMaxSize;
};

template <typename T> PacketBuffer<T>::PacketBuffer(size_t maxSize/*= 0*/)
    : mMaxSize(maxSize)
{
}

template <typename T> bool PacketBuffer<T>::bufferPacket(const T& packet)
{
    if (mMaxSize > 0 && mPackets.size() == mMaxSize) {
        // No more space. Drop the packet.
        return false;
    }
    mPackets.push(packet);
    return true;
}

template <typename T> T PacketBuffer<T>::getNextPacket()
{
    if (mPackets.empty()) {
        throw std::out_of_range("Buffer is empty");
    }
    // Retrieve the head element
    T temp = mPackets.front();
    // Pop the head element
    mPackets.pop();
    // Return the head element
    return temp;
}

A practical application of this class would require multiple threads. C++ provides synchronization classes to allow thread-safe access to shared objects. Without explicit synchronization, no Standard Library object can be used safely from multiple threads when at least one of the threads modifies the object. Synchronization is discussed in Chapter 23. The focus in this example is on the queue class, so here is a single-threaded example of using the PacketBuffer:

class IPPacket final
{
    public:
        IPPacket(int id) : mID(id) {}
        int getID() const { return mID; }
    private:
        int mID;
};

int main()
{
    PacketBuffer<IPPacket> ipPackets(3);

    // Add 4 packets
    for (int i = 1; i <= 4; ++i) {
        if (!ipPackets.bufferPacket(IPPacket(i))) {
            cout << "Packet " << i << " dropped (queue is full)." << endl;
        }
    }

    while (true) {
        try {
            IPPacket packet = ipPackets.getNextPacket();
            cout << "Processing packet " << packet.getID() << endl;
        } catch (const out_of_range&) {
            cout << "Queue is empty." << endl;
            break;
        }
    }
    return 0;
}

The output of this program is as follows:

Packet 4 dropped (queue is full).
Processing packet 1
Processing packet 2
Processing packet 3
Queue is empty.

priority_queue Operations

A priority_queue provides even fewer operations than does a queue. The push() and emplace() methods allow you to insert elements, pop() allows you to remove elements, and top() returns a const reference to the head element.

Like a queue, a priority_queue supports size(), empty(), and swap(). However, it does not provide any comparison operators.

priority_queue Example: An Error Correlator

Single failures on a system can often cause multiple errors to be generated from different components. A good error-handling system uses error correlation to process the most important errors first. You can use a priority_queue to write a very simple error correlator. Assume all error events encode their own priority. The error correlator simply sorts error events according to their priority, so that the highest-priority errors are always processed first. Here is the class definition:

// Sample Error class with just a priority and a string error description.
class Error final
{
    public:
        Error(int priority, std::string_view errorString)
            : mPriority(priority), mErrorString(errorString) {}

        int getPriority() const { return mPriority; }
        std::string_view getErrorString() const { return mErrorString; }

    private:
        int mPriority;
        std::string mErrorString;
};

bool operator<(const Error& lhs, const Error& rhs);
std::ostream& operator<<(std::ostream& os, const Error& err);

// Simple ErrorCorrelator class that returns highest priority errors first.
class ErrorCorrelator final
{
    public:
        // Add an error to be correlated.
        void addError(const Error& error);
        // Retrieve the next error to be processed.
        Error getError();
    private:
        std::priority_queue<Error> mErrors;
};

Here are the definitions of the functions and methods:

bool operator<(const Error& lhs, const Error& rhs)
{
    return (lhs.getPriority() < rhs.getPriority());
}

ostream& operator<<(ostream& os, const Error& err)
{
    os << err.getErrorString() << " (priority " << err.getPriority() << ")";
    return os;
}

void ErrorCorrelator::addError(const Error& error)
{
    mErrors.push(error);
}

Error ErrorCorrelator::getError()
{
    // If there are no more errors, throw an exception.
    if (mErrors.empty()) {
        throw out_of_range("No more errors.");
    }
    // Save the top element.
    Error top = mErrors.top();
    // Remove the top element.
    mErrors.pop();
    // Return the saved element.
    return top;
}

Here is a simple unit test showing how to use the ErrorCorrelator. Realistic use would require multiple threads so that one thread adds errors, while another processes them. As mentioned earlier with the queue example, this requires explicit synchronization, which is only discussed in Chapter 23.

ErrorCorrelator ec;
ec.addError(Error(3, "Unable to read file"));
ec.addError(Error(1, "Incorrect entry from user"));
ec.addError(Error(10, "Unable to allocate memory!"));

while (true) {
    try {
        Error e = ec.getError();
        cout << e << endl;
    } catch (const out_of_range&) {
        cout << "Finished processing errors" << endl;
        break;
    }
}

The output of this program is as follows:

Unable to allocate memory! (priority 10)
Unable to read file (priority 3)
Incorrect entry from user (priority 1)
Finished processing errors

stack Operations

Like the queue, the stack provides push(), emplace(), and pop(). The difference is that push() adds a new element to the top of the stack, “pushing down” all elements inserted earlier, and pop() removes the element from the top of the stack, which is the most recently inserted element. The top() method returns a const reference to the top element if called on a const object, and a non-const reference if called on a non-const object.

The stack supports empty(), size(), swap(), and the standard comparison operators.

stack Example: Revised Error Correlator

You can rewrite the previous ErrorCorrelator class so that it gives out the most recent error instead of the one with the highest priority. The only change required is to change mErrors from a priority_queue to a stack. With this change, the errors are distributed in LIFO order instead of priority order. Nothing in the method definitions needs to change because the push(), pop(), top(), and empty() methods exist on both a priority_queue and a stack.

Constructing maps

The map class template takes four types: the key type, the value type, the comparison type, and the allocator type. As always, the allocator is ignored in this chapter. The comparison type is similar to the comparison type for a priority_queue described earlier. It allows you to specify a different comparison class than the default. In this chapter, only the default less comparison is used. When using the default, make sure that your keys all respond to operator< appropriately. If you’re interested in further detail, Chapter 18 explains how to write your own comparison classes.

If you ignore the comparison and allocator parameters, constructing a map is just like constructing a vector or a list, except that you specify the key and value types separately in the template instantiation. For example, the following code constructs a map that uses ints as the key and stores objects of the Data class:

class Data final
{
    public:
        explicit Data(int value = 0) : mValue(value) { }
        int getValue() const { return mValue; }
        void setValue(int value) { mValue = value; }

    private:
        int mValue;
}; 
…
map<int, Data> dataMap;

A map also supports uniform initialization:

map<string, int> m = {
    { "Marc G.", 123 },
    { "Warren B.", 456 },
    { "Peter V.W.", 789 }
};

Inserting Elements

Inserting an element into sequential containers such as vector and list always requires you to specify the position at which the element is to be added. A map, along with the other ordered associative containers, is different. The map’s internal implementation determines the position in which to store the new element; you need only to supply the key and the value.

When inserting elements, it is important to keep in mind that maps require unique keys: every element in the map must have a different key. If you want to support multiple elements with the same key, you have two options: you can either use a map and store another container such as a vector or an array as the value for a key, or you can use multimaps, described later.

map<int, Data> dataMap;

auto ret = dataMap.insert({ 1, Data(4) });   // Using an initializer_list
if (ret.second) {
    cout << "Insert succeeded!" << endl;
} else {
    cout << "Insert failed!" << endl;
}

ret = dataMap.insert(make_pair(1, Data(6))); // Using a pair object
if (ret.second) {
    cout << "Insert succeeded!" << endl;
} else {
    cout << "Insert failed!" << endl;
}

pair<map<int, Data>::iterator, bool> ret;

Insert succeeded!
Insert failed!

if (auto result = dataMap.insert({ 1, Data(4) }); result.second) {
    cout << "Insert succeeded!" << endl;
} else {
    cout << "Insert failed!" << endl;
}

if (auto [iter, success] = dataMap.insert({ 1, Data(4) }); success) {
    cout << "Insert succeeded!" << endl;
} else {
    cout << "Insert failed!" << endl;
}

ret = dataMap.insert_or_assign(1, Data(7));
if (ret.second) {
    cout << "Inserted." << endl;
} else {
    cout << "Overwritten." << endl;
} 

map<int, Data> dataMap;
dataMap[1] = Data(4);
dataMap[1] = Data(6); // Replaces the element with key 1

void func(const map<int, int>& m)
{
    cout << m[1] << endl;  // Error
}

map Iterators

map iterators work similarly to the iterators on the sequential containers. The major difference is that the iterators refer to key/value pairs instead of just the values. In order to access the value, you must retrieve the second field of the pair object. map iterators are bidirectional, meaning you can traverse them in both directions. Here is how you can iterate through the map from the previous example:

for (auto iter = cbegin(dataMap); iter != cend(dataMap); ++iter) {
    cout << iter->second.getValue() << endl;
}

Take another look at the expression used to access the value:

iter->second.getValue()

iter refers to a key/value pair, so you can use the -> operator to access the second field of that pair, which is a Data object. You can then call the getValue() method on that Data object.

Note that the following code is functionally equivalent:

(*iter).second.getValue()

Using a range-based for loop, the loop can be written more readable as follows:

for (const auto& p : dataMap) {
    cout << p.second.getValue() << endl;
}

It can be implemented even more elegantly using a combination of a range-based for loop and C++17 structured bindings:

for (const auto& [key, data] : dataMap) {
    cout << data.getValue() << endl;
}

Looking Up Elements

A map provides logarithmic lookup of elements based on a supplied key. If you already know that an element with a given key is in a map, the simplest way to look it up is through operator[] as long as you call it on a non-const map or a non-const reference to a map. The nice thing about operator[] is that it returns a reference to the element that you can use and modify directly, without worrying about pulling the value out of a pair object. Here is an extension to the preceding example to call the setValue() method on the Data object value at key 1:

map<int, Data> dataMap;
dataMap[1] = Data(4);
dataMap[1] = Data(6);
dataMap[1].setValue(100);

However, if you don’t know whether the element exists, you may not want to use operator[], because it will insert a new element with that key if it doesn’t find one already. As an alternative, map provides a find() method that returns an iterator referring to the element with the specified key, if it exists, or the end() iterator if it’s not in the map. Here is an example using find() to perform the same modification to the Data object with key 1:

auto it = dataMap.find(1);
if (it != end(dataMap)) {
    it->second.setValue(100);
}

As you can see, using find() is a bit clumsier, but it’s sometimes necessary.

If you only want to know whether or not an element with a certain key is in a map, you can use the count() method. It returns the number of elements in a map with a given key. For maps, the result will always be 0 or 1 because there can be no elements with duplicate keys.

Removing Elements

A map allows you to remove an element at a specific iterator position or to remove all elements in a given iterator range, in amortized constant and logarithmic time, respectively. From the client perspective, these two erase() methods are equivalent to those in the sequential containers. A great feature of a map, however, is that it also provides a version of erase() to remove an element matching a key. Here is an example:

map<int, Data> dataMap;
dataMap[1] = Data(4);
cout << "There are " << dataMap.count(1) << " elements with key 1" << endl;
dataMap.erase(1);
cout << "There are " << dataMap.count(1) << " elements with key 1" << endl;

The output is as follows:

There are 1 elements with key 1
There are 0 elements with key 1

Nodes

All the ordered and unordered associative containers are so-called node-based data structures. Starting with C++17, the Standard Library provides direct access to nodes in the form of node handles. The exact type is unspecified, but each container has a type alias called node_type that specifies the type of a node handle for that container. A node handle can only be moved, and is the owner of the element stored in a node. It provides read/write access to both the key and the value.

Nodes can be extracted from an associative container as a node handle using the extract() method, based either on a given iterator position or on a given key. Extracting a node from a container removes it from the container, because the returned node handle is the sole owner of the extracted element.

New insert() overloads are provided that allow you to insert a node handle into a container.

Using extract() to extract node handles, and insert() to insert node handles, you can effectively transfer data from one associative container to another one without any copying or moving involved. You can even move nodes from a map to a multimap, and from a set to a multiset. Continuing with the example from the previous section, the following code snippet transfers the node with key 1 to a second map:

map<int, Data> dataMap2;
auto extractedNode = dataMap.extract(1);
dataMap2.insert(std::move(extractedNode));

The last two lines can be combined into one:

dataMap2.insert(dataMap.extract(1));

One additional operation is available to move all nodes from one associative container to another one: merge(). Nodes that cannot be moved because they would cause, for example, duplicates in a target container that does not allow duplicates, are left in the source container. Here is an example:

map<int, int> src = { {1, 11}, {2, 22} };
map<int, int> dst = { {2, 22}, {3, 33}, {4, 44}, {5, 55} };
dst.merge(src);

After the merge operation, src still contains one element, {2, 22}, because the destination already contains such an element, so it cannot be moved. dst contains {1, 11}, {2, 22}, {3, 33}, {4, 44}, and {5, 55} after the operation.

map Example: Bank Account

You can implement a simple bank account database using a map. A common pattern is for the key to be one field of a class or struct that is stored in a map. In this case, the key is the account number. Here are simple BankAccount and BankDB classes:

class BankAccount final
{
    public:
        BankAccount(int acctNum, std::string_view name)
            : mAcctNum(acctNum), mClientName(name) {}

        void setAcctNum(int acctNum) { mAcctNum = acctNum; }
        int getAcctNum() const { return mAcctNum; }

        void setClientName(std::string_view name) { mClientName = name; }
        std::string_view getClientName() const { return mClientName; }
    private:
        int mAcctNum;
        std::string mClientName;
};

class BankDB final
{
    public:
        // Adds account to the bank database. If an account exists already
        // with that number, the new account is not added. Returns true
        // if the account is added, false if it's not.
        bool addAccount(const BankAccount& account);

        // Removes the account acctNum from the database.
        void deleteAccount(int acctNum);

        // Returns a reference to the account represented
        // by its number or the client name.
        // Throws out_of_range if the account is not found.
        BankAccount& findAccount(int acctNum);
        BankAccount& findAccount(std::string_view name);

        // Adds all the accounts from db to this database.
        // Deletes all the accounts from db.
        void mergeDatabase(BankDB& db);
    private:
        std::map<int, BankAccount> mAccounts;
};

Here are the implementations of the BankDB methods, with comments explaining the code:

bool BankDB::addAccount(const BankAccount& acct)
{
    // Do the actual insert, using the account number as the key
    auto res = mAccounts.emplace(acct.getAcctNum(), acct);
    // or: auto res = mAccounts.insert(make_pair(acct.getAcctNum(), acct));

    // Return the bool field of the pair specifying success or failure
    return res.second;
}

void BankDB::deleteAccount(int acctNum)
{
    mAccounts.erase(acctNum);
}

BankAccount& BankDB::findAccount(int acctNum)
{
    // Finding an element via its key can be done with find()
    auto it = mAccounts.find(acctNum);
    if (it == end(mAccounts)) {
        throw out_of_range("No account with that number.");
    }
    // Remember that iterators into maps refer to pairs of key/value
    return it->second;
}

BankAccount& BankDB::findAccount(string_view name)
{
    // Finding an element by a non-key attribute requires a linear
    // search through the elements. Uses C++17 structured bindings.
    for (auto& [acctNum, account] : mAccounts) {
        if (account.getClientName() == name) {
            return account;  // found it!
        }
    }
    // If your compiler doesn't support the above C++17 structured
    // bindings yet, you can use the following implementation
    //for (auto& p : mAccounts) {
    //    if (p.second.getClientName() == name) { return p.second; }
    //}

    throw out_of_range("No account with that name.");
}

void BankDB::mergeDatabase(BankDB& db)
{
    // Use C++17 merge().
    mAccounts.merge(db.mAccounts);
    // Or: mAccounts.insert(begin(db.mAccounts), end(db.mAccounts));

    // Now clear the source database.
    db.mAccounts.clear();
}

You can test the BankDB class with the following code:

BankDB db;
db.addAccount(BankAccount(100, "Nicholas Solter"));
db.addAccount(BankAccount(200, "Scott Kleper"));

try {
    auto& acct = db.findAccount(100);
    cout << "Found account 100" << endl;
    acct.setClientName("Nicholas A Solter");

    auto& acct2 = db.findAccount("Scott Kleper");
    cout << "Found account of Scott Kleper" << endl;

    auto& acct3 = db.findAccount(1000);
} catch (const out_of_range& caughtException) {
    cout << "Unable to find account: " << caughtException.what() << endl;
}

The output is as follows:

Found account 100
Found account of Scott Kleper
Unable to find account: No account with that number.

multimap Example: Buddy Lists

Most of the numerous online chat programs allow users to have a “buddy list” or list of friends. The chat program confers special privileges on users in the buddy list, such as allowing them to send unsolicited messages to the user.

One way to implement the buddy lists for an online chat program is to store the information in a multimap. One multimap could store the buddy lists for every user. Each entry in the container stores one buddy for a user. The key is the user and the value is the buddy. For example, if Harry Potter and Ron Weasley had each other on their individual buddy lists, there would be two entries of the form “Harry Potter” maps to “Ron Weasley” and “Ron Weasley” maps to “Harry Potter.” A multimap allows multiple values for the same key, so the same user is allowed multiple buddies. Here is the BuddyList class definition:

class BuddyList final
{
    public:
        // Adds buddy as a friend of name.
        void addBuddy(const std::string& name, const std::string& buddy);
        // Removes buddy as a friend of name
        void removeBuddy(const std::string& name, const std::string& buddy);
        // Returns true if buddy is a friend of name, false otherwise.
        bool isBuddy(const std::string& name, const std::string& buddy) const;
        // Retrieves a list of all the friends of name.
        std::vector<std::string> getBuddies(const std::string& name) const;
    private:
        std::multimap<std::string, std::string> mBuddies;
};

Here is the implementation, with comments explaining the code. It demonstrates the use of lower_bound(), upper_bound(), and equal_range():

void BuddyList::addBuddy(const string& name, const string& buddy)
{
    // Make sure this buddy isn't already there. We don't want
    // to insert an identical copy of the key/value pair.
    if (!isBuddy(name, buddy)) {
        mBuddies.insert({ name, buddy }); // Using initializer_list
    }
}

void BuddyList::removeBuddy(const string& name, const string& buddy)
{
    // Obtain the beginning and end of the range of elements with
    // key 'name'. Use both lower_bound() and upper_bound() to demonstrate
    // their use. Otherwise, it's more efficient to call equal_range().
    auto begin = mBuddies.lower_bound(name);  // Start of the range
    auto end = mBuddies.upper_bound(name);    // End of the range

    // Iterate through the elements with key 'name' looking
    // for a value 'buddy'. If there are no elements with key 'name',
    // begin equals end, so the loop body doesn't execute.
    for (auto iter = begin; iter != end; ++iter) {
        if (iter->second == buddy) {
            // We found a match! Remove it from the map.
            mBuddies.erase(iter);
            break;
        }
    }
}

bool BuddyList::isBuddy(const string& name, const string& buddy) const
{
    // Obtain the beginning and end of the range of elements with
    // key 'name' using equal_range(), and C++17 structured bindings.
    auto [begin, end] = mBuddies.equal_range(name);

    // Iterate through the elements with key 'name' looking
    // for a value 'buddy'.
    for (auto iter = begin; iter != end; ++iter) {
        if (iter->second == buddy) {
            // We found a match!
            return true;
        }
    }
    // No matches
    return false;
}

vector<string> BuddyList::getBuddies(const string& name) const
{
    // Obtain the beginning and end of the range of elements with
    // key 'name' using equal_range(), and C++17 structured bindings.
    auto [begin, end] = mBuddies.equal_range(name);

    // Create a vector with all names in the range (all buddies of name).
    vector<string> buddies;
    for (auto iter = begin; iter != end; ++iter) {
        buddies.push_back(iter->second);
    }
    return buddies;
}

This implementation uses C++17 structured bindings, as in this example:

auto [begin, end] = mBuddies.equal_range(name);

If your compiler doesn’t support structured bindings yet, then you can write the following:

auto range = mBuddies.equal_range(name);
auto begin = range.first;  // Start of the range
auto end = range.second;   // End of the range

Note that removeBuddy() can’t simply use the version of erase() that erases all elements with a given key, because it should erase only one element with the key, not all of them. Note also that getBuddies() can’t use insert() on the vector to insert the elements in the range returned by equal_range(), because the elements referred to by the multimap iterators are key/value pairs, not strings. The getBuddies() method must iterate explicitly through the range extracting the string from each key/value pair and pushing it onto the new vector to be returned.

Here is a test of the BuddyList:

BuddyList buddies;
buddies.addBuddy("Harry Potter", "Ron Weasley");
buddies.addBuddy("Harry Potter", "Hermione Granger");
buddies.addBuddy("Harry Potter", "Hagrid");
buddies.addBuddy("Harry Potter", "Draco Malfoy");
// That's not right! Remove Draco.
buddies.removeBuddy("Harry Potter", "Draco Malfoy");
buddies.addBuddy("Hagrid", "Harry Potter");
buddies.addBuddy("Hagrid", "Ron Weasley");
buddies.addBuddy("Hagrid", "Hermione Granger");

auto harrysFriends = buddies.getBuddies("Harry Potter");

cout << "Harry's friends: " << endl;
for (const auto& name : harrysFriends) {
    cout << "	" << name << endl;
}

The output is as follows:

Harry's friends:
        Ron Weasley
        Hermione Granger
        Hagrid

set Example: Access Control List

One way to implement basic security on a computer system is through access control lists. Each entity on the system, such as a file or a device, has a list of users with permissions to access that entity. Users can generally be added to and removed from the permissions list for an entity only by users with special privileges. Internally, a set provides a nice way to represent the access control list. You could use one set for each entity, containing all the usernames who are allowed to access the entity. Here is a class definition for a simple access control list:

class AccessList final
{
    public:
        // Default constructor
        AccessList() = default;
        // Constructor to support uniform initialization.
        AccessList(std::initializer_list<std::string_view> initlist);
        // Adds the user to the permissions list.
        void addUser(std::string_view user);
        // Removes the user from the permissions list.
        void removeUser(std::string_view user);
        // Returns true if the user is in the permissions list.
        bool isAllowed(std::string_view user) const;
        // Returns a vector of all the users who have permissions.
        std::vector<std::string> getAllUsers() const;
    private:
        std::set<std::string> mAllowed;
};

Here are the method definitions:

AccessList::AccessList(initializer_list<string_view> initlist)
{
    mAllowed.insert(begin(initlist), end(initlist));
}

void AccessList::addUser(string_view user)
{
    mAllowed.emplace(user);
}

void AccessList::removeUser(string_view user)
{
    mAllowed.erase(string(user));
}

bool AccessList::isAllowed(string_view user) const
{
    return (mAllowed.count(string(user)) != 0);
}

vector<string> AccessList::getAllUsers() const
{
    return { begin(mAllowed), end(mAllowed) };
}

Take a look at the interesting one-line implementation of getAllUsers(). That one line constructs a vector<string> to return, by passing a begin and end iterator of mAllowed to the vector constructor. If you want, you can split this over two lines:

vector<string> users(begin(mAllowed), end(mAllowed));
return users;

Finally, here is a simple test program:

AccessList fileX = { "pvw", "mgregoire", "baduser" };
fileX.removeUser("baduser");

if (fileX.isAllowed("mgregoire")) {
    cout << "mgregoire has permissions" << endl;
}

if (fileX.isAllowed("baduser")) {
    cout << "baduser has permissions" << endl;
}

auto users = fileX.getAllUsers();
for (const auto& user : users) {
    cout << user << "  ";
}

One of the constructors for AccessList uses an initializer_list as a parameter, so that you can use the uniform initialization syntax, as demonstrated in the test program for initializing fileX.

The output of this program is as follows:

mgregoire has permissions
mgregoire  pvw

unordered_map Example: Phone Book

The following example uses an unordered_map to represent a phone book. The name of a person is the key, while the phone number is the value associated with that key.

template<class T>
void printMap(const T& m)
{
    for (auto& [key, value] : m) {
        cout << key << " (Phone: " << value << ")" << endl;
    }
    cout << "-------" << endl;
}

int main()
{
    // Create a hash table.
    unordered_map<string, string> phoneBook = {
        { "Marc G.", "123-456789" },
        { "Scott K.", "654-987321" } };
    printMap(phoneBook);

    // Add/remove some phone numbers.
    phoneBook.insert(make_pair("John D.", "321-987654"));
    phoneBook["Johan G."] = "963-258147";
    phoneBook["Freddy K."] = "999-256256";
    phoneBook.erase("Freddy K.");
    printMap(phoneBook);

    // Find the bucket index for a specific key.
    const size_t bucket = phoneBook.bucket("Marc G.");
    cout << "Marc G. is in bucket " << bucket
         << " which contains the following "
         << phoneBook.bucket_size(bucket) << " elements:" << endl;
    // Get begin and end iterators for the elements in this bucket.
    // 'auto' is used here. The compiler deduces the type of
    // both as unordered_map<string, string>::const_local_iterator
    auto localBegin = phoneBook.cbegin(bucket);
    auto localEnd = phoneBook.cend(bucket);
    for (auto iter = localBegin; iter != localEnd; ++iter) {
        cout << "	" << iter->first << " (Phone: "
            << iter->second << ")" << endl;
    }
    cout << "-------" << endl;

    // Print some statistics about the hash table
    cout << "There are " << phoneBook.bucket_count() << " buckets." << endl;
    cout << "Average number of elements in a bucket is "
         << phoneBook.load_factor() << endl;
    return 0;
}

A possible output is as follows. Note that the output can be different on a different system, because it depends on the implementation of both the hash function and the unordered_map itself being used.

Scott K. (Phone: 654-987321)
Marc G. (Phone: 123-456789)
-------
Scott K. (Phone: 654-987321)
Marc G. (Phone: 123-456789)
Johan G. (Phone: 963-258147)
John D. (Phone: 321-987654)
-------
Marc G. is in bucket 1 which contains the following 2 elements:
        Scott K. (Phone: 654-987321)
        Marc G. (Phone: 123-456789)
-------
There are 8 buckets.
Average number of elements in a bucket is 0.5

bitset Basics

A bitset, defined in <bitset>, is templatized on the number of bits it stores. The default constructor initializes all fields of a bitset to 0. An alternative constructor creates a bitset from a string of 0 and 1 characters.

You can adjust the values of individual bits with the set(), reset(), and flip() methods, and you can access and set individual fields with an overloaded operator[]. Note that operator[] on a non-const object returns a proxy object to which you can assign a Boolean value, call flip(), or complement with operator~. You can also access individual fields with the test() method. Additionally, you can stream bitsets with the normal insertion and extraction operators. A bitset is streamed as a string of 0 and 1 characters.

Here is a small example:

bitset<10> myBitset;

myBitset.set(3);
myBitset.set(6);
myBitset[8] = true;
myBitset[9] = myBitset[3];

if (myBitset.test(3)) {
    cout << "Bit 3 is set!"<< endl;
}
cout << myBitset << endl;

The output is as follows:

Bit 3 is set!
1101001000

Note that the leftmost character in the output string is the highest numbered bit. This corresponds to our intuitions about binary number representations, where the low-order bit representing 2⁰ = 1 is the rightmost bit in the printed representation.

Bitwise Operators

In addition to the basic bit manipulation routines, a bitset provides implementations of all the bitwise operators: &, |, ^, ~, <<, >>, &=, |=, ^=, <<=, and >>=. They behave just as they would on a “real” sequence of bits. Here is an example:

auto str1 = "0011001100";
auto str2 = "0000111100";
bitset<10> bitsOne(str1);
bitset<10> bitsTwo(str2);

auto bitsThree = bitsOne & bitsTwo;
cout << bitsThree << endl;
bitsThree <<= 4;
cout << bitsThree << endl;

The output of the program is as follows:

0000001100
0011000000

bitset Example: Representing Cable Channels

One possible use of bitsets is tracking channels of cable subscribers. Each subscriber could have a bitset of channels associated with their subscription, with set bits representing the channels to which they actually subscribe. This system could also support “packages” of channels, also represented as bitsets, which represent commonly subscribed combinations of channels.

The following CableCompany class is a simple example of this model. It uses two maps, each of string/bitset. One stores the cable packages, while the other stores subscriber information.

const size_t kNumChannels = 10;

class CableCompany final
{
    public:
        // Adds the package with the specified channels to the database.
        void addPackage(std::string_view packageName,
            const std::bitset<kNumChannels>& channels);
        // Removes the specified package from the database.
        void removePackage(std::string_view packageName);
        // Retrieves the channels of a given package.
        // Throws out_of_range if the package name is invalid.
        const std::bitset<kNumChannels>& getPackage(
            std::string_view packageName) const;
        // Adds customer to database with initial channels found in package.
        // Throws out_of_range if the package name is invalid.
        // Throws invalid_argument if the customer is already known.
        void newCustomer(std::string_view name, std::string_view package);
        // Adds customer to database with given initial channels.
        // Throws invalid_argument if the customer is already known.
        void newCustomer(std::string_view name,
            const std::bitset<kNumChannels>& channels);
        // Adds the channel to the customers profile.
        // Throws invalid_argument if the customer is unknown.
        void addChannel(std::string_view name, int channel);
        // Removes the channel from the customers profile.
        // Throws invalid_argument if the customer is unknown.
        void removeChannel(std::string_view name, int channel);
        // Adds the specified package to the customers profile.
        // Throws out_of_range if the package name is invalid.
        // Throws invalid_argument if the customer is unknown.
        void addPackageToCustomer(std::string_view name,
            std::string_view package);
        // Removes the specified customer from the database.
        void deleteCustomer(std::string_view name);
        // Retrieves the channels to which a customer subscribes.
        // Throws invalid_argument if the customer is unknown.
        const std::bitset<kNumChannels>& getCustomerChannels(
            std::string_view name) const;
    private:
        // Retrieves the channels for a customer. (non-const)
        // Throws invalid_argument if the customer is unknown.
        std::bitset<kNumChannels>& getCustomerChannelsHelper(
            std::string_view name);

        using MapType = std::map<std::string, std::bitset<kNumChannels>>;
        MapType mPackages, mCustomers;
};

Here are the implementations of all methods, with comments explaining the code:

void CableCompany::addPackage(string_view packageName,
    const bitset<kNumChannels>& channels)
{
    mPackages.emplace(packageName, channels);
}

void CableCompany::removePackage(string_view packageName)
{
    mPackages.erase(packageName.data());
}

const bitset<kNumChannels>& CableCompany::getPackage(
    string_view packageName) const
{
    // Get a reference to the specified package.
    auto it = mPackages.find(packageName.data());
    if (it == end(mPackages)) {
        // That package doesn't exist. Throw an exception.
        throw out_of_range("Invalid package");
    }
    return it->second;
}

void CableCompany::newCustomer(string_view name, string_view package)
{
    // Get the channels for the given package.
    auto& packageChannels = getPackage(package);
    // Create the account with the bitset representing that package.
    newCustomer(name, packageChannels);
}

void CableCompany::newCustomer(string_view name,
    const bitset<kNumChannels>& channels)
{
    // Add customer to the customers map.
    auto result = mCustomers.emplace(name, channels);
    if (!result.second) {
        // Customer was already in the database. Nothing changed.
        throw invalid_argument("Duplicate customer");
    }
}

void CableCompany::addChannel(string_view name, int channel)
{
    // Get the current channels for the customer.
    auto& customerChannels = getCustomerChannelsHelper(name);
    // We found the customer; set the channel.
    customerChannels.set(channel);
}

void CableCompany::removeChannel(string_view name, int channel)
{
    // Get the current channels for the customer.
    auto& customerChannels = getCustomerChannelsHelper(name);
    // We found this customer; remove the channel.
    customerChannels.reset(channel);
}

void CableCompany::addPackageToCustomer(string_view name, string_view package)
{
    // Get the channels for the given package.
    auto& packageChannels = getPackage(package);
    // Get the current channels for the customer.
    auto& customerChannels = getCustomerChannelsHelper(name);
    // Or-in the package to the customer's existing channels.
    customerChannels |= packageChannels;
}

void CableCompany::deleteCustomer(string_view name)
{
    mCustomers.erase(name.data());
}

const bitset<kNumChannels>& CableCompany::getCustomerChannels(
    string_view name) const
{
    // Use const_cast() to forward to getCustomerChannelsHelper()
    // to avoid code duplication.
    return const_cast<CableCompany*>(this)->getCustomerChannelsHelper(name);
}

bitset<kNumChannels>& CableCompany::getCustomerChannelsHelper(
    string_view name)
{
    // Find a reference to the customer.
    auto it = mCustomers.find(name.data());
    if (it == end(mCustomers)) {
        throw invalid_argument("Unknown customer");
    }
    // Found it.
    // Note that 'it' is a reference to a name/bitset pair.
    // The bitset is the second field.
    return it->second;
}

Finally, here is a simple program demonstrating how to use the CableCompany class:

CableCompany myCC;
auto basic_pkg = "1111000000";
auto premium_pkg = "1111111111";
auto sports_pkg = "0000100111";

myCC.addPackage("basic", bitset<kNumChannels>(basic_pkg));
myCC.addPackage("premium", bitset<kNumChannels>(premium_pkg));
myCC.addPackage("sports", bitset<kNumChannels>(sports_pkg));

myCC.newCustomer("Marc G.", "basic");
myCC.addPackageToCustomer("Marc G.", "sports");
cout << myCC.getCustomerChannels("Marc G.") << endl;

The output is as follows:

1111100111