vector<bool> 看起来像是一个存放布尔变量的容器,但是其实本身其实并不是一个容器,它里面存放的对象也不是布尔变量,这一点在 GCC 源码中 vector<bool> 的注释中写的很清楚:

/**
 *  @brief  A specialization of vector for booleans which offers fixed time
 *  access to individual elements in any order.
 *
 *  Note that vector<bool> does not actually meet the requirements for being
 *  a container.  This is because the reference and pointer types are not
 *  really references and pointers to bool.  See DR96 for details.  @see
 *  vector for function documentation.
 *
 *  @ingroup Containers
 *  @ingroup Sequences
 *
 *  In some terminology a %vector can be described as a dynamic
 *  C-style array, it offers fast and efficient access to individual
 *  elements in any order and saves the user from worrying about
 *  memory and size allocation.  Subscripting ( @c [ ] ) access is
 *  also provided as with C-style arrays.
 */
template<typename _Alloc>
class vector<bool, _Alloc> : protected _Bvector_base<_Alloc>
{
    // XXX: real declaration.
}

C++ 标准中对容器的要求中有一条:

如果 c 是支持 [ ] 操作的 T 类型的容器,那么下面的表达式必须可以编译:

\(T* p = \&c[0]\)

但同样是按照 C++ 标准, vector<bool> 作为一个单独的对象,它里面存放的并非真正的 bool, 为了节省内存,其中存放的是 bitfields ,它用其中的每一个 bit 来表示 bool 。 不同于普通的 [ ] 操作符, vector<bool>::[ ] 返回并不是 bool& ,而是一个可以将 vector<bool> 的内部表示转换成 bool 类型的 proxy ,所以表达式:

vector<bool> c;
bool* p = &c[0];

不能编译。

所以,用到 vector<bool> 的时候,切记它并非真正的容器,如果想用真正的存放 bool 类型的容器,需使用 deque

KDE 下 U 盘挂载失败

2014年9月03日 00:12

重装完 KDE 后发现在 dolphin 中无法挂载 U 盘了,提示 unable to authenticate。但是用 udisksctl 却可以挂载:

yyc@TDesk run > udisksctl mount -b /dev/sdc1
==== AUTHENTICATING FOR org.freedesktop.udisks2.filesystem-mount-other-seat ===
挂载 Generic Mass-Storage (/dev/sdc1) 需要身份验证
Authenticating as: root
password:
==== AUTHENTICATION COMPLETE ===
Mounted /dev/sdc1 at /run/media/yyc/3139-3239.

然后,狠狠心,直接把 udisk 安装到 polkit 里面的配置文件给改了:

<?xml version="1.0" encoding="utf-8"?>
<action id="org.freedesktop.udisks2.filesystem-mount-other-seat">
    <description>Mount a filesystem from a device plugged into another seat</description>
    <description xml:lang="zh_CN">挂载插入另一槽位设备上的文件系统</description>
    <message>Authentication is required to mount the filesystem</message>
    <message xml:lang="zh_CN">挂载文件系统需要身份验证</message>
    <defaults>
        <allow_any>yes</allow_any>
        <allow_inactive>yes</allow_inactive>
        <allow_active>yes</allow_active>
    </defaults>
</action>

然后虽然有安全隐患,但 U 盘就可以用了,自己的机器,应该没什么问题。

假设有若干对象存于一个 vector 中:

class Widget;
vector<Widget> vw;

后来由于某些原因,从该容器中删除了若干对象(参考erase-remove idiom )。对于 vector 和 string 来讲, erase()clear() 并不会改变容器的capacity,也就不会改变他们的内存占用。

swap() 本意是用来交换两个容器的内容( Iterators, pointers, and references),但我们可以用他来快速将容器的 capacity 调整为 合适 的大小:

vector<Widget>(vw).swap(vw);

巧妙之处在于, vector 的拷贝构造函数仅仅拷贝有用的部分而忽略那些未占用的空间,用这个拷贝构造出来的容器来和 vw 进行 swap() 就可以调整 vw 的 capacity 为一个 相对较小的值

这里之所以说是 相对较小的值 而不是与 size() 绝对相等,是因为容器的 Implementation 在构造的时候会自己选取合适的值来保证分配的空间足够容纳所有的元素,但这个值可能会比 size() 大, 可参考Item 14

下面是一个简单的例子,对 vector 进行一些操作,然后输出其 erase, swap,clear 之后的 size 与 capacity:

#include <vector>
#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <fstream>
#include <iterator>

using namespace std;

const int MAX = 1024;

#define show(v, msg)    printf ("%s -- %s: size: %lu, capacity: %lu\n", \
                                #v, msg, v.size(), v.capacity());

int main(int argc, char *argv[])
{
    srand(time(NULL));

    printf("Testing vector...\n");
    vector<int> v;
    show(v, "After init");

    v.reserve(MAX);
    show(v, "After reserve()");

    for (int i = 0; i < MAX; ++i)
    {
        v.push_back(random()%1000);
    }
    show(v, "After Filling");

    v.erase(remove_if(v.begin(), v.end(), [](int x){return x > 100;}), v.end());
    show(v, "After erase()");

    vector<int>(v).swap(v);
    show(v, "After swap()");

    v.clear();
    show(v, "after clear");

    vector<int>().swap(v);
    show(v, "after swap with empty vector");

    return 0;
}

