2

我正在用 C++ 编写一个程序，它将与 Windows Embedded Compact 7 一起使用。我听说在编写嵌入式代码时最好不要动态分配数组。我将跟踪 0 到 50 个对象，因此我最初分配 50 个对象。

Object objectList[50];
int activeObjectIndex[50];
static const int INVALID_INDEX = -1;
int activeObjectCount=0;

activeObjectCount 告诉我实际使用了多少对象，activeObjectIndex 告诉我正在使用哪些对象。如果正在使用第 0、第 7 和第 10 个对象，我希望activeObjectIndex = [0,7,10,-1,-1,-1,...,-1];并且activeObjectCount=3; 随着不同的对象变为活动或不活动，我希望 activeObjectIndex 列表保持有序。

目前，我只是在每个循环结束时对值可能会更改的 activeObjectIndex 进行排序。

首先，有没有比我正在做的更好的方法来跟踪嵌入式系统中的对象（可能是活动的也可能不是活动的）？如果没有，是否有一种算法可以用来在每次添加或删除活动对象时保持对象排序？还是我应该定期做一个冒泡排序或其他东西来保持它们的顺序？

4

5 回答 5

1

std::vector 的开销非常小。您可能遇到的问题是动态调整大小将分配比需要更多的内存。但是，因为您有 50 个元素，所以这根本不应该是一个问题。试一试，只有当你看到强烈的影响时才改变它。

如果您不能/不想从 std::vector 中删除未使用的对象，您可以向您的对象添加一个布尔值，指示它是否处于活动状态？这不需要比使用 activeObjectIndex 更多的内存（可能甚至更少，具体取决于对齐问题）。

要使用布尔值（最后不活动）对数据进行排序，请编写一个函数：

bool compare(const Object & a, const Object & b) {
    if(a.active && !b.active) return true;
    else return false;
}

std::sort(objectList,objectList + 50, &compare); // if you use an array
std::sort(objectList.begin(),objectList.end(), &compare); // if you use std::vector

如果你想使用 activeObjectIndex 进行排序，它会更复杂。如果要使用始终有序的结构，请使用 std::set。但是它需要更多的内存（但对于 50 个元素，这不是问题）。

理想情况下，实现以下功能：

bool operator<(const Object & a, const Object & b) {
    if(a.active && !b.active) return true;
    else return false;
}

这将允许直接使用 std::sort(objectList.begin(), objectList.end()) 或声明将保持排序的 std::set。

于 2012-12-24T21:16:20.733 回答
1

跟踪活动/非活动的一种方法是让活动对象位于双向链表上。当一个对象从非活动状态变为活动状态然后添加到列表中，从活动状态到非活动状态从列表中删除。您可以将这些添加到对象

Object * next, * prev;

所以这不需要内存分配。

于 2012-12-24T21:22:40.487 回答
1

如果不允许动态内存分配，我会使用简单的 c-array 或std::array和一个指向 last+1 对象的索引。对象始终按排序顺序保存。

添加是通过将新对象插入到排序列表的正确位置来完成的。查找插入位置lower_bound或find_if可以使用。对于 50 个元素，第二个可能会更快。删除类似。

于 2012-12-24T21:22:56.433 回答
1

您不应该担心对列表进行排序，因为编写一个方法来搜索索引列表中的活动是什么O(N)，并且在您的特定情况下，摊销到O(1)，因为您的数组似乎足够小额外的验证。

您可以维护检查的最后一个元素的索引，直到达到限制：

unsigned int next(const unsigned int& last) {

    for (unsigned int i = last + 1; i < MAX_ARRAY_SIZE; i++) {
        if (activeObjectIndex[i] != -1) {
            return i;
        }
    }

    return -1;

}

但是，如果你真的想要一个边索引，你可以简单地把数组的大小加倍，为元素创建一个双链表：

activeObjectIndex[MAX_ARRAY_SIZE * 3] = {-1};
activeObjectIndex[i] = "element id";
activeObjectIndex[i + 1] = "position of the previous element";
activeObjectIndex[i + 2] = "position of the next element";
于 2012-12-24T21:26:19.880 回答
1

你有一个难题，答案需要对你的系统有相当多的了解。如果没有这些知识，我无法给出完整的答案。然而，15 年的嵌入式设计经验教会了我以下几点：

  1. 你是对的，你通常不想在运行时分配对象。预分配所有对象，并将它们移动到活动/非活动队列。
  2. 把事情整理好通常很难。也许你不需要。你没有提到它，但我敢打赌你真的只需要将你的对象保存在“使用”和“空闲”池中，并且你正在使用索引来快速查找/删除对象。

我提出以下解决方案。将您的对象更改为以下内容：

class Object {
  Object *mNext, *mPrevious;
public:
  Object() : mNext(this), mPrevious(this) { /* etc. */ }

  void insertAfterInList(Object *p2) {
    mNext->mPrev = p2;
    p2->mNext = mNext;
    mNext = p2;
    p2->mPrev = this;
  }

  void removeFromList() {
    mPrev->mNext = mNext;
    mNext->mPrev = mPrev;
    mNext = mPrev = this;
  }

  Object* getNext() {
    return mNext;
  }

  bool hasObjects() {
    return mNext != this;
  }
};

并使用您的对象：

#define NUM_OBJECTS (50)
Object gObjects[NUM_OBJECTS], gFree, gUsed;

void InitObjects() {
  for(int i = 0; i < NUM_OBJECTS; ++i) {
    gFree.insertAfter(&mObjects[i]);
  }
}

Object* GetNewObject() {
  assert(mFree.hasObjects());
  Object obj = mFree->getNext();
  obj->removeFromList();
  gUsed.insertAfter(obj);
  return obj;
}

void ReleaseObject(Object *obj) {
  obj->removeFromList();
  mFree.insertAfter(obj);
}

编辑以修复一个小故障。现在应该可以工作了，虽然没有经过测试。:)

于 2012-12-24T21:39:43.197 回答