malloc realloc calloc

1、malloc

Defined in header <stdlib.h>
void* malloc( size_t size );
Allocates size bytes of uninitialized storage.

malloc is thread-safe. (since C11)
Parameters
size – number of bytes to allocate

Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc().
On failure, returns a null pointer.
2、calloc

Defined in header <stdlib.h>
void* calloc( size_t num, size_t size );
Allocates memory for an array of num objects of size size and initializes all bits in the allocated storage to zero.

calloc is thread-safe. (since C11)
Parameters
num – number of objects
size – size of each object

 Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc().
On failure, returns a null pointer.
3、realloc

Defined in header <stdlib.h>
void *realloc( void *ptr, size_t new_size );
Reallocates the given area of memory. It must be previously allocated by malloc(), calloc() or realloc() and not yet freed with free, otherwise, the results are undefined.
The reallocation is done by either:
a) expanding or contracting the existing area pointed to by ptr, if possible. The contents of the area remain unchanged up to the lesser of the new and old sizes. If the area is expanded, the contents of the new part of the array are undefined.
b) allocating a new memory block of size new_size bytes, copying memory area with size equal the lesser of the new and the old sizes, and freeing the old block.

It’s thread-safe since C11.
Parameters
ptr – pointer to the memory area to be reallocated
new_size – new size of the array

Return value

On success, returns the pointer to the beginning of newly allocated memory. The returned pointer must be deallocated with free() or realloc(). The original pointer ptr is invalidated and any access to it is undefined behavior (even if reallocation was in-place).
On failure, returns a null pointer. The original pointer ptr remains valid and may need to be deallocated with free() or realloc().

Two Sum

题目1:Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

题目意思是从给定一组数中,选出2个数,他们的和满足给定的一个目标值,按顺序输出这两个数对应的索引。(假设正好只有一个解)
思路:先按从小到大顺序数组排序,然后从小到大依次遍历,先确定一个较小的数,然后再其后面的数中使用二分查找的方式找另外一个数。

class Solution {
public:
    struct Item{
        int value;
        int index;
        Item(int pvalue, int pindex):value(pvalue), index(pindex){};
        bool operator<(const Item &it)
        {
            return value < it.value;
        }
    };
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        vector<Item> data;
        for(int i = 0; i <nums.size(); i++)
        {
            data.push_back(Item(nums[i], i));
        }
        sort(data.begin(), data.end());
        int lindex = 0, rindex = data.size() - 1;
        for( int lindex = 0; lindex <= rindex; lindex++){
            if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target)){
                result.push_back(min(data[lindex].index+1, data[lindex+1].index+1));
                result.push_back(max(data[lindex].index+1, data[lindex+1].index+1));
                return result;
            }
            else if((lindex > 0) && (data[lindex].value ==data[lindex+1].value) && (data[lindex].value * 2 == target))
                continue;
            int ret = -1;
            int remain = target - data[lindex].value;
            int left = lindex, right = rindex;
            while(left <= right){
                int mid = (left+right)/2;
                if(data[mid].value == remain){   // must compare the index
                    result.push_back(min(data[lindex].index+1, data[mid].index+1));
                    result.push_back(max(data[lindex].index+1, data[mid].index+1));
                    return result;
                }
                else if(data[mid].value < remain){
                    left = mid + 1;
                }
                else
                    right = mid - 1;
            }
        }
    }
};

时间复杂度为O(nlogn)
听说使用hashmap能将为O(n) 后续再探讨

C++ IO(get, getline)

1、get

std::basic_istream::get
int_type get(); (1)
basic_istream& get( char_type& ch ); (2)
basic_istream& get( char_type* s, std::streamsize count ); (3)
basic_istream& get( char_type* s, std::streamsize count, char_type delim ); (4)
basic_istream& get( basic_streambuf& strbuf ); (5)
basic_istream& get( basic_streambuf& strbuf, char_type delim ); (6)

2、getline

