Containers

Lambda Examples

Lambda example

#include <iostream>

template<typename F>
int foo(int x, int y, F lambda) {
    return lambda(x,y);
}

struct Multiply{
    double operator()( const double v1, const double v2 ) const{
        return v1 * v2;
    }
};

int main(){
    std::cout << foo(2,3, [](int x, int y){return x*y;}) << std::endl;
    Multiply mul;
    std::cout << foo(3,4, mul) << std::endl;
    return 0;
}

6
12

Really looks like this

template<>
int foo<__lambda_9_27>(int x, int y, __lambda_9_27 lambda){
    return lambda.operator()(x, y);
}


int main(){
  struct __lambda_9_27{
      int operator()(int x, int y) const{
          return x * y;
      }
  }

  std::cout.operator<<(foo(2, 3, __lambda_9_27{})).operator<<(std::endl);
}

Example 2

#include <iostream>
#include <vector>
using std::cout, std::vector,std::endl;

struct Multiply{
    double operator()( const double v1, const double v2 ) const{
        return v1 * v2;
    }
};

template<typename ITR, typename F>
int acc(ITR itr, ITR end,int init, F lambda) {
    int sum = init;
    for (; itr!=end; ++itr)
        sum=lambda(sum,*(itr));
    return sum;
}

int main(){
    vector vec1{10,20,30};
    cout << acc(vec1.begin(), vec1.end(), 0, [](int x, int y){return x+y;}) << std::endl;

    vector vec2{2,3,4};
    Multiply multiply;
    cout << acc(vec2.begin(), vec2.end(), 1, multiply) << std::endl;
    return 0;
}

60
24

Really looks like this:

template<>
int acc<__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > >, __lambda_15_46> //ITR,F
(__gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > itr, //arg1
 __gnu_cxx::__normal_iterator<int *, std::vector<int, std::allocator<int> > > end, //arg2
 int init,                                                                         //arg3
 __lambda_15_46 lambda){                                                           //arg4

     //start of function
      int sum = init;
      for(; __gnu_cxx::operator!=(itr, end); itr.operator++())
          sum = lambda.operator()(sum, (itr).operator*());
      return sum;
}

for_each

#include <iostream>
#include <algorithm>
#include <vector>
using std::cout, std::vector,std::endl,std::for_each;

int main(){
    vector nums{10,20,30};
    for_each(nums.begin(), nums.end(), [](int &n){ n++; });
    for_each(nums.cbegin(), nums.cend(), [](const int& n) { cout << n << " "; });
}

11 21 31

I usually will use a range-based for (for(auto& n : nums)) instead of for_each

Containers

Sequence containers

Sequence containers implement data structures which can be accessed sequentially.

name	description
array	static contiguous array
vector	dynamic contiguous array
deque	double-ended queue
forward_list	singly-linked list
list	doubly-linked list

Associative containers

Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity).

name	description
set	collection of unique keys, sorted by keys
map	collection of key-value pairs, sorted by keys, keys are unique
multiset	collection of keys, sorted by keys
multimap	collection of key-value pairs, sorted by keys

Unordered associative containers

Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) amortized, O(n) worst-case complexity).

name	description
unordered_set	collection of unique keys, hashed by keys
unordered_map	collection of key-value pairs, hashed by keys, keys are unique
unordered_multiset	collection of keys, hashed by keys
unordered_multimap	collection of key-value pairs, hashed by keys

Container adaptors

Container adaptors provide a different interface for sequential containers.

name	description
stack	adapts a container to provide stack (LIFO data structure)
queue	adapts a container to provide queue (FIFO data structure)
priority_queue	adapts a container to provide priority queue

Span (C++20)

name	description
span	a non-owning view over a contiguous sequence of objects

More info

Sequence containers

array

Creating array

std::array<int, 3> a1{ {1, 2, 3} }; //double curly 
std::array<int, 3> a2 = {1, 2, 3};  // never required after =
std::array<std::string, 2> a3 = { std::string("a"), "b" };

Element access & Capacity

a1[0]=1
a1.at(3) // throw std::out_of_range
a2.front()
a3.back()
a3.size()

container operations are supported

std::sort(a1.begin(), a1.end());
std::reverse_copy(a2.begin(), a2.end(), 
                    std::ostream_iterator<int>(std::cout, " "));

3 2 1

ranged for loop is supported

for(const auto& s: a3)
        std::cout << s << ' ';

Most modifiers are not supported such as push_back

