marvin安装与使用

 
cuDNN安装

cp lib* cudnn_dir/lib64/
cp cudnn.h cudnn_dir/include/
cd cudnn_dir
export LD_LIBRARY_PATH=`pwd`:$LD_LIBRARY_PATH

如出现error while loading shared libraries: libcudnn.so.4: cannot open shared object file: No such file or directory错误,是文件权限问题,可进行如下操作

cd cudnn_dir
rm -rf libcudnn.so libcudnn.so.4
chmod u=rwx,g=rx,o=rx libcudnn.so.4.0.4
ln -s libcudnn.so.4.0.4 libcudnn.so.4
ln -s libcudnn.so.4 libcudnn.so

 
marvin依赖cuda 7.5和cuDNN 4rc
curl -L https://github.com/PrincetonVision/marvin/tarball/master | tar zx
mv PrincetonVision* marvin && cd marvin
./compile.sh

c++模版中的dependent type和typename

Qualified and unqualified names

A qualified name is one that specifies a scope. For instance, in the following C++ program, the references to cout and endl are qualified names:

#include <iostream>
int main()  {
   std::cout << "Hello world!" << std::endl;
}

In both cases, the use of cout and endl began with std::.

Dependent and non-dependent names

A dependent name is a name that depends on a template parameter. Suppose we have the following declaration (not legal C++):

template <class T>
class MyClass {
   int i;
   vector<int> vi;
   vector<int>::iterator vitr;
   T t;
   vector<T> vt;
   vector<T>::iterator viter;
};

The types of the first three declarations are known at the time of the template declaration. However, the types of the second set of three declarations are not known until the point of instantiation, because they depend on the template parameter T.
The names T, vector<T>, and vector<T>::iterator are called dependent names, and the types they name are dependent types. The names used in the first three declarations are called non-dependent names, at the types are non-dependent types.
如下面一段代码中,const_iterator是从属类型,需要在它前面加上typename。否则,在某些情况下,会导致编译解析时产生二义性。

template<typename C>
bool lastGreaterThanFirst(const C& container){
	if(container.empty())
		return false;
	typename C::const_iterator begin(container.begin());
	typename C::const_iterator end(container.end());
	return *--end > *begin;
}

下面进行详细解释

template <class T>
void foo() {
   T::iterator * iter;
   ...
}

如果定义一个嵌套类型的类,

class ContainsAType {
   class iterator { ... }:
   ...
};

foo<ContainsAType>();  在这种情况下,iter将会被声明为一个指向T::iterator 类型的指针变量。
但是如果有人按以下方式声明类,

class ContainsAValue {
   static int iterator;
};

foo<ContainsAValue>(); 在这种情况下,将会有两种解析结果:一个叫做iter的变量,或者静态变量T::iterator。只有在实例化后才能消除他们之间的歧义。
Before a qualified dependent type, you need typename. Without typename, there is a C++ parsing rule that says that qualified dependent names should be parsed as non-types even if it leads to a syntax error. 
头疼,先mark下来。。
参考:http://pages.cs.wisc.edu/~driscoll/typename.html
 
 

STL系列——list

template < class T, class Alloc = allocator<T> > class list;
list是一个序列容器,是以双端链表的形式实现的。list相对于其他序列容器,在任意位置的删除、移动、提取元素的性能更好,但是在随机访问上的性能表现比较差。

Member functions

default (1)	list();
                explicit list (const allocator_type& alloc);
