65.9K
CodeProject 正在变化。 阅读更多。
Home

STL 向量容器介绍

Nitron
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.83/5 (48投票s)

2003年11月4日

9分钟阅读

viewsIcon

323400

downloadIcon

2249

介绍 std::vector，并讨论 STL 算法和谓词。

引言

本文旨在介绍 std::vector，并涵盖一些最常见的 vector 成员函数以及如何正确使用它们。本文还将讨论谓词和函数指针在常见迭代器算法（如 remove_if() 和 for_each()）中的用法。阅读本文后，读者应该能够有效地使用 vector 容器，并且不再需要动态 C 风格数组。

Vector 概述

vector 是 C++ 标准模板库（STL）的一部分；STL 是通用、模板化类和函数的集合，它实现了大量常见数据结构和算法。vector 被认为是一种容器类。与现实生活中的容器一样，这些容器是旨在容纳其他对象的对象。简而言之，vector 是一个动态数组，旨在容纳任何类型的对象，并且能够根据需要增长和收缩。

为了使用 vector，您需要包含以下头文件

#include <vector>

vector 属于 std 命名空间，因此您需要对名称进行限定。这可以通过以下方式实现

using std::vector;
vector<int> vInts;

或者您可以像这样完全限定名称

std::vector<int> vInts;

但是，我建议您不要声明全局命名空间，例如

using namespace std;

这会污染全局命名空间，并可能在以后的实现中引起问题。至于 vector 容器的接口，我已将 vector 的成员函数和运算符列在下表中。

Vector 成员函数 1

函数 描述
赋值 擦除一个 vector 并将指定元素复制到空 vector 中。
at 返回对 vector 中指定位置元素的引用。
back 返回对 vector 最后一个元素的引用。
begin 返回指向容器中第一个元素的随机访问迭代器。
容量 返回 vector 在不分配更多存储空间的情况下可以包含的元素数量。
clear 擦除 vector 的元素。
empty 测试 vector 容器是否为空。
end 返回一个随机访问迭代器，该迭代器指向 vector 结束位置的下一个位置。
erase 从指定位置移除 vector 中的一个元素或一个元素范围。
front 返回对 vector 中第一个元素的引用。
get_allocator 返回 vector 使用的分配器类的对象。
插入 在 vector 的指定位置插入一个元素或多个元素。
max_size 返回 vector 的最大长度。
pop_back 删除 vector 末尾的元素。
push_back 在 vector 末尾添加一个元素。
rbegin 返回反向 vector 中第一个元素的迭代器。
rend 返回反向 vector 结束位置的迭代器。
resize 为 vector 指定新大小。
reserve 为 vector 对象保留最小存储长度。
size 返回 vector 中元素的数量。
swap 交换两个 vector 的元素。
向量 构造一个特定大小或具有特定值元素或具有特定分配器或作为其他 vector 副本的 vector。

Vector 运算符 1

运算符 描述
operator[] 返回对指定位置 vector 元素的引用。

构造 Vector

为 vector 容器提供了几个构造函数。以下是一些最常见的。

构造一个空 vector 来容纳 Widget 类型的对象

vector<Widget> vWidgets;
//     ------
//      |
//      |- Since vector is a container, its member functions
//         operate on iterators and the container itself so 
//         it can hold objects of any type.

构造一个可容纳 500 个 Widget 的 vector

vector<Widget> vWidgets(500);

构造一个可容纳 500 个 Widget 并初始化为 0 的 vector

vector<Widget> vWidgets(500, Widget(0));

从另一个 Widget vector 构造一个 Widget vector

vector<Widget> vWidgetsFromAnother(vWidgets);

向 Vector 添加元素

向 vector 添加元素的默认方法是使用 push_back()。push_back() 成员函数负责将元素添加到 vector 的末尾，并根据需要分配内存。例如，要向 vector<Widget> 添加 10 个 Widget，您可以使用以下代码

for(int i= 0;i<10; i++)
    vWidgets.push_back(Widget(i));

获取 Vector 中元素的数量

