# Difference between map & unordered_map

目前有三个容器我不太了解其内部实现,打算通过 <c++ primer> 进行学习

  1. map
  2. multimap
  3. unordered_map

map

map 是目前最简单的结构,实现的方法是 BST(binary search tree)。因此,其时间复杂度等都与 BST 相同,搜索,增加,删除基本时间都是 log(n)。

use map when

  1. 数据有序
  2. 需要按照有序的顺序获得元素

unordered_map

unordered_map 则是通常所说的 hash table,哈希表,搜索,增加,删除都是以hash表为主,较好的情况是o(1),也就是hash函数可以较好的把元素分布到表中,如果 hash 函数比较糟糕,则每一次添加删除查找,都是完整遍历一个表。

use unordered_map when

  1. 对数据计数
  2. 只需要根据 key 访问 value

简单来讲,就是当你需要使用 vector 来计数的时候,可以用 unordered_map 来代替。

| map             | unordered_map
---------------------------------------------------------
Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table
                | like Red-Black Tree |

search time     | log(n)              | O(1) -> Average
                |                     | O(n) -> Worst Case

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

multimap

multimap containers are generally slower than unordered_multimap containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.

[阅读全文]
CPP  STL 

Ros Kinect Configure Note

This blog for my kinect-v2 ros configure.

Environment

  • Thinkpad P70
  • Ubuntu 14.04
  • indigo

Reference to https://github.com/code-iai/iai_kinect2

Install

Before start, make sure the cuda, cudnn has been configured correctly.

First, you need to install libfreenect2.

I recommend to use export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:/usr/local/cuda/lib64 in your .zshrc or .bashrc (more professional, in bash_profile or .zshenv). You will avoid some problems about library error.

When installing libfreenect2, Use cmake .. -DCMAKE_INSTALL_PREFIX=$HOME/freenect2 -DENABLE_CXX11=ON to generate Makeifle at build/

[阅读全文]
cpp 