std::getline
Defined in header <string>
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>& input,
                                        std::basic_string<CharT,Traits,Allocator>& str,
                                            CharT delim ); (1)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>&& input,
                                         std::basic_string<CharT,Traits,Allocator>& str,
                                            CharT delim ); (1)  (since C++11)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>& input,
                                          std::basic_string<CharT,Traits,Allocator>& str ); (2)
template< class CharT, class Traits, class Allocator >
std::basic_istream<CharT,Traits>& getline( std::basic_istream<CharT,Traits>&& input,
                                            std::basic_string<CharT,Traits,Allocator>& str ); (2)  (since C++11)

 
get()和getline()的区别,get()不读取换行符,会将换行符留在输入流中,getIine()抽取并丢弃输入流中的换行符
 
cin使用方法 http://blog.sina.com.cn/s/blog_771bd2c9010137bf.html

C++ 11 auto

C++11中auto的功能:实现变量的自动类型的推断。auto可以在变量声明的时候根据变量初始值的类型自动为变量选择匹配的类型。(使用typeid运算符可以输出变量的类型)auto自动类型推断发生在编译期间。
auto虽然可以使一些冗长的代码简化,但为了使代码更加清晰易懂,也应该合理地使用。下述情形可以使用:
用于替代冗长复杂、变量使用范围专一的变量声明。

#include<string>
#include<vector>
int main()
{
    std::vector<std::string> vs;
    for (auto i = vs.begin(); i != vs.end(); i++)
    {
        //..
    }
}

定义模板函数时,用于声明依赖模板参数的变量类型。

template <typename _Tx,typename _Ty>
void Multiply(_Tx x, _Ty y)
{
    auto v = x*y;
    std::cout << v;
}

上面代码只有在编译时,才能知道变量v类型。
模板函数依赖于模板参数的返回值

template <typename _Tx, typename _Ty>
auto multiply(_Tx x, _Ty y)->decltype(_Tx*_Ty)
{
    return x*y;
}

无法在编译器前确定模板参数类型,所以也无法知道返回值类型,这里我们可以使用auto。auto在这里的作用也称为 返回值占位 ,它只是为函数返回值占了一个位置,真正的返回值是后面的decltype(_Tx*_Ty)。

  • auto 变量必须在定义时初始化,这类似于const关键字。
  • 定义在一个auto序列的变量必须始终推导成同一类型。例如:
        auto a4 = 10, a5 = 20, a6 = 30;//正确
        auto b4 = 10, b5 = 20.0, b6 = 'a';//错误,没有推导为同一类型

    使用auto关键字做类型自动推导时,依次施加一下规则:

  • 如果初始化表达式是引用,则去除引用语义。
    int a = 10;
    int &b = a;
    auto c = b;//c的类型为int而非int&(去除引用)
    auto &d = b;//此时c的类型才为int&
    c = 100;//a =10;
    d = 100;//a =100;
  • 如果初始化表达式为const或volatile(或者两者兼有),则除去const/volatile语义。
    const int a1 = 10;
    auto  b1= a1; //b1的类型为int而非const int(去除const)
    const auto c1 = a1;//此时c1的类型为const int
    b1 = 100;//合法
    c1 = 100;//非法
  • 如果auto关键字带上&号,则不去除const语意。
    const int a2 = 10;
    auto &b2 = a2;//因为auto带上&,故不去除const,b2类型为const int
    b2 = 10; //非法

    这是因为不是去掉了const,则b2为a2的非const引用,通过b2可以改变a2的值,则显然是不合理的。

  • 初始化表达式为数组时,auto关键字推导类型为指针。
        int a3[3] = { 1, 2, 3 };
        auto b3 = a3;
        cout << typeid(b3).name() << endl;

    程序将输出

    int *
  • 若表达式为数组且auto带上&,则推导类型为数组类型。
       int a7[3] = { 1, 2, 3 };
        auto & b7 = a7;
        cout << typeid(b7).name() << endl;

    程序输出

    int [3]
  • 函数或者模板参数不能被声明为auto
    void func(auto a)  //错误
    {
        //...
    }
  • 时刻要注意auto并不是一个真正的类型。auto仅仅是一个占位符,它并不是一个真正的类型,不能使用一些以类型为操作数的操作符,如sizeof或者typeid。
       cout << sizeof(auto) << endl;//错误
       cout << typeid(auto).name() << endl;//错误