fill (2)	explicit list (size_type n, const allocator_type& alloc = allocator_type());
                list (size_type n, const value_type& val,const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator>
                    list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
copy (4)	list (const list& x);
                list (const list& x, const allocator_type& alloc);
move (5)	list (list&& x);
                list (list&& x, const allocator_type& alloc);
initializer list (6)
                list (initializer_list<value_type> il,const allocator_type& alloc = allocator_type());
copy (1)	list& operator= (const list& x);
move (2)	list& operator= (list&& x);
initializer list (3)
                list& operator= (initializer_list<value_type> il);

用法:

std::list<int> first (3);      // list of 3 zero-initialized ints
std::list<int> second (5);     // list of 5 zero-initialized ints
second = first;
first = std::list<int>();

Iterators

begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
当容器为空时,begin() 返回的迭代器不能解引用,end( )和begin( )返回一样。

Capacity

bool empty() const noexcept;              // 判断是否为空
size_type size() const noexcept;          // list中元素个数
size_type max_size() const noexcept;

Element access

std::list::front( )

 reference front();
const_reference front() const;

std::list::back( )

reference back();
const_reference back() const;

Modifiers

 

STL系列——vector

 
template < class T, class Alloc = allocator<T> > class vector; // generic template
vector用来表示数组,是大小可以动态改变的序列容器。vector内部使用动态分配的数组来存储元素。当元素增加需要分配更多空间的时候,需要将原始数组中内容拷贝到新的数组,然后销毁原始数组。z再分配是一个比较耗时的过程。为了内存使用和再分配之间的平衡,数组的长度的增长,不同的库有b不同的实现策略。
如gcc(这里使用版本是 gcc 5.2), 第一次分配时,capacity() == size()。如果后面增加内容,假设增加长度len, 原始vector长度为size( ),
若len > size(), 重新分配空间,增长后,capacity() = len + size();
若 len <= size( ) 并且 len + size()> capacity(),重新分配空间,增长后,capacity() = size()*2 ;
若len <= size( ) 并且 len+ size( ) <= capacity( ),不重新分配。

构造函数

default (1)   vector();
              explicit vector (const allocator_type& alloc);
fill (2)      explicit vector (size_type n, const allocator_type& alloc = allocator_type());
              vector (size_type n, const value_type& val,
                        const allocator_type& alloc = allocator_type());
range (3)     template <class InputIterator>
                    vector (InputIterator first, InputIterator last,
                                const allocator_type& alloc = allocator_type());
copy (4)      vector (const vector& x);
              vector (const vector& x, const allocator_type& alloc);
move (5) vector (vector&& x);
vector (vector&& x, const allocator_type& alloc);
initializer list (6) vector (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

几种使用方法

// constructors used in the same order as described above:
std::vector<int> first;                                // empty vector of ints
std::vector<int> second (4,100);                       // four ints with value 100
std::vector<int> third (second.begin(),second.end());  // iterating through second
std::vector<int> fourth (third);                       // a copy of third
// the iterator constructor can also be used to construct from arrays:
int myints[] = {16,2,77,29};
std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

赋值构造函数

copy (1)               vector& operator= (const vector& x);
move (2)               vector& operator= (vector&& x);
initializer list (3)   vector& operator= (initializer_list<value_type> il);

迭代器

begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
当容器为空时,begin() 返回的迭代器不能解引用。(string为空时,begin() 可以解引用)

Capacity

size_type size() const noexcept;
size_type max_size() const;           // return the maximum number of elements that the vector can holds. due to known systems or library implementation limitations.

void resize (size_type n);
void resize (size_type n, const value_type& val);

如果n小于当前容器size(), 只保留开头的n个元素;如果n大于容器size(), 通过插入进行扩展。同时如果n 大于当前capacity(), 一个自动空间重分配操作会执行。
size_type capacity() const noexcept;       // 返回当前vector分配的存储空间大小(expressed in terms of elements)
bool empty() const noexcept;
void reserve (size_type n);         // request a change in capacity   当n大于当前capacity时,会导致容器重分配空间;否则没有影响。
void shrink_to_fit();    // 要求容器减小他的capacity到适合他的size,没有强制要求,具体示实现。可能会导致reallocation,但是不会修改vector的size或者内容。

Element Access

// Returns a reference to the element at position n in the vector container.
 reference operator[] (size_type n);
const_reference operator[] (size_type n) const;
// Access element
// Returns a reference to the element at position n in the vector.
reference at (size_type n);
const_reference at (size_type n) const;
//Access first element
//Returns a reference to the first element in the vector.
reference front();
const_reference front() const;
//Access last element
//Returns a reference to the last element in the vector.
 reference back();
const_reference back() const;
// Returns a direct pointer to the memory array used internally by the vector to store its owned elements.
 value_type* data() noexcept;
const value_type* data() const noexcept;

Modifier

range (1)        template <class InputIterator>
                     void assign (InputIterator first, InputIterator last);
fill (2)         void assign (size_type n, const value_type& val);
initializer list (3)  void assign (initializer_list<value_type> il);

range适用于迭代器或者数组
push_back( )、pop_back( )

single element (1)    iterator insert (const_iterator position, const value_type& val);
fill (2)              iterator insert (const_iterator position, size_type n, const value_type& val);
range (3)             template <class InputIterator>
                           iterator insert (const_iterator position, InputIterator first, InputIterator last);
move (4)              iterator insert (const_iterator position, value_type&& val);
initializer list (5)  iterator insert (const_iterator position, initializer_list<value_type> il);
iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

删除指定位置的元素,或者一段区间的元素
返回值为指向删除元素后第一个元素的iterator

void swap (vector& x);

与另一个有相同类型(T, Alloc)的容器的内容进行交换。 包括内容、capacity。其实就是相当于两个指针换了指向的位置,对应的属性(data、size、capacity等)也改变了。

void clear() noexcept;

清除vector里面的内容,将容器大小减小到0。不保证有内存的重新分配。

vector<int>( ).swap(x)

可以强制清空vector x,并重分配空间

template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

C++11新特性,Construct and insert element。

The container is extended by inserting a new element at position. This new element is constructed in place using args as the arguments for its construction.
This effectively increases the container size by one.
template <class... Args>
  void emplace_back (Args&&... args);

Construct and insert element at the end

Allocator

allocator_type get_allocator() const noexcept;
// Returns a copy of the allocator object associated with the vector.

例子

// vector::get_allocator
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> myvector;
  int * p;
  unsigned int i;
  // allocate an array with space for 5 elements using vector's allocator:
  p = myvector.get_allocator().allocate(5);
  // construct values in-place on the array:
  for (i=0; i<5; i++) myvector.get_allocator().construct(&p[i],i);
  std::cout << "The allocated array contains:";
  for (i=0; i<5; i++) std::cout << ' ' << p[i];
  std::cout << '\n';
  // destroy and deallocate:
  for (i=0; i<5; i++) myvector.get_allocator().destroy(&p[i]);
  myvector.get_allocator().deallocate(p,5);
  return 0;
}

关系操作符

(1) template <class T, class Alloc>
  bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(2) template <class T, class Alloc>
  bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(3) template <class T, class Alloc>
  bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(4) template <class T, class Alloc>
  bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(5) template <class T, class Alloc>
  bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(6) template <class T, class Alloc>
  bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

== 操作首先比较size,如果相同,然后使用operator==顺序比较,直到第一个不匹配的
<操作则使用operator<进行顺序比较
其他比较操作内部使用 operator == 或者 operator < 操作进行比较

template <class T, class Alloc>
  void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

交换操作,类似于x.swap(y)

模板特化

template < class T, class Alloc = allocator<T> > class vector; // generic template
template <class Alloc> class vector<bool,Alloc>;               // bool specialization

 

STL系列——string

 
说到string,不得不先介绍basic_string。basic_string是各种字符类型string的泛化。

std::basic_string

template < class charT,
           class traits = char_traits<charT>,    // basic_string::traits_type
           class Alloc = allocator<charT>        // basic_string::allocator_type
           > class basic_string;
Generic string class
The basic_string is the generalization of class string for any character type (see string for a description).

Template parameters

charT
Character type.
The string is formed by a sequence of characters of this type.
This shall be a non-array POD type.
traits
Character traits class that defines essential properties of the characters used by basic_string objects (see char_traits).
traits::char_type shall be the same as charT.
Aliased as member type basic_string::traits_type.
Alloc
Type of the allocator object used to define the storage allocation model. By default, the allocator class template is used, which defines the simplest memory allocation model and is value-independent.
Aliased as member type basic_string::allocator_type.

Note: Because the first template parameter is not aliased as any member type, charT is used throughout this reference to refer to this type.

Template instantiations

      u16string  String of 16-bit characters (class )
      u32string   String of 32-bit characters (class )
string是basic_string类模板的一个实例化,使用char类型,同时使用basic_string默认的char_trailts和allocator类型。

构造函数

default (1)        string();
copy (2)           string (const string& str);
substring (3)      string (const string& str, size_t pos, size_t len = npos);
from c-string (4)  string (const char* s);
from sequence (5)  string (const char* s, size_t n);
fill (6)           string (size_t n, char c);
range (7)          template <class InputIterator>
                   string  (InputIterator first, InputIterator last);
initializer list (8) string (initializer_list<char> il);
move (9)             string (string&& str) noexcept;

使用介绍

std::string s0 ("Initial string");
  // constructors used in the same order as described above:
  std::string s1;
  std::string s2 (s0);
  std::string s3 (s0, 8, 3);                       // from pos = 8, len = 3
  std::string s4 ("A character sequence", 6);      // first n characters pointed by s
  std::string s5 ("Another character sequence");   // pointed by s
  std::string s6a (10, 'x');                   // Fills the string with n consecutive copies of character c.
  std::string s6b (10, 42);      // 42 is the ASCII code for '*'
  std::string s7 (s0.begin(), s0.begin()+7);

赋值运算符 std::string::operator=

string (1)           string& operator= (const string& str);
c-string (2)         string& operator= (const char* s);
character (3)        string& operator= (char c);
initializer list (4) string& operator= (initializer_list<char> il);
move (5)             string& operator= (string&& str) noexcept;

使用介绍

str1 = "Test string: ";   // c-string
str2 = 'x';               // single character
str3 = str1 + str2;       // string

迭代器

begin()、end()       an iterator or a const_iterator(if string object is const)
rbegin()、rend()     a reverse_iterator or a const_reverse_iterator
cbegin()、cend()     const_iterator
crbegin()、crend()

Capacity

size_t size() const noexcept;
size_t length() const noexcept;
// size 和 length相同,返回string实际字节数,不一定和capacity不同
void resize (size_t n);
void resize (size_t n, char c);     // 调整string的长度到length,如果n < length截短;如果n > length,用字符c进行填充,c没有指定,填充空字符
size_t max_size() const noexcept;  // string能够到达的最大长度,与操作系统或者库的实现有关
size_t capacity() const noexcept;  // 当前给string分配的空间,当前空间用完时,自动扩展,理论最大长度为max_size();任意时刻都能修改;可以被reserve()显式地修改
void reserve (size_t n = 0);       //如果n>capacity(),增加capacity()到n;其他情形不强制约定;reserver不改变string内容和length
void clear() noexcept;              // 清空string中内容
bool empty() const noexcept;        // 判断string内容是否为空
void shrink_to_fit();                // C++11, 减少capacity到string的size;不是强制的,具体试容器实现;不改变string内容和length

元素访问

      char& operator[] (size_t pos);
const char& operator[] (size_t pos) const;
// 返回pos位置指向字符的引用,如果pos == length,返回空字符引用 如果string是常量,返回 const char&,否则返回char&
char& at (size_t pos);
const char& at (size_t pos) const;  // 类似于[],不过这里可以检测pos是否小于length,否则抛出异常out_of_range()
char& back();
const char& back() const;  // 返回string中最后一个字符的引用,string不能为空,否则抛出异常
 char& front();
const char& front() const;  // 返回string中第一个字符的引用,string不能为空,否则抛出异常

Modifiers

// std::string::operator+=
// Append to string
// return value: *this
string (1)           string& operator+= (const string& str);
c-string (2)         string& operator+= (const char* s);
character (3)        string& operator+= (char c);
initializer list (4) string& operator+= (initializer_list<char> il);
// Extends the string by appending additional characters at the end of its current value

 

// std::string::append
// Append to string. Extends the string by appending additional characters at the end of its current value
string (1)        string& append (const string& str);
substring (2)     string& append (const string& str, size_t subpos, size_t sublen = npos);
c-string (3)      string& append (const char* s);
buffer (4)        string& append (const char* s, size_t n);
fill (5)          string& append (size_t n, char c);
range (6)         template <class InputIterator>
                      string& append (InputIterator first, InputIterator last);
initializer list(7) string& append (initializer_list<char> il);
void push_back (char c);
// Appends character c to the end of the string, increasing its length by one.
// string::push_back
#include <iostream>
#include <fstream>
#include <string>
int main ()
{
  std::string str;
  std::ifstream file ("test.txt",std::ios::in);
  if (file) {
    while (!file.eof()) str.push_back(file.get());
  }
  std::cout << str << '\n';
  return 0;
}
// return value: *this
string (1)        string& assign (const string& str);
substring (2)     string& assign (const string& str, size_t subpos, size_t sublen = npos);
c-string (3       string& assign (const char* s);
buffer (4)        string& assign (const char* s, size_t n);
fill (5)          string& assign (size_t n, char c);
range (6)         template <class InputIterator>
                     string& assign (InputIterator first, InputIterator last);
initializer list(7) string& assign (initializer_list<char> il);
move (8)            string& assign (string&& str) noexcept;
// Inserts additional characters into the string right before the character indicated by pos (or p):
// return value
// The signatures returning a reference to string, return *this.
// Those returning an iterator, return an iterator pointing to the first character inserted.
string (1)          string& insert (size_t pos, const string& str);
substring (2)       string& insert (size_t pos, const string& str, size_t subpos, size_t sublen = npos);
c-string (3)        string& insert (size_t pos, const char* s);
buffer (4)          string& insert (size_t pos, const char* s, size_t n);
fill (5)            string& insert (size_t pos,   size_t n, char c);
                    iterator insert (const_iterator p, size_t n, char c);
single character (6) iterator insert (const_iterator p, char c);
range (7)            template <class InputIterator>
                         iterator insert (iterator p, InputIterator first, InputIterator last);
initializer list (8)  string& insert (const_iterator p, initializer_list<char> il);
// Erase characters from string
// Erases part of the string, reducing its length:
// return value:
// The sequence version (1) returns *this.
// The others return an iterator referring to the character that now occupies the position of the first character erased, or string::end if no such character exists.
sequence (1)  string& erase (size_t pos = 0, size_t len = npos);
character (2) iterator erase (const_iterator p);
range (3)     iterator erase (const_iterator first, const_iterator last);
string (1)    string& replace (size_t pos,        size_t len,        const string& str);
              string& replace (const_iterator i1, const_iterator i2, const string& str);
substring (2) string& replace (size_t pos,        size_t len,        const string& str,
                 size_t subpos, size_t sublen);
c-string (3)  string& replace (size_t pos,        size_t len,        const char* s);
              string& replace (const_iterator i1, const_iterator i2, const char* s);
buffer (4)    string& replace (size_t pos,        size_t len,        const char* s, size_t n);
              string& replace (const_iterator i1, const_iterator i2, const char* s, size_t n);
fill (5)      string& replace (size_t pos,        size_t len,        size_t n, char c);
              string& replace (const_iterator i1, const_iterator i2, size_t n, char c);
range (6)     template <class InputIterator>
                   string& replace (const_iterator i1, const_iterator i2,
                   InputIterator first, InputIterator last);
initializer list (7) string& replace (const_iterator i1, const_iterator i2, initializer_list<char> il);
// Swap string values
// Exchanges the content of the container by the content of str, which is another string object. Lengths may differ.
// After the call to this member function, the value of this object is the value str had before the call, and the value of str is the value this object had before the call.
void swap (string& str);
// Delete last character
// Erases the last character of the string, effectively reducing its length by one.
void pop_back();

String operations

const char* c_str() const noexcept;     返回C-string类型的字符串,和string::data返回同样的值
allocator_type get_allocator() const noexcept;         Get allocator. Returns a copy of the allocator object associated with the string.

size_t copy (char* s, size_t len, size_t pos = 0) const;

copy将string从pos位置起,长度为len的子字符串,拷贝到s中;返回拷贝的字符数;注意这里不会自动在拷贝的内容后面添加结束符。

// std::string::find
// Searches the string for the first occurrence of the sequence specified by its argument
// return value:
//The position of the first character of the first match.
//If no matches were found, the function returns string::npos.
string (1)    size_t find (const string& str, size_t pos = 0) const noexcept;
c-string (2)  size_t find (const char* s, size_t pos = 0) const;
buffer (3)    size_t find (const char* s, size_t pos, size_type n) const;
character (4) size_t find (char c, size_t pos = 0) const noexcept;
// Searches the string for the first character that matches any of the characters specified in its arguments.
string (1)     size_t find_first_of (const string& str, size_t pos = 0) const noexcept;
c-string (2)   size_t find_first_of (const char* s, size_t pos = 0) const;
buffer (3)     size_t find_first_of (const char* s, size_t pos, size_t n) const;
character (4)  size_t find_first_of (char c, size_t pos = 0) const noexcept;

rfind() 查找最后一个匹配的位置。 find_first_of() 只需要匹配指定制定字符或者字符串中任意一个字符就行,而find()必须匹配整个给定的内容。
与find_first_of( )相反,find_last_of( ) 找最后一个匹配。当pos指定时,只找pos之前的,pos默认为string::npos
find_first_not_of寻找第一个不与指定字符或者字符串中任一字符匹配的位置。  find_last_not_of( ) 与find_last_of( )类似。
string substr (size_t pos = 0, size_t len = npos) const;

string (1)     int compare (const string& str) const noexcept;
substrings (2) int compare (size_t pos, size_t len, const string& str) const;
               int compare (size_t pos, size_t len, const string& str,
                   size_t subpos, size_t sublen = npos) const;
c-string (3)   int compare (const char* s) const;
               int compare (size_t pos, size_t len, const char* s) const;
buffer (4)     int compare (size_t pos, size_t len, const char* s, size_t n) const;

compare返回值0. >0, <0
string::npos是一个静态成员常量值,值定义为-1,是无符号类型size_t最大的可能的代表值。

非成员函数重载

void swap (string& x, string& y);
void swap (string& x, string& y);
string (1)     string operator+ (const string& lhs, const string& rhs);
c-string (2)   string operator+ (const string& lhs, const char*   rhs);
               string operator+ (const char*   lhs, const string& rhs);
character (3)  string operator+ (const string& lhs, char          rhs);
               string operator+ (char          lhs, const string& rhs);
istream& operator>> (istream& is, string& str);   // 从输入流中提取字符串存储到string中,使用空格作为分隔符
ostream& operator<< (ostream& os, const string& str);
istream& getline (istream&  is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);
istream& getline (istream&  is, string& str);
istream& getline (istream&& is, string& str);
//Get line from stream into string
Extracts characters from is and stores them into str until the delimitation character delim is found (or the newline character, '\n', for (2)).
The extraction also stops if the end of file is reached in is or if some other error occurs during the input operation.
If the delimiter is found, it is extracted and discarded, i.e. it is not stored and the next input operation will begin after it.

 
 

stl 中 next_permutation、prev_permutation的原理和使用

next_permutation实现原理
在《STL源码解析》中找到了这个函数,在此也简单叙述一下原理:
在STL中,除了next_permutation外,还有一个函数prev_permutation,两者都是用来计算排列组合的函数。前者是求出下一个排列组合,而后者是求出上一个排列组合。所谓“下一个”和“上一个”,书中举了一个简单的例子:对序列 {a, b, c},每一个元素都比后面的小,按照字典序列,固定a之后,a比bc都小,c比b大,它的下一个序列即为{a, c, b},而{a, c, b}的上一个序列即为{a, b, c},同理可以推出所有的六个序列为:{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a},其中{a, b, c}没有上一个元素,{c, b, a}没有下一个元素。
next_permutation的函数原型如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last
);
template<class BidirectionalIterator, class BinaryPredicate>
bool next_permutation(
      BidirectionalIterator _First,
      BidirectionalIterator _Last,
      BinaryPredicate _Comp
 );

对于第二个重载函数的第三个参数,默认比较顺序为小于。如果找到下一个序列,则返回真,否则返回假。
函数实现原理如下:
在当前序列中,从尾端往前寻找两个相邻元素,前一个记为*i,后一个记为*ii,并且满足*i < *ii。然后再从尾端寻找另一个元素*j,如果满足*i < *j,即将第i个元素与第j个元素对调,并将第ii个元素之后(包括ii)的所有元素颠倒排序,即求出下一个序列了。
代码实现如下:

template<class BidirectionalIterator>
bool next_permutation(
      BidirectionalIterator first,
      BidirectionalIterator last
)
{
    if(first == last)
        return false; //空序列
    BidirectionalIterator i = first;
    ++i;
    if(i == last)
        return false;  //一个元素,没有下一个序列了
    i = last;
    --i;
    for(;;) {
        BidirectionalIterator ii = i;
        --i;
        if(*i < *ii) {
            BidirectionalIterator j = lase;
            while(!(*i < *--j));
            iter_swap(i, j);
            reverse(ii, last);
            return true;
        }
        if(i == first) {
            reverse(first, last);  //全逆向,即为最小字典序列,如cba变为abc
            return false;
        }
    }
}

prev_permutation实现类似,就是反向查找。
例子:

#include<iostream>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	    string str = "abcd";
	    do{
		        cout<<str<<endl;
    	}while(next_permutation(str.begin(), str.end()));
	    cout<<"after loop:\n"<<str<<endl;
    	return 0;
}