其输出如下:

Testing vector...
v -- After init: size: 0, capacity: 0
v -- After reserve(): size: 0, capacity: 1024
v -- After Filling: size: 1024, capacity: 1024
v -- After erase(): size: 106, capacity: 1024
v -- After swap(): size: 106, capacity: 106
v -- after clear: size: 0, capacity: 106
v -- after swap with empty vector: size: 0, capacity: 0
Program ended with exit code: 0

有时需要支持 C 的接口,但这并不复杂。

对于 vector 来讲, \(v[0]\) 的地址 \(\&v[0]\) 即可作为数组指针传递给 C API:

 1: // Legacy C API.
 2: extern void doSomething(const int* pInts, size_t numInts);
 3: 
 4: vector<int> v;
 5: // ...
 6: // Operations on v.
 7: // ...
 8: 
 9: if (!v.empty())
10: {
11:     doSomething(&v[0], v.size());
12: }

也许有人会说:可以用 v.begin() 来替代 \(\&v[0]\), 但并非永远如此, v.begin() 返回的是一个迭,迭代器指向的对象的地址才是真正的 \(\&v[0]\) ,即:

&*v.begin() == &v[0]

String 对象没有要求保证所有字符串都存放在连续的内存空间,而且 string 内部不会保证内存中对象会以 NULL 结尾,上面对 \(\&v[0]\) 的方法对 string 不一定行得通,对 string 来讲,我们应该使用它提供的成员函数: c_str() , 下面的代码中无需检查 ss 是否为空,因为如果 ss 为空, ss.c_str() 会返回 NULL

13: // Legacy C API:
14: extern void doSomething(const char* str);
15: 
16: string ss;
17: // ...
18: // Do something with ss
19: // ...
20: 
21: doSomething(ss.c_str());

注意第 2 和第 14 行中 C API 中的 const 限定符,调用的函数不应该修改指针指向的内容,但如果我们需要通过调用 C API 来初始化 vector 或 string,应该怎么做?

对于 vector 来讲, Item 14 提到,通过 reserve() 可以预留出足够的空间,而且是连续空间,这样我们可以在调用 C API 进行初始化之前来分配好足够空间,并在初始化之后调用 resize() 来改变容器的大小:

// C API: this function takes a pointer to an array of at most arraySize
// doubles and writes data to it. It returns the number of doubles written,
// which is never more than maxNumDoubles.
size_t fillArray(double *pArray, size_t arraySize);

vector<double> vd;
vd.reserve(maxNumDoubles);
vd.resize(fillArray(&vd[0], maxNumDoubles))

或者更简单的:

vector<double> vd(maxNumDouble);
vd.resize(fillArray(&vd[0], vd.size()));

String 提供的 c_str() 指向的指针是只读的,不能将其传给 C API 进行初始化,但我们可以通过前面提到的方法:将 vector<char> 的指针传给 C API,然后再用这个 vector 来初始化 string

// C API: this function takes a pointer to an array of at most arraySize
// chars and writes data to it. It returns the number of chars written,
// which is never more than maxNumChars.

size_t fillString(char* pArray, size_t arraySize);

vector<char> vc(maxNumChars);
size_t charsWritten = fillString(&vc[0], vc.size());
string s(vc.begin(), vc.begin()+charsWritten));

上面的这个技巧,可以适用于任何的容器,例如如果我们想用 C API 来初始化一个 set:

size_t doSomething(int* pints, size_t numInts); // C API to initialize int array.
vector<int> v(maxNumInts); // This is media
size_t sz = doSomething(&v[0], v.size());
set<int> intSet(v.begin(), v.begin()+sz);

2013/11/01 | Comments

大约一年前,我接触了 Java 中的 Btrace 能够不停机查看线上 JVM 运行情况的特性让我艳羡不已。 另外还有强悍的 jStack 和 jConsole 来进行运行期侦测,JVM 的工业级强度果然不是盖的。

当时公司技术方面也遇到了一些瓶颈,一部分原因是 CPython 本身的 IO 模型问题, 另一方面也和早期代码写的极不工整脱不了关系。万般无奈之下,我们用 Jython 推翻重做了主要业务,效果立竿见影,但同时也把真实问题给规避掉了。

在这之后我们在 JVM 的领导下,走上了康庄大道。但我心中始终还有一个梗, 就是想对性能遇到瓶颈的 Python Process 进行线上侦测。 这篇文章就是开始的第一步。

PS:这篇文章理论上是可行的,但是在我机器(Ubuntu 12.04 / 系统自带 Python) 无法正常执行,会爆出 unable to read python frame information 的问题。解决方法我会在下篇文章中写出。这里只是单纯翻译一下原文。

原文可以移步 https://wiki.python.org/moin/DebuggingWithGdb

