Effective STL

【Effective STL（1）】容器

2018-02-27  本文已影响42人  downdemo

01 仔细选择你的容器

02 小心对“容器无关代码”的幻想

class Widget {...};
vector<Widget> vw;
Widget bestWidget;
... // 给bestWidget一个值
vector<Widget>::iterator i = // 寻找和bestWidget相等的Widget
find(vw.begin(), vw.end(), bestWidget);

class Widget { ... };
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw;
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget);

class Widget { ... };
template<typename T> // 关于为什么这里需要一个template
SpecialAllocator { ... }; // 请参见条款10
typedef vector<Widget, SpecialAllocator<Widget> > WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw; // 仍然能用
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget); // 仍然能用

class CustomerList {
private:
    typedef list<Customer> CustomerContainer;
    typedef CustomerContainer::iterator CCIterator;
    CustomerContainer customers;
public: // 通过这个接口
    ... // 限制list特殊信息的可见性
};

03 使容器里对象的拷贝操作轻量而正确

04 用empty来代替检查size()是否为0

05 尽量使用区间成员函数代替他们的单元素兄弟

v1.assign(v2.begin() + v2.size() / 2, v2.end());

vector<Widget> v1, v2; // 假设v1和v2是Widget的vector
v1.clear();
for (vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
    ci != v2.end(); ++ci)
        v1.push_back(*ci);

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());

int data[numValues]; // 假设numValues在其他地方定义
vector<int> v;
...
v.insert(v.begin(), data, data + numValues); // 把data中的int插入v前部

vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
    insertLoc = v.insert(insertLoc, data[i]);
    ++insertLoc;
}

// 或者用copy，本质上和上面代码是一样的
copy(data, data + numValues, inserter(v, v.begin()));

// 区间构造
container::container(InputIterator begin, // 区间的起点
    InputIterator end); // 区间的终点
// 区间插入，所有序列容器提供
void container::insert(iterator position, // 区间插入的位置
    InputIterator begin, // 插入区间的起点
    InputIterator end); // 插入区间的终点
// 关联容器使用比较函数决定元素位置，省略了position参数
void container::insert(lnputIterator begin, InputIterator end);
// 序列容器区间删除
iterator container::erase(iterator begin, iterator end);
// 关联容器区间删除
void container::erase(iterator begin, iterator end);
// 区间赋值
void container::assign(InputIterator begin, InputIterator end);

06 警惕C++最令人恼怒的解析

ifstream dataFile("ints.dat");
list<int> data(istream_iterator<int>(dataFile), istream_iterator<int>());

ifstream dataFile("ints.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd;
list<int> data(dataBegin, dataEnd);

07 当使用new得指针的容器时，记得在销毁容器前delete那些指针

void f()
{
    vector<A*> v;
    for (int i = 0; i < 10; ++i)
    v.push_back(new A);
    ...
} // 出了作用域A泄漏！

void f()
{
    vector<A*> v;
    ...
    for (vector<A*>::iterator i = v.begin(); i != v.end(); ++i) delete *i;
}

template<typename T>
struct DeleteObject : public unary_function<const T*, void> {
    void operator()(const T* ptr) const
    {
        delete ptr;
    }
};

void f()
{
    ...
    for_each(v.begin(), v.end(), DeleteObject<A>);
}

struct DeleteObject {
    template<typename T> // 模板化加在这里
    void operator()(const T* ptr) const
    {
        delete ptr;
    }
};
// 使用时无需再指定类型
for_each(v.begin(), v.end(), DeleteObject());

void f()
{
    vector<shared_ptr<A>> v;
    for (int i = 0; i < 10; ++i) v.push_back(shared_ptr<A>(new A));
    ...
} // 这里没有泄漏

08 永不建立auto_ptr的容器

09 在删除选项中仔细选择

// 连续内存容器（vector、deque、string）最好的删除方法是erase-remove惯用法
c.erase(remove(c.begin(), c.end(), 1963), c.end()); 
// list的成员函数直接remove更高效
c.remove(1963);
// 关联容器没有remove，方法是调用erase，只花费对数时间（序列容器为线性时间）
c.erase(1963);

c.erase(remove_if(c.begin(), c.end(), f), c.end());
c.remove_if(f); // c为list

remove_copy_if(c.begin(), c.end(), 
    inserter(c2, c2.end()), f);
c.swap(c2);

for (AssocContainer<int>::iterator it = c.begin(); it!= c.end(); ++i) {
    if (badValue(*it)) c.erase(it);
}

for (AssocContainer<int>::iterator it = c.begin(); it != c.end();) {
    if (f(*it)) c.erase(it++);
    else ++it;
}

ofstream logFile;
AssocContainer<int> c;
for (AssocContainer<int>::iterator it = c.begin(); it !=c.end();) {
    if (f(*it)) {
        logFile << "Erasing " << *it <<'\n';
        c.erase(it++); // 删除元素
    }
    else ++it;
}

for (SeqContainer<int>::iterator it = c.begin(); it != c.end();) {
    if (f(*it)){
    logFile << "Erasing " << *it << '\n';
    it = c.erase(i);
    }
    else ++it;
}

10 注意分配器的协定和约束

void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);
// 本质上pointer就是T*的typedef

