イム書き込みタイマーマネージャー、：、なぜ必要とするCで
キーは、できるだけ小さくする必要があります。 最初はリンクされたリストについて考えましたが、途中の部分を取り除くと、リストを再構築する必要があり、時間がかかることがあります。典型的なダイナミック配列は同じです - 私はその構造をrebilidingするとき、私はそれらのいくつかを逃していないポインタに注意する必要があります。
アイデア？あなたは、リンクされたリストから削除するときに何かを再構築する必要はありません。すべての答え
ため
Thxを。それはO(1)です。どのような構造を選択しても、おそらくポインタについて注意する必要があります。
両方のファクト（リンクされたリストとポインタ）の+1 – jv42
これは誤解を招きます。どちらか一方を削除している場合、または既にアイテムへの参照がある場合はO（1）操作のみです。リスト内のアイテムを削除する必要がある場合は、O（1）ではありません。この質問から、タイマーを削除することはリストのどこにでも起こりうると思われます。 – pfhayes
@PFHayes私は二重リンクリストを想定していました。一定時間内に二重リンクリストから要素を削除する方法がわからない場合は、質問してください - 私はあなたにお手伝いします:-)。それは次のようなフレーズです： "*一定の時間内に要素をリストから削除する方法はわかりません*。" – cnicutar
メモリの容量をできるだけ小さくしなければならない場合は、アレイを使用することになりますが、アレイを使用する唯一の欠点は、アレイのサイズ変更が高価（CPUサイクルが多い）です。タイマーの数の上限は、この最大値にサイズ設定された単一の配列を使用すると効率的になります。タイマーの数が非常に動的であれば、リスト（ベクトル・コレクション）が必要です。
一般に、アレイは最小限のメモリを使用します。単一ブロックなので、割り当てオーバーヘッドが少なく、リンクされたリスト内の次/前のポインタのような管理オーバーヘッドはありません。
もちろん、十分な大きさの配列の始めから途中から削除するのは、リンクされたリストから特定のノードを削除するよりも時間がかかりませんし、配列へのポインタ/インデックスも参照しなくなります。タイマーAPIのユーザーにどのような処理をするか、また特定のハンドルのタイマーデータを見つける方法を慎重に検討する必要があります。しかし、実際にメモリの使用が唯一の重要な問題であれば、アレイが勝ちます。
これまで私はこのようなことをしてきましたが、個人的には、明らかにいくつかの特定の制約に失敗しない限り、リンクされたリストから始めました。アクティブタイマーのリストが大きくなり過ぎるのを防ぐことができれば、 "timerdata"構造体へのポインタの配列もうまくいくかもしれません。
ヒープ/優先度キューを使用できます。これは配列と同じメモリ要件がありますが、挿入と削除はO（lg n）opsです。待ち行列内の項目は、各タイマオブジェクトの時間放置時間順に並べ替えることができます。実際のタイマーがトリガーすると、リスト内の他のタイマーのトリガー時間を調整する必要があります。したがって、timer1が1秒後に消灯し、timer2が1.5秒後に消灯するように設定されている場合、timer1がトリガーすると、0.5秒後にoffになるようにtimer2を調整する必要があります。おそらくそれは何か？
タイマーエレメントとは何ですか？何が入ってるの？それはちょうどいくつかのタイマー割込みや複雑なクラスによってカウントされた値であり、おそらくタイミングを取る独自のスレッドでカウントされますか？
どのような操作が最も頻繁に実行される可能性がありますか？ - 優先権としてそれらへのアクセスを最適化する。
リストを注文する際に利点がありますか？次のタイマーのタイムアウトが常にリストの先頭になるように（つまり、デルタキュー）、昇順の有効期限の順に並べ替えます。
RGDS、 マーティン
はこの宿題ですか？ – Nix
まあ、中に変更するのは、（二重）連動リストの強みの一つです。 – jmg