很多时候，有必要知道 vector 中有多少元素（如果存在的话）。请记住，vector 是动态的，分配和 push_back() 的数量通常由用户文件或某些其他数据源确定。要测试您的 vector 是否包含任何内容，您可以调用 empty()。要获取元素的数量，您可以调用 size()。例如，如果您想在 vector v 为空时将变量初始化为 -1，或者在不为空时将其初始化为 v 中元素的数量，您可以使用以下代码

int nSize = v.empty() ? -1 : static_cast<int>(v.size());

访问 Vector 中的元素

有两种方法可以访问存储在 vector 中的对象。

  1. vector::at()
  2. vector::operator[]

operator[] 主要为了与旧版 C 代码库兼容而支持。它的操作方式与标准 C 风格数组 operator[] 相同。但是，始终首选使用 at() 成员函数，因为 at() 进行了边界检查，如果我们尝试访问超出 vector 限制的位置，它将抛出异常。然而，operator[] 则不关心，并且可能会导致一些严重的错误，我们现在将演示这一点。

考虑以下代码：

vector<int> v;
v.reserve(10);


for(int i=0; i<7; i++)
    v.push_back(i);


try
{
 int iVal1 = v[7];  // not bounds checked - will not throw
 int iVal2 = v.at(7); // bounds checked - will throw if out of range
}
catch(const exception& e)
{
 cout << e.what();
}

现在，仅仅因为我们为 10 个 int 保留了空间，并不意味着它们已初始化甚至已定义。这种情况最好用下图说明。

您可以自己尝试此代码并观察结果，或者在演示中查看类似的情况。底线：尽可能使用 at()。

从 Vector 中删除元素

将元素放入 vector 相当容易，但将其取出可能会有些棘手。首先，vector 只有 erase()、pop_back() 和 clear() 这些成员函数来删除元素。如果您知道需要删除哪些元素；如果您只需要删除最后一个元素；或者如果您想删除所有元素，那么这些函数就足够了。现在，在您编写一些疯狂的循环来标记要删除的元素并强行实现特定于应用程序的实现之前，请坐下来，深吸一口气，然后对自己说：“S...T...L...”。

remove_if() 算法

现在，我们进入一些有趣的东西。要使用 remove_if()，您需要包含以下文件

#include <algorithm>

remove_if() 接受 3 个参数

  1. iterator _First：指向要操作的范围中第一个元素的迭代器。
  2. iterator _Last：指向要操作的范围中最后一个元素的迭代器。
  3. predicate _Pred：应用于正在评估的迭代器的谓词。

谓词

谓词基本上是指向函数或实际函数对象的指针，该函数或函数对象返回对该对象的自定义评估的“是/否”答案。函数对象需要提供函数调用运算符 operator()()。在 remove_if() 的情况下，通常提供一个派生自 unary_function 的函数对象，以允许用户将数据传递给谓词进行评估。

例如，考虑这样一种情况，您希望根据某些匹配标准从 vector<CString> 中删除元素，即如果字符串包含一个值、以一个值开头、以一个值结尾或是一个值。首先，您需要设置一个数据结构来保存相关数据，类似于以下代码

#include <functional>
enum findmodes 
{
 FM_INVALID = 0,
 FM_IS,
 FM_STARTSWITH,
 FM_ENDSWITH,
 FM_CONTAINS
};
typedef struct tagFindStr
{
 UINT iMode;
 CString szMatchStr;
} FindStr;
typedef FindStr* LPFINDSTR;

然后您可以按照所示实现谓词

class FindMatchingString 
    : public std::unary_function<CString, bool> 
{
    
public: 
    FindMatchingString(const LPFINDSTR lpFS) : m_lpFS(lpFS) {} 
    
    bool operator()(CString& szStringToCompare) const 
    { 
        bool retVal = false;

        switch(m_lpFS->iMode) 
        {
        case FM_IS: 
            { 
                retVal = (szStringToCompare == m_lpFDD->szMatchStr); 
                break;
            }
        case FM_STARTSWITH: 
            { 
                retVal = (szStringToCompare.Left(m_lpFDD->szMatchStr.GetLength())
                            == m_lpFDD->szWindowTitle);
                break;
            } 
        case FM_ENDSWITH: 
            {
                retVal = (szStringToCompare.Right(m_lpFDD->szMatchStr.GetLength()) 
                            == m_lpFDD->szMatchStr);
                break; 
            } 
        case FM_CONTAINS: 
            {
                retVal = (szStringToCompare.Find(m_lpFDD->szMatchStr) != -1);
                break; 
            }
        }
        
        return retVal;
    }
        
private: 
    LPFINDSTR m_lpFS;
};