// list的可能实现
template<typename T, typename Allocator = allocator<T>>
class list {
private:
    Allocator alloc; // 用于T类型对象的分配器
    struct ListNode { // 链表里的节点
        T data:
        ListNode *prev;
        ListNode *next;
    };
    ...
};

template<typename T>
class allocator {
public:
    template<typename U>
    struct rebind {
        typedef allocator<U> other;
    }
...
};

11 理解自定义分配器的正确用法

void* mallocShared(size_t bytesNeeded);
void freeShared(void *ptr);

template<typename T>
class SharedMemoryAllocator {
public:
    ...
    pointer allocate(size_type numObiects, const void *localityHint = 0)
    {
        return static_cast<pointer>(mallocShared(numObiects * sizeof(T)));
    }
    void deallocate(pointer ptrToMemory, size_ type numObjects)
    {
        freeShared(ptrToMiemory);
    }
    ...
};

typedef vector<double, SharedMemoryAllocator<double>> SharedDoubleVec;
...
{ // 开始一个块
    SharedDoubleVec v; // 建立一个元素在共享内存中的vector
    ...
}

// 分配足够的共享内存
void *pVectorMemory = mallocShared(sizeof(SharedDoubleVec));
// 用placement new建立一个SharedDoubleVec对象
SharedDoubleVec *pv = new (pVectorMemory) SharedDoubleVec;
...
pv->~SharedDoubleVec(); // 销毁共享内存中的对象
freeShared(pVectorMemory); // 销毁原来的共享内存块

class Heap1 {
public:
    ...
    static void* alloc(size_t numBytes, const void *memoryBlockToBeNear);
    static void dealloc(void *ptr);
    ...
};
class Heap2 { ... }; // 有相同的alloc/dealloc接口

template<typenameT, typename Heap>
class SpecificHeapAllocator {
public:
    pointer allocate(size_type numObjects, const void *localityHint = 0)
    {
        return static_cast<pointer>(Heap::alloc(numObjects * sizeof(T),
        localityHint));
    }
    void deallocate(pointer ptrToMemory, size_type numObjects)
    {
        Heap::dealloc(ptrToMemory);
    }
    ...
};

// 把v和s的元素放进Heap1
// 把L和m的元素放进Heap2
vector<int, SpecificHeapAllocator<int, Heap1>> v;
set<int, SpecificHeapAllocator<int Heap1>> s;

list<Widget,
    SpecificHeapAllocator<Widget, Heap2>> L;
map<int, string, less<int>,
    SpecificHeapAllocator<pair<const int, string>, Heap2>> m;

12 对STL容器线程安全性的期待现实一些

vector<int> v;
vector<int>::iterator first5(find(v.begin(), v.end(), 5)); // 行1
if (first5 != v.end()){ // 行2
    *first5 = 0; // 行3
}

vector<int> v;
...
getMutexFor(v);
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if (first5 != v.end()) { // 这里现在安全了
    *first5 = 0; // 这里也是
}
releaseMutexFor(v);

// 获取和释放容器的互斥量的类的模板核心
// 忽略了很多细节
template<typename Container>
class Lock {
public:
    Lock(const Containers container) : c(container)
    {
        getMutexFor(c);
    }
    ~Lock()
    {
        releaseMutexFor(c);
    }
private:
    const Container& c;
};

vector<int> v;
...
{ // 建立新块
    Lock<vector<int> > lock(v);
    vector<int>::iterator first5(find(v.begin(), v.end(), 5));
    if (first5 != v.end()) {
    *first5 = 0;
    }
}
上一篇 下一篇

猜你喜欢

热点阅读