vector

• The storage of the vector is handled automatically, being expanded and contracted as needed.

• The elements are stored contiguously.

• Element access, capacity, container operations and ranged-loops are supported

Creation

std::vector<int> v = {1, 2, 3, 4, 5, 6};

Modifiers

v.emplace_back(7);
v.pop_back();
v.erase(v.begin());
v.erase(v.begin()+1, v.begin()+3);

print(v);

deque

• deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end O(1)

• not stored contiguously

• Expansion of a deque is cheaper than the expansion of a std::vector

  • cons: large minimal memory cost

• Random access - O(1)

• Element access, capacity, container operations and ranged-loops are supported

std::deque<int> d = {7, 5, 16, 8};
d.emplace_front(10);

A deque is somewhat recursively defined: Internally it maintains a double-ended queue of chunks of fixed size. Each chunk is a vector, and the queue (“map” in the graphic below) of chunks itself is also a vector.

Source

list

• constant time insertion and removal of elements from anywhere in the container.

• Fast random access is not supported

• Usually a doubley-linked list

std::list<int> l = { 7, 5, 16, 8 };

Element access

• supports mostly everthing in vector except for [], at

doubly_linked_list.jpg

Examples

#include <iostream>
#include <vector>
#include <list>
#include <numeric>      // std::accumulate
#include <algorithm>    //std::transform

using namespace std;
int main(){
    std::vector<int> v = {1, 5, 4, 3, 2};
    std::list<double > l = {2.2, 4.4, 6.6, 8.8, 11};
    cout << std::accumulate(v.cbegin(),v.cend(),0) << endl;
    cout << accumulate(v.cbegin(),v.cend(),1,[&v](int i,int j) { return i*j;}) << endl;

    //sort v
    sort(v.begin(),v.end());

    //sum 2 containers
    vector<double> v_sum;
    std::transform(v.begin(), v.end(), l.begin(),
            std::back_inserter(v_sum),std::plus<double>()); // std::multiplies<double>()

    for(const auto& s: v_sum)
        std::cout << s << ' ';
    cout<<endl;

    return 0;
}

15
120
3.2 6.4 9.6 12.8 16

More examples: std::reduce,std::transform_reduce

Filling in numbers

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>    //std::transform

using namespace std;
int main(){
//    std::srand(std::time(nullptr));
    vector<int> v(5);

    std::generate(v.begin(), v.end(), std::rand);

    for(const auto& s: v)
        std::cout << s << ' ';
    cout<<endl;

    fill(v.begin(), v.end(),1); //fills only 1 num

    for(const auto& s: v)
        std::cout << s << ' ';
    cout<<endl;

    return 0;
}

1804289383 846930886 1681692777 1714636915 1957747793
1 1 1 1 1

std::iota-fill container with range

Conditional

#include <iostream>
#include <vector>
#include <algorithm>    //std::any_of

using namespace std;
int main(){
    vector<int> v {1,2,3,4,-1};
    // Checking if any element is negative
    any_of(v.cbegin(), v.cend(), [](int x){ return x<0; }) ? cout << "There exists a negative element\n" :cout << "All are positive elements\n";

    int N=2;
    cout << count_if(v.begin(), v.end(),[N](int a){ return (a >= N);}) <<endl;
    return 0;
}

There exists a negative element
3

all_of(), none_of(),count_if,find_if

Associative Containers

set

Sorted data structures that can be quickly searched (O(log n) complexity).No duplicates

set<int, less<int> > s ={1,3,3,4,-1};

#include <iostream>
#include <set>

using namespace std;
int main() {
    set<int, less<int> > s ={1,3,3,4,-1}; //  std::greater<int>
    s.insert(-5);
    s.erase(1);

    for(const auto& v: s)
        std::cout << v << ' '; cout<<endl;
}

-5 -1 3 4

Important! as with any sorted container we need to give the set a Compare class such as less<int> or greater<int> by default Compare = std::less<T>

multiset

Similar to set, with an exception that multiple elements can have same values.

    multiset<int, greater<int> > s ={1,3,3};

#include <iostream>
#include <set>

using namespace std;
int main() {
    multiset<int, greater<int> > s ={1,3,3,-1};
    for(const auto& v: s)
        std::cout << v << ' '; cout<<endl;
}

3 3 1 -1

map

• Each element has a key value and a mapped value.

• No two mapped values can have same key values.

• keys are sorted

map<int, int> m;

#include <iostream>
#include <map>