C++ values 和rvalues

C++左值和右值是一个不容易理解的概念,而且经常由于使用不正确而出现错误。
这里看到一个定义:
An lvalue (locator value) represents an object that occupies some identifiable location in memory (i.e. has an address).
rvalues are defined by exclusion, by saying that every expression is either an lvalue or an rvalue. Therefore, from the above definition of lvalue, an rvalue is an expression that does not represent an object occupying some identifiable location in memory.
 
左值变量与右值变量之间的转换
除了数组、不完整类型和函数,所有左值变量都能转换为右值。反之,则不行。但解引用操作符*是一个意外,能将右值变为左值,如*(p+1) = 10, p+1是右值,但*(p+1)是左值。 同时,&操作符也能将左值变为右值。

string 和 integer之间转换

Implement atoi to convert a string to an integer.

class Solution {
public:
    int myAtoi(string str) {
        if(str.size() == 0)
            return 0;
        int pos = 0;
        while(str[pos] == ' ')
            pos ++;
        bool isPositive = true;
        if(str[pos] == '-'){
            isPositive = false;
            pos++;
        }
        else if(str[pos] == '+'){
            isPositive = true;
            pos++;
        }
        if(str[pos] < '0' || str[pos] >'9')
            return 0;
        int val = 0;
        while(str[pos] >= '0' && str[pos] <= '9')
        {
            if(val > INT_MAX/10 ||((val == INT_MAX/10) && str[pos] - '0' >= 8))
                return isPositive?INT_MAX:INT_MIN;
            val = val *10 + str[pos]-'0';
            ++pos;
        }
        if(isPositive)
            return val;
        else
            return -val;
    }
};

interger to string

string itos(int x){
   int val = (x>=0)? x:-x;
   string res;
   while(val){
      res = char(val%10+'0') + res;
      val = val/10;
   }
   if(x < 0)
      res = '-'+res;
   return res;
}

 
还可以通过stringstream实现转换(需include<sstream>)

string str = "123234afi";
int num;
stringstream ss;
ss<<str;
ss>>num;   // num返回123234;如果str="123 23",num 返回123;如果str = "ab123",num返回0
int num = -234;
stringstream ss;
string file;
ss<<num;
ss>>file;

stringstream重新使用时应该清理掉
ss.str(“”);
ss.clear();
另外,C++11引入to_string()能将数值类型转换为string类型。

string to_string (int val);
string to_string (long val);
string to_string (long long val);
string to_string (unsigned val);
string to_string (unsigned long val);
string to_string (unsigned long long val);
string to_string (float val);
string to_string (double val);
string to_string (long double val);
Convert numerical value to string
Returns a string with the representation of val.

2015年华为上机实习(济南)

题目一:
将输入字符串中,紧接数字的第一个连续多次(2或以上)出现的字母去掉一个。如输入 325abbcddaf678ffrtssh,输出325abcddaf678frtssh

/*
 * test.cpp
 *
 *  Created on: 2015年5月6日
 *      Author: zhangjun
 */
#include<stdio.h>
#include<string.h>
#define MAX 1000
int isdig(char a)
{
   	if(a>'0'&&a<'9')
		      return 1;
	   else
      		return 0;
}
int main()
{
   	char data[MAX];
	   char result[MAX];
	   scanf("%s", data);
	   int len = strlen(data);
	   int i;
	   int label = 0;
	   int j = 0;
	   for( i = 0; i < len; i++)
	   {
		      if(isdig(data[i]))
			      label = 1;
		      if((label == 1)&&!(isdig(data[i]))&&(data[i]==data[i-1]))
		      {
			         label = 0;
			         continue;
		      }
		      else
			         result[j++] = data[i];
	   }
   	result[j] = 0;
	   printf("%sn", result);
	   return 0;
}

 