通过这种实现，您可以有效地从 vector 中删除字符串，如下所示

// remove all strings containing the value of 
// szRemove from vector<CString> vs.

FindStr fs;
fs.iMode = FM_CONTAINS;
fs.szMatchStr = szRemove;

vs.erase(std::remove_if(vs.begin(), vs.end(), FindMatchingString(&fs)), vs.end());

remove_if() 真正做了什么

您可能想知道为什么在上面的示例中调用 remove_if() 时还要调用 erase()。原因非常微妙，对于不熟悉迭代器或 STL 算法的人来说并不直观。由于 remove()、remove_if() 以及所有 remove 系列函数只对迭代器范围进行操作，它们无法操作容器的内部。对 remove_if() 的调用实际上会重新排列正在操作的容器的元素。考虑上面的示例，如果

  1. szRemove = "o"。
  2. vs = 下图所示。

观察结果后，可以看出 remove_if() 实际上返回一个前向迭代器，指向修改后范围的新结束位置，即剩余序列的最后一个元素的下一个位置，该序列不包含指定值。剩余元素可能保留或不保留其原始值，为安全起见，始终假定它们是未知的。

然后，对 erase() 的调用负责实际处理“已移除”的元素。请注意，在上面的示例中，我们将 remove_if() 的结果到 vs.end() 的范围传递给 erase()。

收缩膨胀的 Vector

很多时候，在大量数据删除或大量调用 reserve() 之后，您可能会发现 vector 的内部远大于它们所需的大小。在这种情况下，通常希望“收缩” vector 以适应数据的大小。然而，resize() 成员函数只能增加 vector 的容量。唯一能够改变内部缓冲区大小的成员是 clear()，但这有一些显著的缺点，例如销毁 vector 中的所有内容。那么如何解决这个问题呢？好吧，让我们尝试第一次尝试。

请记住，我们可以从另一个 vector 构造一个 vector。让我们看看会发生什么。假设我们有一个容量为 1000 的 vector v。然后我们调用 size() 并意识到 vector 中只有 7 个元素。哇，我们浪费了大量的内存！让我们尝试从当前 vector 创建一个新 vector。

std::vector<CString> vNew(v);
cout << vNew.capacity();

结果 vNew.capacity() 返回 7。新 vector 只分配了从 v 中获取的足够空间。现在，我不想摆脱 v，因为我可能到处都在使用它。如果我尝试 swap() v 和 vNew 的内部呢？

    vNew.swap(v);
    cout << vNew.capacity();
    cout << v.capacity();

有趣：vNew.capacity() 现在是 1000，而 v.capacity() 是 7。太棒了，成功了。

是的，它可能奏效了，但这并不是一个优雅的解决方案，不是吗？我们如何让这个交换技巧更具风格呢？我们真的需要命名我们的临时变量吗？让我们尝试另一种方法。考虑这段代码

    std::vector<CString>(v).swap(v);

您看到我们做了什么了吗？我们创建了一个临时的未命名变量而不是命名变量，并一步完成了 swap()。更优雅。现在，当临时变量超出作用域时，它将带走其膨胀的内部缓冲区，然后我们只留下一个漂亮的、整洁的 v。

整合

在示例应用程序中，您可以看到如何实现这里讨论的主题。控制台应用程序是这些示例实际操作的分步说明，而 MFC 应用程序主要是演示如何将 STL、算法和谓词与 MFC 结合使用。

结论

我希望本文能为使用 STL vector 容器的开发人员提供有价值的参考和指导。我也希望那些在阅读本文之前对使用 vector 持怀疑态度的人现在不再感到畏惧，并准备好放弃他们的 C 风格数组并尝试一下。

参考文献

  1. Plauger, P.J. 标准 C++ 库参考。2003 年 2 月。MSDN。
  2. Schildt, Herbert. C++ 从基础开始，第二版。伯克利：1998。
  3. Sutter, Herb. 更多异常 C++。印第安纳波利斯：2002。
© . All rights reserved.