performance
cppBuilder
#migrated
TStringList

C++ Builder XE4, 10.2 Tokyo > TStringList > 既存の項目は追加しない > 案1:{ .Sorted = true | .Duplicates = dupIgnore } | 案2: 最後の項目とだけ比較

動作環境
C++ Builder XE4
RAD Studio 10.2 Tokyo Update 2 (追記: 2018/01/05)

概要

  • TStringListに項目を追加する
  • 既存の項目と同じ場合は追加しない

関連

https://stackoverflow.com/questions/20284819/find-duplicates-in-a-stringlist-very-fast

こちらのリンクにてDuplicatesの指定についての記載が見つかった。

案1: System.Classes.TStringList.Duplicates

ビルトインヘルプによると

Duplicates を設定すると,ソートされたリストに重複文字列を追加しようとしたときに発生する動作を指定できます。
...
dupIgnore
重複文字列をリストに追加しようという試みを無視する

ただし以下の注意書きがある。

メモ: Duplicates は,リストがソートされていない場合には何もしません。

code

試してみた。

Unit1.cpp
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    String msg = L"hello";

    TStringList *SL = new TStringList();

    SL->Sorted = true;
    //SL->Duplicates = System::Types::dupIgnore;
    SL->Duplicates = System::Classes::dupIgnore;


    for(int loop=0; loop<3; loop++) {
        SL->Add(msg);
    }

    for(int idx=0; idx < SL->Count; idx++) {
        Memo1->Lines->Add(SL->Strings[idx]);
    }

    delete SL;
}
//---------------------------------------------------------------------------

Button1を1回押した結果。

qiita.png

1行しか追加されていない。「既存の項目は追加しない」という目的は果たすことができる。

制限

.Sortedをtrueにしないといけない。

.Sortedをtrueにした場合の項目並びが意図していない並びになる可能性がある。
使用していいかはソート結果の検証が必要になる。

処理のオーダーは不明。

案2: 最後の項目とだけ比較

以下とする。

  • .Sorted = trueとは別の並びとなっている

IndexOf()を使うとO(N^2)の計算になる。

最後の項目とだけ比較するのでよければO(N)になるだろう。
(N: 追加試行の項目数)。

code

Unit1.cpp
//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "Unit1.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
    : TForm(Owner)
{
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
    String msg = L"hello";

    TStringList *SL = new TStringList();

    for(int loop=0; loop<3; loop++) {
        if (HasItem(SL, msg)) {
            continue;
        }
        SL->Add(msg);
    }

    for(int idx=0; idx < SL->Count; idx++) {
        Memo1->Lines->Add(SL->Strings[idx]);
    }

    delete SL;
}
//---------------------------------------------------------------------------

bool __fastcall TForm1::HasItem(TStringList *srcPtr, String item)
{
    if (srcPtr == NULL) {
        return false; // error
    }

    if (srcPtr->Count == 0) {
        return false;
    }
    int last = srcPtr->Count - 1;
    return srcPtr->Strings[last] == item;
}

注意点

追加する項目の途中に別のものが入った場合に、処理が破綻する。

例: Zun, Zun, Doko, Zun, ZunのDokoで破綻。

用途

  • 独自形式のタイムスタンプから始まる文字列
  • (タイムスタンプを含めて)重複文字列が送られてくる場合がある
  • .Sorted=trueにすると意図しない並びになる