统计一行字符中有多少个单词

思路:如果一个字符是字母,而它之前字符不是字母,则表示新单词开始,此时单词计数加1;如果一个字符是字母,并且它之前的字符也是字母,则表示还是原来单词,单词计数不变。 使用一个标签,表示当前字符是否处于一个单词中。

#include<stdio.h>
#include<iostream>
#include<string.h>
int wordcount(char data[], int size)
{
	if(size <= 1)
		return 0;
	int i = 0, word = 0, count = 0;
	while( i < size)
	{
		while( i < size && (data[i] < 'A' ||(data[i] > 'Z'&&data[i] < 'a')||data[i] > 'z'))
			i++;
		while( i < size && ((data[i] >= 'A'&&data[i]<= 'Z')||(data[i] >= 'a'&&data[i]<= 'z')))
		{
			i ++;
			if(word == 0)
			{
				word = 1;
				count ++;
			}
		}
		word = 0;
	}
	return count;
}
int main()
{
	char data[100];
	gets(data);
	std::cout<<wordcount(data, strlen(data))<<std::endl;
}

 

一致性hash C++实现

http://martinbroadhurst.com/Consistent-Hash-Ring.html

Consistent Hash Ring

Introduction

Consistent hashing was first described in a paper, Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web (1997) by David Karger et al. It is used in distributed storage systems like Amazon Dynamo, memcached, Project Voldemort and Riak.

The problem

Consistent hashing is a very simple solution to a common problem: how can you find a server in a distributed system to store or retrieve a value identified by a key, while at the same time being able to cope with server failures and network partitions?
Simply finding a server for value is easy; just number your set of s servers from 0 to s – 1. When you want to store or retrieve a value, hash the value’s key modulo s, and that gives you the server.
The problem comes when servers fail or become unreachable through a network partition. At that point, the servers no longer fill the hash space, so the only option is to invalidate the caches on all servers, renumber them, and start again. Given that, in a system with hundreds or thousands of servers, failures are commonplace, this solution is not feasible.

The solution

In consistent hashing, the servers, as well as the keys, are hashed, and it is by this hash that they are looked up. The hash space is large, and is treated as if it wraps around to form a circle – hence hash ring. The process of creating a hash for each server is equivalent to placing it at a point on the circumference of this circle. When a key needs to be looked up, it is hashed, which again corresponds to a point on the circle. In order to find its server, one then simply moves round the circle clockwise from this point until the next server is found. If no server is found from that point to end of the hash space, the first server is used – this is the “wrapping round” that makes the hash space circular.
The only remaining problem is that in practice hashing algorithms are likely to result in clusters of servers on the ring (or, to be more precise, some servers with a disproportionately large space before them), and this will result in greater load on the first server in the cluster and less on the remainder. This can be ameliorated by adding each server to the ring a number of times in different places. This is achieved by having a replica count, which applies to all servers in the ring, and when adding a server, looping from 0 to the count – 1, and hashing a string made from both the server and the loop variable to produce the position. This has the effect of distributing the servers more evenly over the ring. Note that this has nothing to do withserver replication; each of the replicas represents the same physical server, and replication of data between servers is an entirely unrelated issue.

Implementation

I’ve written an example implementation of consistent hashing in C++. As you can imagine from the description above, it isn’t terribly complicated. Here is the main class:

template <class Node, class Data, class Hash = HASH_NAMESPACE::hash<const char*> >
class HashRing
{
public:
   typedef std::map<size_t, Node> NodeMap;
   HashRing(unsigned int replicas)
     : replicas_(replicas), hash_(HASH_NAMESPACE::hash<const char*>())
   {
   }
   HashRing(unsigned int replicas, const Hash& hash)
     : replicas_(replicas), hash_(hash)
   {
   }
   size_t AddNode(const Node& node);
   void RemoveNode(const Node& node);
   const Node& GetNode(const Data& data) const;
private:
   NodeMap ring_;
   const unsigned int replicas_;
   Hash hash_;
};
template <class Node, class Data, class Hash>
size_t HashRing<Node, Data, Hash>::AddNode(const Node& node)
{
   size_t hash;
   std::string nodestr = Stringify(node);
   for (unsigned int r = 0; r < replicas_; r++) {
      hash = hash_((nodestr + Stringify(r)).c_str());
      ring_[hash] = node;
   }
   return hash;
}
template <class Node, class Data, class Hash>
void HashRing<Node, Data, Hash>::RemoveNode(const Node& node)
{
   std::string nodestr = Stringify(node);
   for (unsigned int r = 0; r < replicas_; r++) {
      size_t hash = hash_((nodestr + Stringify(r)).c_str());
      ring_.erase(hash);
   }
}
template <class Node, class Data, class Hash>
const Node& HashRing<Node, Data, Hash>::GetNode(const Data& data) const
{
   if (ring_.empty()) {
      throw EmptyRingException();
   }
   size_t hash = hash_(Stringify(data).c_str());
   typename NodeMap::const_iterator it;
   // Look for the first node >= hash
   it = ring_.lower_bound(hash);
   if (it == ring_.end()) {
      // Wrapped around; get the first node
      it = ring_.begin();
   }
   return it->second;
}

 

A few points to note:

  • The default hash function is hash from <map>.
    In practice you probably don’t want to use this. Something like MD5 would probably be best.
  • I had to define HASH_NAMESPACE because g++ puts the non-standard hash in a different namespace than that which other compilers do.
    Hopefully this will all be resolved with the widespread availablity of std::unordered_map.
  • The Node and Data types need to have operator << defined for a std::ostream.
    This is because I write them to an ostringstream in order to “stringify” them before getting the hash.

I’ve also written an example program that simulates using a cluster of cache servers to store and retrieve some data.

Source code

You can browse the source code and example program here:

Here is a compressed tar archive containing the source code, example program and makefile:

time,gettimeofday,clock_gettime,_ftime

time()提供了秒级的精确度
1、头文件 <time.h>
2、函数原型
time_t time(time_t * timer)
函数返回从TC1970-1-1 0:0:0开始到现在的秒数
用time()函数结合其他函数(如:localtime、gmtime、asctime、ctime)可以获得当前系统时间或是标准时间。
#include <time.h>
#include <stdio.h>
int main(void)
{
    time_t t;
    t = time(NULL);
    printf("The number of seconds since January 1, 1970 is %ld",t);
    return 0;
}
#include <stdio.h>
#include <stddef.h>
#include <time.h>
int main(void)
{
    time_t timer;//time_t就是long int 类型
    struct tm *tblock;
    timer = time(NULL);//这一句也可以改成time(&timer);
    tblock = localtime(&timer);
    printf("Local time is: %s/n",asctime(tblock));
    return 0;
}

 

gettimeofday()提供了微秒级的精确度
1、头文件 <time.h>
2、函数原型
int gettimeofday(struct timeval *tv, struct timezone *tz);
gettimeofday()会把目前的时间由tv所指的结构返回,当地时区的信息则放到tz所指的结构中(可用NULL)。
参数说明:
    timeval结构定义为:
    struct timeval
    {
        long tv_sec; /*秒*/
        long tv_usec; /*微秒*/
    };
    timezone 结构定义为:
    struct timezone
    {
        int tz_minuteswest; /*和Greenwich 时间差了多少分钟*/
        int tz_dsttime; /*日光节约时间的状态*/
    };
    上述两个结构都定义在/usr/include/sys/time.h。tz_dsttime 所代表的状态如下
        DST_NONE /*不使用*/
        DST_USA /*美国*/
        DST_AUST /*澳洲*/
        DST_WET /*西欧*/
        DST_MET /*中欧*/
        DST_EET /*东欧*/
        DST_CAN /*加拿大*/
        DST_GB /*大不列颠*/
        DST_RUM /*罗马尼亚*/
        DST_TUR /*土耳其*/
        DST_AUSTALT /*澳洲(1986年以后)*/