输出:

[zhangjun@s3 leetcode]$ ./strtest
abcd
abdc
acbd
acdb
adbc
adcb
bacd
badc
bcad
bcda
bdac
bdca
cabd
cadb
cbad
cbda
cdab
cdba
dabc
dacb
dbac
dbca
dcab
dcba
after loop:
abcd

 
最后一个排列没有下一个排列,用next_permutation会返回false,但使用这个方法后,序列会变成字典序列的第一个。如dcba变成abcd。

数字在排序数组中出现的次数

题目描述

统计一个数字在排序数组中出现的次数。
解法:由于数组是有序的,可以采用二分查找的思想,分别查找连续k值得左边界和有边界,
class Solution {
public:
    int GetStartOfK(vector<int> data, int k){  // 查找左边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size()-1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] >= k)        // 大于等于k时,end向start紧靠,找到左边界
                end = mid - 1;
            else
                start = mid + 1;
        }
        if(data[start] == k)
            return start;
        else
            return -1;
    }
    int GetEndOfK(vector<int> data, int k){  //查找右边界
        if(data.size() == 0)
            return -1;
        int start = 0, end = data.size() - 1;
        int mid = 0;
        while(start <= end){
            mid = (start+end)/2;
            if(data[mid] <= k)         // 小于等于k时, start向end紧靠,找到右边界
                start = mid + 1;
            else
                end = mid - 1;
        }
        if(data[end] == k)
            return end;
        else
            return -1;
    }
    int GetNumberOfK(vector<int> data ,int k) {
        int count = 0;
        if(data.size() > 0){
            int start = GetStartOfK(data, k);
            int end = GetEndOfK(data, k);
            if(start > -1 && end > -1)
                count = end - start + 1;
        }
        return count;
    }
};

 

