C STL

Sequence Containers

Implement data structures which can be accessed in a sequential manner

std::vector

template < class T, class Alloc = allocator > class vector;
header

Member function

// inserting into a vector
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;
  it = myvector.begin();
  it = myvector.insert ( it , 200 );
  myvector.insert (it,2,300);
  // "it" no longer valid, get a new one:
  it = myvector.begin();
  std::vector<int> anothervector (2,400);
  myvector.insert (it+2,anothervector.begin(),anothervector.end());
  int myarray [] = { 501,502,503 };
  myvector.insert (myvector.begin(), myarray, myarray+3);
  std::cout << "myvector contains:";
  for (it=myvector.begin(); it<myvector.end(); it++)
    std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
}
//myvector contains: 501 502 503 300 300 400 400 200 100 100 100

Container Adaptors

Provide a different interface for sequential containers

std::queue

template > class queue;
header

Member functions

Example

// CPP code to illustrate  
// Queue in Standard Template Library (STL) 
#include <iostream> 
#include <queue> 
using namespace std; 
void showq(queue <int> gq) 
{ 
    queue <int> g = gq; 
    while (!g.empty()) 
    { 
        cout << '\t' << g.front(); 
        g.pop(); 
    } 
    cout << '\n'; 
} 
int main() 
{ 
    queue <int> gquiz; 
    gquiz.push(10); 
    gquiz.push(20); 
    gquiz.push(30); 
    cout << "The queue gquiz is : "; 
    showq(gquiz); 
    cout << "\ngquiz.size() : " << gquiz.size(); 
    cout << "\ngquiz.front() : " << gquiz.front(); 
    cout << "\ngquiz.back() : " << gquiz.back(); 
    cout << "\ngquiz.pop() : "; 
    gquiz.pop(); 
    showq(gquiz); 
    return 0; 
}

std::stack

header
template > class stack;

Member Functions

Associative Containers

Implement sorted data structures that can be quickly searched(O(log n) complexity)

std::map

header

Member Functions

std::set

header
template < class T, // set::key_type/value_type
class Compare = less, // set::key_compare/value_compare
class Alloc = allocator // set::allocator_type
> class set;

Member Functions

Unordered Associative Containers

implement unordered data structures that can be quickly searched

unordered_map

header
template >

unordered_set

unordered_map

unordered_multimap

Algorithm

std::sort

header
template void sort (RandomAccessIterator first, RandomAccessIterator last);
template void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

sort(first_iterator, last_iterator)

// sort algorithm example
#include <iostream>     // std::cout
#include <algorithm>    // std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

struct myclass {
  bool operator() (int i,int j) { return (i<j);}
} myobject;

int main () {
  int myints[] = {32,71,12,45,26,80,53,33};
  std::vector<int> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33

  // using default comparison (operator <):
  std::sort (myvector.begin(), myvector.begin()+4);           //(12 32 45 71)26 80 53 33

  // using function as comp
  std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80)

  // using object as comp
  std::sort (myvector.begin(), myvector.end(), myobject);     //(12 26 32 33 45 53 71 80)

  // print out content:
  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

//output
//$ myvector contains: 12 26 32 33 45 53 71 80

std::reverse

To reverse a vector
header
reverse(first_iterator, last_iterator)

// A C++ program to demonstrate working of sort(), 
// reverse() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
    // Initializing vector with array values 
    int arr[] = {10, 20, 5, 23 ,42 , 15}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    vector<int> vect(arr, arr+n); 

    cout << "Vector is: "; 
    for (int i=0; i<n; i++) 
        cout << vect[i] << " "; 

    // Reversing the Vector 
    reverse(vect.begin(), vect.end()); 

    cout << "\nVector after reversing is: "; 
    for (int i=0; i<6; i++) 
        cout << vect[i] << " "; 

    return 0; 
}

std::max_element

To find the maximum element of a vector.
header
*max_element(first_iterator, last_iterator)