using namespace std;
int main() {
    map<int, int> m;

    // insert elements in random order
    m.insert(pair<int, int>(3, 60));
    m.insert(pair<int, int>(1, 40));
    m.insert(pair<int, int>(2, 30));
    m.erase(2); // remove elems with key=2

    for(const auto& v: m)
        std::cout << v.first << ": " << v.second << endl;
}

1: 40
3: 60

Example 2

#include <iostream>
#include <map>
#include <string>
using std::map; using std::cout; using std::string;

int main(){
    map<string, string> address_book = { std::make_pair("one","0123"),std::make_pair("two","4567") };
    address_book.insert({ "three", "7657" });

    for (auto & address_entry : address_book){
        cout << address_entry.first << " | " << address_entry.second << " |" << std::endl;
    }
    return 0;
}

one | 0123 |
three | 7657 |
two | 4567 |

This also works

map<string, string> address_book = { {"one","0123"}, 
{"two","4567"} };

multimap

Multimap is similar to map with an addition that multiple elements can have same keys.

Unordered associative containers

unordered_set

unordered_set <string> us ;

#include <iostream>
#include <unordered_set>

using namespace std;
int main() {
    unordered_set <string> uset ;

    uset.insert("code") ;
    uset.insert("in") ;
    uset.insert("c++") ;
    uset.insert("is") ;
    uset.insert("fast") ;

    for(const auto& v: uset)
        std::cout << v << " "; cout<<endl;
    return 0;
}

fast is code c++ in

unordered_map

#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    unordered_map<string, double> umap;

    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap.insert(make_pair("e", 2.718));

    for (auto x : umap)
        cout << x.first << ": " << x.second << endl;

    umap.find("e") == umap.end() ? cout << "e: not found\n" : cout << "e: found\n";
    return 0;
}

e: 2.718
PI: 3.14
root2: 1.414
e: found

Span (C++20)

The following code helps us with one-off errors.

#include <iostream>
#include <span>

using namespace std;

void printSpan(std::span<int> s){
    for (auto& i : s)
        cout << i < " "; cout <<endl;
    //std::find_if(s.begin(), s.end(),some_predicate);
}
int main() {
    int a[5]={0,1,2,3,4,5};
    printSpan(a);
    return 0;
}

Besides of ranged-based for loops, we also have find_if etc but without container overhead. Pretty cool 😎

Valarray

• std:: valarray and here

Difference between std::pair and std::tuple with only two members?

• std::pair can only have two values - not zero, one, three or more

• It's a bit easier to get the contents of a pair than a tuple. You have to use a function call in the tuple case: get<0>(t), while the pair case is just a member field (p.first,p.second)

Unpacking

#include <iostream>
#include <tuple>
using namespace std;

auto f_pair() {
    return pair(5,"hello");
//    return tuple(5,"hello");
}

int main() {
    auto f = f_pair; // f is a pointer to function
    auto [i,j] = f(); 
    cout << i << " " << j << endl;

    auto [x,y] = f_pair();
    cout << x << " " << y << endl;
}

5 hello
5 hello

auto [x,y] = f_pair() Creates this implicitly

  std::pair<int, const char *> __f_pair13 = f_pair();
  std::tuple_element<0, std::pair<int, const char *> >::type& x = std::get<0UL>(__f_pair13);
  std::tuple_element<1, std::pair<int, const char *> >::type& y = std::get<1UL>(__f_pair13);

Unpacking Structed Bindings

Allows unpacking any data structure whose size is known during compile time

#include <iostream>
using namespace std;

struct Packed {
    int x;
    string y;
    float z;
};

int main() {
    Packed p;
    p.x =1; p.y="nissan"; p.z=3.14;
    auto & [ x, y, z ] = p; // access by reference
    cout << x << " " << y << " " << z << endl;
}

1 nissan 3.14

Credits

basic_string and string

A std::string is an instantiation of the std::basic_string template with a type of char

#include <iostream>
using namespace std;

ostream& operator<< (ostream& out, basic_string<int> s) {
    for (int i: s)
        out << i << " ";
    return out;
}

int main() {
    basic_string<int> si({1,2,3,4,5,6});
    si.replace(3,6, basic_string<int>{7,8,9});
    cout << si << endl;

    basic_string<char> si2({'n','i','s','s','a','n'});
    cout << si2 << endl;
}

1 2 3 7 8 9 
nissan

without overloading the global operator<< we would have been able to print ints