返回值: 成功则返回0,失败返回-1,错误代码存于errno。附加说明EFAULT指针tv和tz所指的内存空间超出存取权限。
#include<stdio.h>
#include<time.h>
int main(void)
{
    struct timeval tv;
    struct timezone tz;
    gettimeofday (&tv , &tz);
    printf(“tv_sec; %d/n”, tv,.tv_sec) ;
    printf(“tv_usec; %d/n”,tv.tv_usec);
    printf(“tz_minuteswest; %d/n”, tz.tz_minuteswest);
    printf(“tz_dsttime, %d/n”,tz.tz_dsttime);
    return 0;
}

 

clock_gettime( ) 提供了纳秒级的精确度
1、头文件 <time.h>
2、编译&链接。在编译链接时需加上 -lrt ;因为在librt中实现了clock_gettime函数
3、函数原型
int clock_gettime(clockid_t clk_id, struct timespect *tp);
    参数说明:
    clockid_t clk_id 用于指定计时时钟的类型,有以下4种:
        CLOCK_REALTIME:系统实时时间,随系统实时时间改变而改变,即从UTC1970-1-1 0:0:0开始计时,中间时刻如果系统时间被用户该成其他,则对应的时间相应改变
        CLOCK_MONOTONIC:从系统启动这一刻起开始计时,不受系统时间被用户改变的影响
        CLOCK_PROCESS_CPUTIME_ID:本进程到当前代码系统CPU花费的时间
        CLOCK_THREAD_CPUTIME_ID:本线程到当前代码系统CPU花费的时间
    struct timespect *tp用来存储当前的时间,其结构如下:
        struct timespec
        {
            time_t tv_sec; /* seconds */
            long tv_nsec; /* nanoseconds */
        };
    返回值。0成功,-1失败
#include<stdio.h>
#include<time.h>
int main()
{
    struct timespec ts;
    clock_gettime(CLOCK_REALTIME, &ts);
    printf("CLOCK_REALTIME: %d, %d", ts.tv_sec, ts.tv_nsec);
    clock_gettime(CLOCK_MONOTONIC, &ts);//打印出来的时间跟 cat /proc/uptime 第一个参数一样
    printf("CLOCK_MONOTONIC: %d, %d", ts.tv_sec, ts.tv_nsec);
    clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &ts);
    printf("CLOCK_PROCESS_CPUTIME_ID: %d, %d", ts.tv_sec, ts.tv_nsec);
    clock_gettime(CLOCK_THREAD_CPUTIME_ID, &ts);
    printf("CLOCK_THREAD_CPUTIME_ID: %d, %d", ts.tv_sec, ts.tv_nsec);
    printf("/n%d/n", time(NULL));
    return 0;
}
/proc/uptime里面的两个数字分别表示:
the uptime of the system (seconds), and the amount of time spent in idle process (seconds).
把第一个数读出来,那就是从系统启动至今的时间,单位是秒

 

_ftime()提供毫秒级的精确度
1、头文件 <sys/types.h> and <sys/timeb.h>
2、函数原型
void _ftime(struct _timeb *timeptr);
参数说明:
    struct _timeb
    {
        time_t time;
        unsigned short millitm;
        short timezone;
        short dstflag;
    };
#include <stdio.h>
#include <sys/timeb.h>
#include <time.h>
void main( void )
{
    struct _timeb timebuffer;
    char *timeline;
    _ftime( &timebuffer );
    timeline = ctime( & ( timebuffer.time ) );
    printf( "The time is %.19s.%hu %s", timeline, timebuffer.millitm, &timeline[20] );
}

 
reference:
http://blog.csdn.net/wind19/article/details/12975173
http://blog.csdn.net/sunlylorn/article/details/6313278