Merge k Sorted Lists

问题描述:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分而治之的思想:   404ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty())
            return NULL;
        return dac(lists,0,lists.size()-1);
    }
private:
    ListNode* dac(vector<ListNode*>& lists,int low,int high)
    {
        int mid=(low+high)/2;
        if(low==high)
            return lists[low];
        ListNode* l1=dac(lists,low,mid);
        ListNode* l2=dac(lists,mid+1,high);
        return mergeTwoLists(l1,l2);
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1)
            return l2;
        if(!l2)
            return l1;
        if(l1->val<l2->val)
            l1->next=mergeTwoLists(l1->next,l2);
        else
            l2->next=mergeTwoLists(l1,l2->next);
    }
};

使用优先队列priority_queue找到最小的元素   436ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
struct cmp{
    bool operator()(const ListNode* l, const ListNode* r){
        return l->val > r->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> q;
        for(auto l : lists){
            if(l) q.push(l);
        }
        if(q.empty())
            return NULL;
        ListNode* result = q.top();      // head
        q.pop();
        if(result->next)
            q.push(result->next);
        ListNode* pointer = result;
        while(!q.empty()){
            pointer->next = q.top();      // the min
            q.pop();
            pointer = pointer->next;
            if(pointer->next)             // the responding ListNode* is not empty
                q.push(pointer->next);
        }
        return result;
    }
};