// A C++ program to demonstrate working of sort(), 
// reverse() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
    // Initializing vector with array values 
    int arr[] = {10, 20, 5, 23 ,42 , 15}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    vector<int> vect(arr, arr+n); 

    cout << "Vector is: "; 
    for (int i=0; i<n; i++) 
        cout << vect[i] << " "; 

    cout << "\nMaximum element of vector is: "; 
    cout << *max_element(vect.begin(), vect.end()); 

    return 0; 
}

std::min_element

To find the minimum element of a vector
header
*min_element(first_iterator, last_iterator)

// A C++ program to demonstrate working of sort(), 
// reverse() 
#include <algorithm> 
#include <iostream> 
#include <vector> 
using namespace std; 

int main() 
{ 
    // Initializing vector with array values 
    int arr[] = {10, 20, 5, 23 ,42 , 15}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    vector<int> vect(arr, arr+n); 

    cout << "Vector is: "; 
    for (int i=0; i<n; i++) 
        cout << vect[i] << " "; 

    cout << "\nMinimum element of vector is: "; 
    cout << *min_element(vect.begin(), vect.end()); 

    return 0; 
}

Smart Pointers

智能指针在C/C++的重要性

Pointers are used for accessing the resources which are external to the program like heap memory. So for accessing the heap memory if anything is created inside heap memory Pointers are used.

普通指针的缺陷

#include <iostream> 
using namespace std; 

class Rectangle { 
private: 
    int length; 
    int breadth; 
}; 

void fun() 
{ 
    // By taking a pointer p and 
    // dynamically creating object 
    // of class rectangle 
    Rectangle* p = new Rectangle(); 
} 

int main() 
{ 
    // Infinite Loop 
    while (1) { 
        fun(); 
    } 
}

在这里p是局部变量，因此将不再可能释放以前p所指向的空间，在无限循环中，最终会因为内存的严重泄漏而导致程序崩溃。

智能指针

当object在跳出其作用域之后，会自动调用其析构函数，由析构函数自动的完成资源的释放。一个简单的实现方式如下

#include <iostream> 
using namespace std; 

class SmartPtr { 
    int* ptr; // Actual pointer 
public: 
    // Constructor: Refer https:// www.geeksforgeeks.org/g-fact-93/ 
    // for use of explicit keyword 
    explicit SmartPtr(int* p = NULL) { ptr = p; } 

    // Destructor 
    ~SmartPtr() { delete (ptr); } 

    // Overloading dereferencing operator 
    int& operator*() { return *ptr; } 
}; 

int main() 
{ 
    SmartPtr ptr(new int()); 
    *ptr = 20; 
    cout << *ptr; 

    // We don't need to call delete ptr: when the object 
    // ptr goes out of scope, the destructor for it is automatically 
    // called and destructor does delete ptr. 

    return 0; 
}

下面是也给针对所有类型的简单实现

#include <iostream> 
using namespace std; 

// A generic smart pointer class 
template <class T> 
class SmartPtr { 
    T* ptr; // Actual pointer 
public: 
    // Constructor 
    explicit SmartPtr(T* p = NULL) { ptr = p; } 

    // Destructor 
    ~SmartPtr() { delete (ptr); } 

    // Overloading dereferncing operator 
    T& operator*() { return *ptr; } 

    // Overloading arrow operator so that 
    // members of T can be accessed 
    // like a pointer (useful if T represents 
    // a class or struct or union type) 
    T* operator->() { return ptr; } 
}; 

int main() 
{ 
    SmartPtr<int> ptr(new int()); 
    *ptr = 20; 
    cout << *ptr; 
    return 0; 
}

unique_ptr

If you are using a unique pointer then if one object is created and pointer P1 is pointing to this one them only one pointer can point this one at one time. So we can’t share with another pointer, but we can transfer the control to P2 by removing P1.

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

class Rectangle { 
    int length; 
    int breadth; 

public: 
    Rectangle(int l, int b) 
    { 
        length = l; 
        breadth = b; 
    } 

