Posts from the “C++” Category

Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.


In C++, containers supporting insert with O(1) are vector, list, unordered_map, and unordered_set.

Containers remove by value with O(1) are unordered_map, unordered_set.

Container supporting random access is vector.

So, we can use vector AND unordered_set or unordered_map for the three functions. Then unordered_set or unordered_map? We have to use vector to store the values for the sake of random access with O(1). And a hash container (unordered_set, or unordered_map) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so unordered_map wins: reference the same value in the vector by the value’s position.

insert and random access can easily being done with O(1) for vector and unordered_map. But for remove, it affects the unordered_map‘s reference in the vector. The instinct is removing the value from the vector by getting its position from unordered_map. But this will decrease the positions of all descending elements in the vector, which affects the references of the unordered_map. The time complexity could be up to linear O(n) if we do position update in the unordered_map, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the vector, and updating the last element’s value in the unordered_map with the new position.  exactly O(1) on average.

Global Constant Pointer

Back to C++ fundamentals.

Given two declarations of global variables:

char const * banana = “banana”;

char const * const apple = “apple”;

Both banana and apple point to a constant character, but banana is not declared as const. What does this mean? banana can point to other values, while apple can’t. Then apple is safer than banana because as a global variable, apple always points to the constant character, while banana can be changed by accident. For instance, if there’s a variable of a class also named as “banana”, and share the same type as the global variable, when some functions of the class change “banana”, it’s possible that the global variable is changed, which causes incorrect value of the global variable when it’s used in other places.

Use Protocol in C++

Define the protocols as classes, and required methods as pure virtual functions:

class ProtocolOne {


virtual void draw()  = 0;


class ProtocolTwo {


virtual void castCameraRays() = 0;


Inherit the Protocol by whichever classes conforming to the protocols:

class SubClassOne : public ProtocolOne {


void draw() { };


class SubClassTwo : public ProtocolOne, public ProtocolTwo {


void draw() { };

void castCameraRays { };


Then with delegates defined as the follows:

class Dopamine {


ProtocolOne *delegate;


void loop() {

if (delegate) {





class Banana {


ProtocolTwo *delegate;

void loop() {

if(delegate) {





Assign the instantiated objects whose classses conform to the protocols to the delegates:

int main() {

Dopamine dopamineOne;

Dopamine dopamineTwo;

Banana banana;

SubClassOne *subclassOne = new SubClassOne();

SubClassTwo *subclassTwo = new SubClassTwo();

dopamineOne.delegate = subclassOne;

dopamineTwo.delegate = subclassTwo;

banana.delegate = subclassTwo;

/* … */

return 0;



reference: link

Pass-by-reference means to pass the reference of an argument in the calling function to the corresponding formal parameter of the called function. The called function can modify the value of the argument by using its reference passed in.

Mutable Data Members

reference: 12.2 in <<C++ Primier>>.

It sometimes (but not very often) happens that a class has a data member that we want to be able to modify, even inside a const member function. We can indicate such members by declaring them as mutable.

Friend Declarations in Class Templates

reference: 16.4.3 in <<C++ Primier>>.

There are three kinds of friend declarations that may appear in a class template. Each kind of declaration declares friendship to one or more entities:

1. Ordinary Friends

A friend declaration for an ordinary nontemplate class or function, which grants friendship to the specific named class or function.

template <class Type> class Bar {
// grants access to ordinary, nontemplate class and function
friend class FooBar;
friend void fcn();
// …

This declaration says that the members of FooBar and the function fcn may access the private and protected members of any instantiation of class Bar.

2. General Template Friendship 

A friend declaration for a class template or function template, which grants access to all instances of the friend.

template <class Type> class Bar {
// grants access to Foo1 or templ_fcn1 parameterized by any type
template <class T> friend class Foo1;
template <class T> friend void templ_fcn1(const T&);
// …

These friend declarations use a different type parameter than does the class itself. That type parameter refers to the type parameter of Foo1 and templ_fcn1. In both these cases, an unlimited number of classes and functions are made friends to Bar. The friend declaration for Foo1 says that any instance of Foo1 may access the private elements of any instance of Bar. Similarly, any instance of templ_fcn1 may access any instance of Bar.

3. Specific Template Friendship

A friend declaration that grants access only to a specific instance of a class or function template.

template <class T> class Foo2;
template <class T> void templ_fcn2(const T&);
template <class Type> class Bar {
// grants access to a single specific instance parameterized by char*
friend class Foo2<char*>;
friend void templ_fcn2<char*>(char* const &);
// …

Even though Foo2 itself is a class template, friendship is extended only to the specific instance of Foo2 that is parameterized by char*. Similarly, the friend declaration for templ_fcn2 says that only the instance of that function parameterized by char* is a friend to class Bar. The specific instantiations of Foo2 and templ_fcn2 parameterized by char* can access every instantiation of Bar.