继续阅读

vector 和 string 容器在动态插入一个新的对象时,如果容器内空间不够,该容器会:

  1. 重新分配空间
    通常的做法是分配当前 Capacity 大小两倍的空间。
  2. 将旧空间中的所有元素拷贝进新的空间中。
  3. 销毁原有空间中存储的对象。
  4. 销毁原有的空间。

可见一个简单的操作背后实际可能会有许多动作。

例如如果想创建一个容器让其存放 1 ~ 1000 这 1000 个 int 值,如果用下面的方法:

vector<int> v;
for (int i = 1; i < 1001; ++i)
{
    v.push_back(i)
}

典型情况下该过程将会导致约 2 ~ 10 次内存的重新分配 (前面提过,容器内存分配时,典型的方式是空间加倍,则内存从 \(1*sizeof(int)\) 增长倒 \(1000*sizeof(int)\) 约需要 10 次 (\(2^{10} = 1024\))。)

我们可以在容器创建之后通过 Reserve 来显式地让容器预先分配好足够的空间来减少频繁的 reallocation,形如:

vector<int> v;
v.reserve(1000);
for (int i = 1; i < 1001; ++i)
{
    v.push_back(i)
}

另外,简单总结一下 vector 和 string 提供的 size 相关函数:

  • size()
    告之容器内 存放了 多少元素。它并不告之容量。
  • capacity()
    告之该容器 可以 存放多少元素。我们可以通过 \(capacity() - size()\) 来计算剩余的空间。
  • resize(size_t n)
    该函数强制让容器将保存的元素数量从当前数量变成 n 。
    • 如果 n 比当前的容纳的元素数量小,则 Capacity 不变,但 n 以后的元素被销毁。
    • 如果 n 更大,则先重新分配内存 (改变了 Capacity),然后调用元素的 Default Constructer 来初始化需要填充的内存。
  • reserve(size_t n)
    该函数让容器至少可以容纳 n 个元素:
    • n > 当前 capacity: 重新分配空间,改变 Capacity,但不影响 size。
    • n < 当前 capacity: nothing is changed.

 

Effective STL 学习笔记: 多用 vector & string

如果可能的话, 尽量避免自己去写动态分配的数组,转而使用 vector 和 string 。

原书作者唯一想到的一个不用 string 的可能的理由,就是 string 所使用的引用计数 (reference counting) 在多线程下可能会因为并发控制反而导致性能下降。我们可以通过查看文档或者 STL 源面的方法来看 String 是否引入了引用计数,如果 string 在多线程下真的因为引用计数而导致了性能下降,我们可以通过下面的方法来避免:

  1. 看是否可以通过某些方法来禁用引用计数,例如条件编译
    该方法可移植性不佳,但最简单。
  2. 看是否有 string 的非引用计数替代品。
  3. vector<char> 来替代 string
    虽然这样可能会导致很多 string 专属的成员函数不能用,但大多的函数都可以通过 STL 算法来替代。
#include <vector>
#include <stdio.h>
using namespace std;

int main(int argc, char *argv[])
{
    vector<char> ss;
    char c = 'a';
    while (c < 'z') {
        ss.push_back(c);
        c++;
    }

    char* p = ss.data();
    fprintf(stderr, "p = %s\n",p);
    return 0;
}

Output:

~/tmp $ g++ test.cpp -o test
~/tmp $ ./test
p = abcdefghijklmnopqrstuvwxy

 

继续阅读

 

 

Effective STL 笔记 – Item 6 ~ 7: Container and Object Pointer

中间两次笔记被删掉了,简单补一下:

Item 3 中提到如果将对象直接放入容器中,可能会引发问题:

  • 大量的拷贝行为要求对象的拷贝构造代价要小
  • 试图将派生类放入存放基类的容器中会引发 Slicing 问题。

对此的简单方法就是在容器中保存对象 指针 ,但如果直接保存指针的话,我们需要自己维护和管理内存,容易混乱。最好的方法是保存 智能指针(smart pointer shared_ptr))

需要注意的是,这里提倡的是 shared_ptr,不是 autoptr,C++ 标准要求不能声明存放 autoptr 的容器 (Container of AutoPtr, COAP)。原因在于,根据定义,AutoPtr 的 Copy 要求将对象的所有权 (ownership) 转给新的 AutoPtr:

1: auto_ptr<int> p1(new int(1));
2: auto_ptr<int> p2(p1);
3: p1 = p2;

上面的示例中,第一行新建了一个 AutoPtr 对象 p1 用于包装一个 int 指针,第一行执行后,p2 接手了该指针,同时,p1 指向 / NULL / 。第三行执行后, p1 重新获取指针,但 p2 被指向 / NULL / 。

假设如果我们声明了一个用于存放 autoptr 的容器 COAP ,那么在对 COAP 进行操作时,对象的所有权将不可避免的会转移给其他的对象,最后导致容器中的 AutoPtr 指向 NULL ,从而引发各种问题。

How to omit h1 title heading in HTML export

Introduce how to omit h1 title in the exported html.

继续阅读