    int area() 
    { 
        return length * breadth; 
    } 
}; 

int main() 
{ 

    unique_ptr<Rectangle> P1(new Rectangle(10, 5)); 
    cout << P1->area() << endl; // This'll print 50 

    // unique_ptr<Rectangle> P2(P1); 

    unique_ptr<Rectangle> P2; 
    P2 = move(P1); 

    // This'll print 50 
    cout << P2->area() << endl; 

    // cout<<P1->area()<<endl; 
    return 0; 
}

shared_ptr

If you are using shared_ptr then more than one pointer can point to this one object at a time and it’ll maintain a Reference Counter using use_count() method.

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

class Rectangle { 
    int length; 
    int breadth; 

public: 
    Rectangle(int l, int b) 
    { 
        length = l; 
        breadth = b; 
    } 

    int area() 
    { 
        return length * breadth; 
    } 
}; 

int main() 
{ 

    shared_ptr<Rectangle> P1(new Rectangle(10, 5)); 
    // This'll print 50 
    cout << P1->area() << endl; 

    shared_ptr<Rectangle> P2; 
    P2 = P1; 

    // This'll print 50 
    cout << P2->area() << endl; 

    // This'll now not give an error, 
    cout << P1->area() << endl; 

    // This'll also print 50 now 
    // This'll print 2 as Reference Counter is 2 
    cout << P1.use_count() << endl; 
    return 0; 
}

weak_ptr

It’s much more similar to shared_ptr except it’ll not maintain a Reference Counter.In this case, a pointer will not have a strong hold on the object. The reason is if suppose pointers are holding the object and requesting for other objects then they may form a Deadlock.

Others

std::bitset

header
template class bitset;

Member Functions

// bitset::operator[]
#include <iostream>       // std::cout
#include <bitset>         // std::bitset

int main ()
{
  std::bitset<4> foo;

  foo[1]=1;             // 0010
  foo[2]=foo[1];        // 0110

  std::cout << "foo: " << foo << '\n';

  return 0;
}

rand

int rand(void)
header

Returns a pseudo-random integral number in the range between 0 and RAND_MAX.

v1 = rand() % 100; // v1 in the range 0 to 99
v2 = rand() % 100 + 1; // v2 in the range 1 to 100
v3 = rand() % 30 + 1985; // v3 in the range 1985-2014

/* rand example: guess the number */
#include <stdio.h>      /* printf, scanf, puts, NULL */
#include <stdlib.h>     /* srand, rand */
#include <time.h>       /* time */

int main ()
{
  int iSecret, iGuess;

  /* initialize random seed: */
  srand (time(NULL));

  /* generate secret number between 1 and 10: */
  iSecret = rand() % 10 + 1;

  do {
    printf ("Guess the number (1 to 10): ");
    scanf ("%d",&iGuess);
    if (iSecret<iGuess) puts ("The secret number is lower");
    else if (iSecret>iGuess) puts ("The secret number is higher");
  } while (iSecret!=iGuess);

  puts ("Congratulations!");
  return 0;
}

/*
    Guess the number (1 to 10): 5
    The secret number is higher
    Guess the number (1 to 10): 8
    The secret number is lower
    Guess the number (1 to 10): 7
    Congratulations!
*/

std::uniform_int_distribution

header
Produces random integer values i, uniformly distributed on the closed interval [a, b], that is, distributed according to the discrete probability function

std::uniform_int_distribution satisfies all requirements of RandomNumberDistribution

#include <random>
#include <iostream>

int main()
{
    std::random_device rd;  //Will be used to obtain a seed for the random number engine
    std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib(1, 6);

    for (int n=0; n<10; ++n)
        //Use `distrib` to transform the random unsigned int generated by gen into an int in [1, 6]
        std::cout << distrib(gen) << ' ';
    std::cout << '\n';
}

// 1 1 6 5 2 2 5 5 6 2

参考资料

https://www.geeksforgeeks.org/auto_ptr-unique_ptr-shared_ptr-weak_ptr-2/
_