C++ Archives - Huahua's Tech Road

C++ 11 Smart Pointers 智能指针

By zxi on June 10, 2020

Example code

C++

// Author: Huahua

#include <iostream>

#include <memory>

class Entity {

public:

Entity() { puts("Entity created!"); }

~Entity() { puts("Entity destroyed!"); }

};

void ex1() {

puts("--------");

puts("Entering ex1");

{

puts("Entering ex1::scope1");

auto e1 = std::make_unique<Entity>();

puts("Leaving ex1::scope1");

}

puts("Leaving ex1");

}

void foo(std::unique_ptr<Entity>) {

puts("Entering foo");

puts("Leaving foo");

}

void ex2() {

puts("--------");

puts("Entering ex2");

auto e1 = std::make_unique<Entity>();

foo(std::move(e1));

// e1 was destoried.

puts("Leaving ex2");

}

void ex3() {

puts("--------");

puts("Entering ex3");

auto e1 = std::make_shared<Entity>();

std::cout << e1.use_count() << std::endl;

{

puts("Entering ex3::scope1");

auto e2 = e1; // use_count ++

std::cout << e1.use_count() << std::endl;

auto e3 = std::move(e2); // use_count remains

std::cout << e1.use_count() << std::endl;

puts("Leaving ex3::scope1");

}

std::cout << e1.use_count() << std::endl;

puts("Leaving ex3");

}

