voidinsert(std::string word){ trie_node* current = root; for(char ch : word){ if(current->children.find(ch) == current->children.end()){ current->children[ch] = new trie_node; } current = current->children[ch]; } current->is_end_of_word = true; } //search whether word is in trie tree or not boolsearch(std::string word){ trie_node* current = root; for(char ch : word){ if(current->children.find(ch) == current->children.end()) returnfalse; current = current->children[ch]; } return current != nullptr && current->is_end_of_word; }
//search whether prefix is the prefix of the word in trie tree or not boolstart_with(std::string prefix){ trie_node* current = root; for(char ch : prefix){ if(current->children.find(ch) == current->children.end()){ returnfalse; } current = current->children[ch]; } returntrue; }
typedef vector<int> vi ; typedef vector<float> vf ; typedef vector<vf> matrix ; voidencode_CS45D(const matrix &M , vf &val , vi &nr , vi &ptr , vi &idx){ int m = M.size() , n = M[0].size() ; int NNZ = 0 , nr_t = -1 , t = 0 ; //NNZ : numble of zeros in each slash //nr_t : nr_temp //t indicate whenther there are all zeros in the slash for(int i = 0 , j = 0 ; i < m ; i++){ t = 0 , nr_t++ ; for(int k = i , l = 0 ; (l < n && k >= 0) ; k-- , l++){ if(M[k][l] != 0){ val.push_back(M[k][l]) ; idx.push_back(l) ; NNZ++ , t = 1 ; } } if(t) nr.push_back(nr_t) ; if(NNZ != ptr.back()) ptr.push_back(NNZ) ; }
for(int i = m -1 , j = 1 ; j < n ; j++){ t = 0 , nr_t++ ; for(int k = i , l = j ; l < n ; l++ , k--){ if(M[k][l] != 0){ val.push_back(M[k][l]) ; idx.push_back(l) ; NNZ++ , t = 1 ; } } if(t) nr.push_back(nr_t) ; if(NNZ != ptr.back()) ptr.push_back(NNZ) ; } }
如果在传参中，M的传参方式是matrix M , 在Gdb调试中，无法step进encode_CS45D这个函数，而是会进入M的拷贝子程序中(未知，较为底层)
RAII即Resource Acquisition is Initialization , 中文翻译叫资源获取即初始化 .其实这种叫法很容易让人疑惑，摘一个stackoverflow上的回答:
It’s a really terrible name for an incredibly powerful concept, and perhaps one of the number 1 things that C++ developers miss when they switch to other languages. There has been a bit of a movement to try to rename this concept as Scope-Bound Resource Management, though it doesn’t seem to have caught on just yet.
叫Scope-Bound Resource Management可能更合适。(即范围限制资源管理)
When we say ‘Resource’ we don’t just mean memory - it could be file handles, network sockets, database handles, GDI objects… In short, things that we have a finite supply of and so we need to be able to control their usage. The ‘Scope-bound’ aspect means that the lifetime of the object is bound to the scope of a variable, so when the variable goes out of scope then the destructor will release the resource. A very useful property of this is that it makes for greater exception-safety. For instance, compare this:
#include<iostream> #include<cstdlib> #include<random> voidfun(){ int* array = newint[100]; for(int i = 0 ; i < 100 ; i++) array[i] = rand(); //use the numbers in array to do something.....
Weak_ptr is a smart pointer that holds a non-owning reference to an object. 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 stronghold on the object. The reason is if suppose pointers are holding the object and requesting for other objects then they may form a Deadlock.
// A simple C++ program to demonstrate run-time // polymorphism #include<chrono> #include<iostream> usingnamespace std;
typedef std::chrono::high_resolution_clock Clock;
// To store dimensions of an image classDimension { public: Dimension(int _X, int _Y) { mX = _X; mY = _Y; }
private: int mX, mY; };
// Base class for all image types classImage { public: virtualvoidDraw()= 0;//虚函数等于0，表示该类的任何派生类都要重新定义Draw() virtual Dimension GetDimensionInPixels()= 0;
protected: int dimensionX; int dimensionY; };
// For Tiff Images classTiffImage : public Image { public: voidDraw(){} Dimension GetDimensionInPixels() { returnDimension(dimensionX, dimensionY); } };
// There can be more derived classes like PngImage, // BitmapImage, etc
// Driver code that calls virtual function intmain() { // An image type Image* pImage = new TiffImage;
// Store time before virtual function calls auto then = Clock::now();
// Call Draw 1000 times to make sure performance // is visible for (int i = 0; i < 1000; ++i) pImage->Draw();
// Store time after virtual function calls auto now = Clock::now();
// Image program (similar to above) to demonstrate // working of CRTP #include<chrono> #include<iostream> usingnamespace std;
typedef std::chrono::high_resolution_clock Clock;
// To store dimensions of an image classDimension { public: Dimension(int _X, int _Y) { mX = _X; mY = _Y; }
private: int mX, mY; };
// Base class for all image types. The template // parameter T is used to know type of derived // class pointed by pointer. template <classT> classImage { public: voidDraw() { // Dispatch call to exact type static_cast<T*>(this)->Draw(); } Dimension GetDimensionInPixels() { // Dispatch call to exact type static_cast<T*>(this)->GetDimensionInPixels(); }
protected: int dimensionX, dimensionY; };
// For Tiff Images classTiffImage : public Image<TiffImage> { public: voidDraw() { // Uncomment this to check method dispatch // cout << "TiffImage::Draw() called" << endl; } Dimension GetDimensionInPixels() { returnDimension(dimensionX, dimensionY); } };
// There can be more derived classes like PngImage, // BitmapImage, etc
// Driver code intmain() { // An Image type pointer pointing to Tiffimage Image<TiffImage>* pImage = new TiffImage;
// Store time before virtual function calls auto then = Clock::now();
// Call Draw 1000 times to make sure performance // is visible for (int i = 0; i < 1000; ++i) pImage->Draw();
// Store time after virtual function calls auto now = Clock::now();
模板的实例化：理解这个问题时， 可以想象编译器会实例化哪些模板。MyString<char>会实例化两个模板：objectCounter<MyString<char>> and MyString<char>。调用MyString<char>的构造函数后，会隐式调用objectCounter< MyString<char>>的构造函数，从而使MyString<char>>::count加一。