C++学习必备


  • 本文出自<svtter.github.io>

  • (cplusplus)[http://www.cplusplus.com]

介绍三个头文件

在/usr/include/stdint.h中包含着各种关于C数据类型的定义,大小等。

  • unistd.h unix standard library header 这个函数库中包含read, write, gitpid等函数
  • stdlib.h standard library header
cpp 

Linux-同步互斥

  • 本文出自<svtter.github.io>

使用pthread实现经典问题:生产者消费者

关于semaphore的相关信息就不再贴出来了。

编译的时候记得-pthread选项。

/*=============================================================================
#
# Author: svtter - [email protected]
#
# QQ : 57180160
#
# Last modified: 2014-10-03 20:35
#
# Filename: producer_consumer.cc
#
# Description: 
#
=============================================================================*/
#include <cstdio>
#include <unistd.h>
#include <semaphore.h>
#include <pthread.h>
#include <sys/types.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
#define N 5
#define item int
// P/V操作
void P(sem_t* sem)
{
    if(sem_wait(sem))
        perror("P error!");
}
void V(sem_t* sem)
{
    if(sem_post(sem))
        perror("V error!");
}
sem_t mutex;
sem_t full;
sem_t empty;
item buffer[N];
int i = , j = -1;
void init_sem()
{
    sem_init(&mutex, , 1);
    sem_init(&full, , );
    sem_init(&empty, , N);
}
void* producer(void *arg)
{
    int product;
    while(1)
    {
        //生成随机数字
        product = rand()%100;
        // cout << "producer running..." << endl;
        P(&empty);
        P(&mutex);
        buffer[i] = product;
        printf("producer produced %d @ %d pos\n",
                product, i);
        i=(i+1)%N;
        V(&mutex);
        V(&full);
        sleep(1);
    }
}
void* consumer(void *arg)
{
    int product, temp;
    while(1)
    {
        // cout << "consumer running..." << endl;
        P(&full);
        P(&mutex);
        j = (j+1)%N;
        product = buffer[j];
        V(&mutex);
        V(&empty);
        printf("Consumer consumed %d @ %d pos\n",
                product, j);
        sleep(3);
    }
}
int main()
{
    //random num
    srand(time(NULL));
    init_sem();
    int error;
    pthread_t producer_t, consumer_t;
    error = pthread_create(&producer_t, NULL, producer, NULL);
    if(error != )
        printf("error in create producer.\n");
    else
        printf("create producer success!\n");
    pthread_create(&consumer_t, NULL, consumer, NULL);
    if(error != )
        printf("error in create consumer.\n");
    else
        printf("create consumer success!\n");
    pthread_join(producer_t, NULL);
    pthread_join(consumer_t, NULL);
    return ;
}

运行结果

生产者消费者

操作系统经典问题:哲学家就餐问题

mutex是c++11的新功能。记得添加C++11支持。(在运行结果中包含编译选项。)

#include <iostream>
#include <mutex>
#include <cstdio>
#include <thread>
#include <semaphore.h>
using namespace std;
#define THINK(i) printf("ph[%d] is thinking...\n", i)
#define EAT(i) printf("ph[%d] eats.\n", i)
void P(mutex &mt)
{
    mt.lock();
}
void V(mutex &mt)
{
    mt.unlock();
}
void P(sem_t* sem)
{
    if(sem_wait(sem))
        perror("P error!");
}
void V(sem_t* sem)
{
    if(sem_post(sem))
        perror("V error!");
}
// 加入unistd.h出现问题,似乎与thread的兼容性比较差,于是重写
void delay()
{
    int sum=;
    for(int i = ; i < 10000000; i++)
        sum += i;
}
mutex fork[5];
sem_t room;
void init()
{
    sem_init(&room, , 4);
}
void philosopher (int i)
{
    for(int j = ; j < 5; j++)
    {
        THINK(i);
        P(&room);
        P(fork[i]);
        P(fork[(i+1)%5]);
        EAT(i);
        V(&room);
        V(fork[i]);
        V(fork[(i+1)%5]);
    }
}
int main()
{
    init();
    thread t[] = {
        thread(philosopher, ),
        thread(philosopher, 1),
        thread(philosopher, 2),
        thread(philosopher, 3),
        thread(philosopher, 4),
    };
    for(int k = ; k < 5; k++)
        t[k].join();
    return ;
}

运行结果

哲学家就餐

操作系统经典问题:读者写者问题

读者优先

  • 使用了c++11的新特性thread
#include <iostream>
#include <mutex>
#include <thread>
using namespace std;
mutex mt, wsem;
int readcount = ;
#define READ(a) cout << a << " is reading..." << endl;
#define FINISH(a) cout << a << " finished reading." << endl;
#define WRITE cout << "writing..." << endl;
void P(mutex &mt)
{
    mt.lock();
}
void V(mutex &mt)
{
    mt.unlock();
}
// 加入unistd.h出现问题,似乎与thread的兼容性比较差,于是重写
void delay()
{
    int sum=;
    for(int i = ; i < 10000000; i++)
        sum += i
}
void read(string a)
{
    for(int i = ; i < 3; i++)
    {
        P(mt);
        readcount++;
        if(readcount == 1)
            P(wsem);
        V(mt);
        READ(a);
        delay();
        P(mt);
        readcount--;
        FINISH(a);
        if(readcount == )
            V(wsem);
        V(mt);
    }
}
void write()
{
    for(int i = ; i < 5; i++)
    {
        P(wsem);
        WRITE;
        delay();
        V(wsem);
    }
}
int main()
{
    thread reader1(read, "svtter");
    thread reader2(read, "sr");
    thread reader3(read, "yym");
    thread reader4(read, "xiaoniu");
    thread writer(write);
    reader1.join();
    reader2.join();
    reader3.join();
    reader4.join();
    writer.join();
    return ;
}

运行结果

由于可以同时阅读,所以读者reading输出可能出现少许问题。

[阅读全文]
cpp