使用make_heap 480ms

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
//struct cmp{
//   bool operator()(const ListNode* l, const ListNode* r){
//        return l->val > r->val;
//    }
//};
bool cmp(const ListNode* l, const ListNode* r){
    return l->val > r->val;
}
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
       ListNode head(0);
       ListNode *curr = &head;
       vector<ListNode*> v;
        for(auto l : lists){
            if(l) v.push_back(l);
        }
        make_heap(v.begin(), v.end(), cmp);
        while(v.size()>0){
            curr->next = v.front();      // the min
            pop_heap(v.begin(), v.end(), cmp);
            v.pop_back();
            curr = curr->next;
            if(curr->next){             // the responding ListNode* is not empty
                v.push_back(curr->next);
                make_heap(v.begin(), v.end(), cmp);
            }
        }
        return head.next;
    }
};

 

map与unordered_map

map是一种关联容器,通过键值和关联值存储元素。map使用operator <判断键值是否相同,map的存储是有序的。

unordered_map是一种无序的关联容器,根据键值的hash值判断是否相同,所以是无序存储的。

C++11 智能指针

编程程序,处理动态内存分配问题时,经常会产生内存泄漏的问题。在编程语言中,常常有两个机制解决这个问题:垃圾回收机制,智能指针。
智能指针能够更有效的管理内存,大部分操作和普通指针一样,但有一些特殊的操作。
C++11新引入了三种智能指针:shared_ptr, unique_ptr, weak_ptr。需引入#include<memory>
shared_ptr 是一个类对象,封装了指针对象,重载了两种常见的指针操作符*和->。内部采用了引用计数的机制。当指向内存对象的引用计数为0时,内存对象销毁。 它允许多个shared_ptr指针共享同一个堆内存分配的对象。user_count()的作用是获得当前对象被引用的次数,reset()的作用是释放该指针对对象的引用,将指针设为空。
shared_ptr函数不能使用常见的C++转型函数,需要使用dynamic_pointer_cast()、static_pointer_cast()、const_pointer_cast()。
weak_ptr可以解决循环引用的问题。weak_ptr可以指向shared_ptr指针指向的对象,但不拥有该内存。使用weak_ptr成员lock, 可以返回指向内存的一个shared_ptr对象, 且当所指向对象内存已经无效时,返回一个指针空值(nullptr)。weak_ptr 不能独立存在,它需要指向一个shared_ptr指针指向的内存。weak_ptr不会增加shared_ptr的指针计数。

// 环形引用
classParent
{
    public:
      shared_ptr<Parent>child;
};
classChild
{
    public:
      shared_ptr<Parent>parent;
};
shared_ptr<Parent>pA(newParent);
shared_ptr<Child>pB(newChild);
pA->child=pB;
pB->parent=pA;

 
unique_ptr 没有复制构造函数,可以防止所有权丢失。unique_ptr拥有唯一所有权,可以使用move进行所有权转移。如 unique_ptr<int> second = move(first) 或者 unique_ptr<int> second(move(first))