void observe(std::weak_ptr<Entity> ew) {

if (std::shared_ptr<Entity> spt = ew.lock()) {

std::cout << spt.use_count() << std::endl;

std::cout << "entity still alive!" << std::endl;

} else {

std::cout << "entity was expired :(" << std::endl;

}

void ex4() {

puts("--------");

puts("Entering ex4");

std::weak_ptr<Entity> ew;

{

puts("Entering ex4::scope1");

auto e1 = std::make_shared<Entity>();

std::cout << e1.use_count() << std::endl;

ew = e1; // use_count remains

std::cout << e1.use_count() << std::endl;

observe(ew);

puts("Leaving ex4::scope1");

}

observe(ew);

puts("Leaving ex4");

}

int main(int argc, char** argv) {

ex1();

ex2();

ex3();

ex4();

return 0;

}

Output

--------

Entering ex1

Entering ex1::scope1

Entity created!

Leaving ex1::scope1

Entity destroyed!

Leaving ex1

--------

Entering ex2

Entity created!

Entering foo

Leaving foo

Entity destroyed!

Leaving ex2

--------

Entering ex3

Entity created!

Entering ex3::scope1

Leaving ex3::scope1

Leaving ex3

Entity destroyed!

--------

Entering ex4

Entering ex4::scope1

Entity created!

entity still alive!

Leaving ex4::scope1

Entity destroyed!

entity was expired :(

Leaving ex4

Python-Like enumerate() In C++17 – C++ Weekly EP1

By zxi on May 17, 2020

C++

// Author: Huahua

#include <iostream>

#include <string>

#include <vector>

#include <list>

#include <tuple>

using namespace std;

// Python-Like enumerate() In C++17

// http://reedbeta.com/blog/python-like-enumerate-in-cpp17/

template <typename T,

typename TIter = decltype(std::begin(std::declval<T>())),

typename = decltype(std::end(std::declval<T>()))>

constexpr auto enumerate(T && iterable) {

struct iterator {

int i;

TIter iter;

bool operator != (const iterator & other) const { return iter != other.iter; }

void operator ++ () { ++i; ++iter; }

auto operator * () const { return std::tie(i, *iter); }

};

struct iterable_wrapper {

T iterable;

auto begin() { return iterator{ 0, std::begin(iterable) }; }

auto end() { return iterator{ 0, std::end(iterable) }; }

};

// return iterable_wrapper{ iterable }; // this makes a copy if iterable is a rvalue.

return iterable_wrapper{ std::forward<T>(iterable) };

}

struct A {

int val;

A(int val): val(val) { cout << "A(int)" << endl; }

A(const A& a): val(a.val) { cout << "A(A&)" << endl; }

A(A&& a): val(a.val) { cout << "A(A&&)" << endl; }

};

int main(int argc, char** argv) {

vector<int> arr{1, 2, 4};

for (size_t i = 0; i < arr.size(); ++i)

cout << i << " " << arr[i] << endl;

size_t idx = 0;

for (int v : arr)

cout << idx++ << " " << v << endl;

for (auto it = begin(arr); it != end(arr); ++it)

cout << distance(begin(arr), it) << " " << *it << endl;

for (const auto& [i, v] : enumerate(arr))

cout << i << " " << v << endl;

list<string> lst{"hello", "world!"};

for (const auto& [i, v] : enumerate(lst))

cout << i << " " << v << endl;

for (const auto& [i, v] : enumerate(string("abcde")))

cout << i << " " << v << endl;

vector<A> vec;

vec.reserve(3);

vec.emplace_back(1);

vec.emplace_back(2);

vec.emplace_back(4);

for (const auto& [i, v] : enumerate(vec))

cout << i << " " << v.val << endl;

for (const auto& [i, v] : enumerate(vector<A>{A(1), A(2), A(4)}))

cout << i << " " << v.val << endl;

return 0;

}

花花酱 LeetCode 669. Trim a Binary Search Tree

By zxi on September 4, 2017

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input:

/ \

0 2

L = 1

R = 2

Output:

Example 2:

Input:

/ \

0 4

L = 1

R = 3

Output:

This problem can be solved with recursion

There 3 cases in total depends on the root value and L, R

Time complexity: O(n)

Space complexity: O(1)

Solution:

// Author: Huahua

class Solution {

public:

// No cleanup -> memory leak

TreeNode* trimBST(TreeNode* root, int L, int R) {

if(!root) return nullptr;

// val not in range, return the left/right subtrees

if(root->val < L) return trimBST(root->right, L, R);

if(root->val > R) return trimBST(root->left, L, R);

// val in [L, R], recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

};

The previous solution has potential memory leak for languages without garbage collection.

Here’s the full program to delete trimmed nodes.

// Author: Huahua

#include <iostream>

using namespace std;

struct TreeNode {

int val;

TreeNode *left;

TreeNode *right;

TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

class Solution {

public:

// With cleanup -> no memory leak

TreeNode*& trimBST(TreeNode*& root, int L, int R) {

if(!root) return root;

if(root->val < L) {

auto& result = trimBST(root->right, L, R);

deleteTree(root->left);

delete root;

root=nullptr;

return result;

} else if(root->val > R) {

auto& result = trimBST(root->left, L, R);

deleteTree(root->right);

delete root;

root=nullptr;

return result;

} else {

// recusively trim left/right subtrees

root->left = trimBST(root->left, L, R);

root->right = trimBST(root->right, L, R);

return root;

}

void deleteTree(TreeNode* &root) {

if(!root) return;

deleteTree(root->left);

deleteTree(root->right);

delete root;

root=nullptr;

}

};

void PrintTree(TreeNode* root) {

if(!root) {

cout<<"null ";

return;

};

if(!root->left && !root->right) {

cout<<root->val<<" ";

} else {

cout<<root->val<<" ";

PrintTree(root->left);

PrintTree(root->right);

}

int main()

{

TreeNode* root=new TreeNode(2);

root->left=new TreeNode(1);

root->right=new TreeNode(3);

PrintTree(root);

std::cout<<std::endl;

TreeNode* t = Solution().trimBST(root, 3, 4);

PrintTree(t);

std::cout<<std::endl;

// Original root was deleted

PrintTree(root);

std::cout<<std::endl;

return 0;

}

Example output

2 1 3

null

Posts tagged as “C++”

C++ 11 Smart Pointers 智能指针

C++

Output

Python-Like enumerate() In C++17 – C++ Weekly EP1

C++

花花酱 LeetCode 669. Trim a Binary Search Tree