• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[System] Dictionary

Level 3
Joined
Jan 31, 2012
Messages
42
This class is an associative array. It is equivalent to std::map in C++ and System.Collections.Generic.Dictionary in C#. To be simple, it's an array that has any possible types as indices.

It's primary purpose is creating databases. Call speed is very high because of using binary search.

To use you should include comparison library for your types:
JASS:
library_once IntegerComparison
    public function less takes integer op1, integer op2 returns boolean
        return op1 < op2
    endfunction

    public function equal takes integer op1, integer op2 returns boolean
        return op1 == op2
    endfunction
endlibrary

library_once RealComparison
    public function less takes real op1, real op2 returns boolean
        return op1 < op2
    endfunction

    public function equal takes real op1, real op2 returns boolean
        return op1 == op2
    endfunction
endlibrary

library_once HandleComparison
    public function less takes handle op1, handle op2 returns boolean
        return GetHandleId(op1) < GetHandleId(op2)
    endfunction

    public function equal takes handle op1, handle op2 returns boolean
        return op1 == op2
    endfunction
endlibrary

library_once StringComparison
    public function less takes string op1, string op2 returns boolean
        return StringHash(op1) < StringHash(op2)
    endfunction

    public function equal takes string op1, string op2 returns boolean
        return op1 == op2
    endfunction
endlibrary

//Unlikely somebody will use bools as indices, but, nevertheless... :)
/*
library_once BooleanComparison
    public function less takes boolean op1, boolean op2 returns boolean
        if op1 then
            return false
        endif
        return op2
    endfunction

    public function equal takes boolean op1, boolean op2 returns boolean
        return op1 == op2
    endfunction
endlibrary
*/
You can have your own structs as indices, but you must write a comparison library for it:
JASS:
struct pair
    real x
    real y
endstruct

library PairComparison
    public function less takes pair op1, pair op2 returns boolean
        if op1.x != op2.x then
            return op1.x < op2.x
        endif
        return op1.y < op2.y
    endfunction

    public function equal takes pair op1, pair op2 returns boolean
        return op1.x == op2.x and op1.y == op2.y
    endfunction
endlibrary
Here is the interface of the class:
JASS:
//! textmacro DeclareDictionary takes indexator_type, value_type, funcs
struct Dictionary_$indexator_type$_$value_type$
    static method Create() -> thistype
    method Destroy()
    method Clear()

    method operator [$indexator_type$] -> $value_type$
    method operator [$indexator_type$]= ($value_type$)
    method operator Exists[$indexator_type$] -> boolean

    method ForEach(code)
    static method operator ForEachKey -> $indexator_type$
    static method operator ForEachValue -> $value_type$
    static method Break()

    method operator Count -> integer
    method Rebuild()
Method ForEach calls the taken function for the each note in the dictionary.
Key and Value represent the arguments of the callback function.
Method Break stops the ForEach loop.
Method Rebuild makes all the wands of the binary tree equal length, enhacing the search.

And some examples:
JASS:
//! runtextmacro DeclareDictionary("integer", "integer", "IntegerComparison")

globals
    Dictionary_integer_integer udg_RewardDatabase
endglobals

function Trig_Reward_Actions takes nothing returns boolean
    local player p = GetOwningPlayer(GetKillingUnit())
    local integer gold
    if IsUnitEnemy(GetTriggerUnit(), p) then
        set gold = udg_RewardDatabase[GetUnitTypeId(GetTriggerUnit())]
        call DisplayTextToPlayer(p, .0, .0, "|cffffff00+" + I2S(gold) + "|r")
        call SetPlayerState(p, PLAYER_STATE_RESOURCE_GOLD, GetPlayerState(p, PLAYER_STATE_RESOURCE_GOLD) + gold)
    endif
    set p = null
    return false
endfunction

debug function DisplayReward takes nothing returns nothing
    debug call Trace(I2S(Dictionary_integer_integer.ForEachKey) + ": " + I2S(Dictionary_integer_integer.ForEachValue))
debug endfunction

//===========================================================================
function InitTrig_Reward takes nothing returns nothing
    local trigger trig = CreateTrigger()
    local integer i = 0
    loop
        call TriggerRegisterPlayerUnitEvent(trig, Player(i), EVENT_PLAYER_UNIT_DEATH, null)
        exitwhen i == 15
        set i = i + 1
    endloop
    call TriggerAddCondition(trig, Condition(function Trig_Reward_Actions))
    set trig = null

    set udg_RewardDatabase = Dictionary_integer_integer.Create()
    set udg_RewardDatabase['hpea'] = 10
    set udg_RewardDatabase['hfoo'] = 20
    set udg_RewardDatabase['hkni'] = 40
    set udg_RewardDatabase['hrif'] = 25
    set udg_RewardDatabase['hmtm'] = 45
    set udg_RewardDatabase['hgyr'] = 45
    set udg_RewardDatabase['hgry'] = 55
    set udg_RewardDatabase['hmpr'] = 30
    set udg_RewardDatabase['hsor'] = 30
    set udg_RewardDatabase['hmtt'] = 40
    set udg_RewardDatabase['hspt'] = 35
    set udg_RewardDatabase['hdhw'] = 35
    call udg_RewardDatabase.Rebuild()
    debug call Trace("Reward: " + I2S(udg_RewardDatabase.Count))
    debug call udg_RewardDatabase.ForEach(function DisplayReward)
endfunction
JASS:
//! runtextmacro DeclareDictionary("handle", "integer", "HandleComparison")

//! zinc
library TrackableTest {
    constant string EF1 = "Abilities\\Spells\\Demon\\DarkPortal\\DarkPortalTarget.mdl";
    constant string EF2 = "abilities\\weapons\\DemolisherMissile\\DemolisherMissile.mdl";
    Dictionary_handle_integer Dict;

    struct loc extends array { real x, y; }

    function onInit() {
        real x = GetRectMinX(gg_rct_Region_000), y, maxX = GetRectMaxX(gg_rct_Region_000),
            minY = GetRectMinY(gg_rct_Region_000), maxY = GetRectMaxY(gg_rct_Region_000);
        loc l = 0;
        trigger track = CreateTrigger(), hit = CreateTrigger();
        trackable t;

        Dict = Dictionary_handle_integer.Create();
        do {
            y = minY;
            do {
                t = CreateTrackable("units\\human\\Peasant\\Peasant.mdl", x, y, 4.712 /*bj_PI * 1.5*/);
                TriggerRegisterTrackableTrackEvent(track, t);
                TriggerRegisterTrackableHitEvent(hit, t);
                l.x = x;
                l.y = y;
                Dict[t] = l;
                l = l + 1;
                y = y + 70.;
            } while (y <= maxY);
            x = x + 70.;
        } while (x <= maxX);
        Dict.Rebuild();

        Preload(EF1);
        Preload(EF2);
        TriggerAddCondition(track,
            function() -> boolean {
                loc l = Dict[GetTriggeringTrackable()];
                DestroyEffect(AddSpecialEffect(EF1, l.x, l.y));
                return false;
            }
        );
        TriggerAddCondition(hit,
            function() -> boolean {
                loc l = Dict[GetTriggeringTrackable()];
                DestroyEffect(AddSpecialEffect(EF2, l.x, l.y));
                return false;
            }
        );
        track = null; hit = null; t = null;
    }
}
//! endzinc
JASS:
//! runtextmacro DeclareDictionary("integer", "string", "IntegerComparison")
//! runtextmacro DeclareDictionary("handle", "integer", "HandleComparison")

struct mystruct
    private static Dictionary_handle_integer D
    private unit caster
    private unit target
    private integer time
    private real x
    private real y

    private static method Timer takes nothing returns nothing
        local timer t = GetExpiredTimer()
        local thistype this = D[t]
        call DestroyEffect(AddSpecialEffect(/*
        */ "Abilities\\Spells\\NightElf\\TrueshotAura\\TrueshotAura.mdl", this.x, this.y))
        if this.time == 1 then
            call SetUnitX(this.target, this.x)
            call SetUnitY(this.target, this.y)
            call PauseTimer(t)
            call DestroyTimer(t)
            set D[t] = 0
            call deallocate(this)
        else
            set this.time = this.time - 1
        endif
        set t = null
    endmethod

    static method Actions takes nothing returns nothing
        local timer t = CreateTimer()
        local thistype this = allocate()
        set this.caster = GetTriggerUnit()
        set this.target = GetSpellTargetUnit()
        set this.time = 4
        set this.x = GetWidgetX(this.target)
        set this.y = GetWidgetY(this.target)
        set D[t] = this
        call TimerStart(t, 1., true, function thistype.Timer)
        set t = null
    endmethod

    private static method onInit takes nothing returns nothing
        set D = Dictionary_handle_integer.Create()
        call Preload("Abilities\\Spells\\NightElf\\TrueshotAura\\TrueshotAura.mdl")
    endmethod
endstruct

//===========================================================================

scope Spells initializer Init
    globals
        private Dictionary_integer_string Database
    endglobals

    private function Spell takes nothing returns boolean
        local string s = Database[GetSpellAbilityId()]
        if s != null then
            call ExecuteFunc(s)
        endif
        return false
    endfunction

    debug private function Display takes nothing returns nothing
        debug call Trace(I2S(Dictionary_integer_string.ForEachKey) + ": \"" + Dictionary_integer_string.ForEachValue + "\"")
    debug endfunction

    private function Init takes nothing returns nothing
        local trigger trig = CreateTrigger()
        local integer i = 0
        loop
            call TriggerRegisterPlayerUnitEvent(trig, Player(i), EVENT_PLAYER_UNIT_SPELL_EFFECT, null)
            exitwhen i == 15
            set i = i + 1
        endloop
        call TriggerAddCondition(trig, Condition(function Spell))
        set trig = null

        set Database = Dictionary_integer_string.Create()
        set Database['A000'] = mystruct.Actions.name
        set Database['A001'] = "Trig_Spell1_Actions"
        set Database['A002'] = "Trig_Spell2_Actions"
        set Database['A003'] = "Trig_Spell3_Actions"
        set Database['A004'] = "Trig_Spell4_Actions"
        set Database['A005'] = "Trig_Spell5_Actions"
        call Database.Rebuild()
        static /*
        */ if DEBUG_MODE then
            call Trace("Spell: " + I2S(Database.Count))
            call Database.ForEach(function Display)
            if Database.Exists['A006'] then
                call Trace("Impossible!")
            endif
        endif
    endfunction
endscope
Code:
JASS:
//! textmacro DeclareDictionary takes indexator_type, value_type, funcs
library_once Dictionary$indexator_type$$value_type$ uses $funcs$
    private struct Node extends array
        static integer Max = 0
        boolean Empty

        static boolean ForEach_Continue = true
        static integer ForEach_Stack = -1
        static $indexator_type$ array ForEach_Key
        static $value_type$ array ForEach_Value
        static $indexator_type$ array indexAr
        static $value_type$ array valueAr

        $indexator_type$ index
        $value_type$ value
        Node n1
        Node n2

        static method create takes nothing returns thistype
            local thistype this = 0
            loop
                if this == Max then
                    static /*
                    */ if DEBUG_MODE then
                        if Max > 8191 then
                            call DisplayTimedTextToPlayer(GetLocalPlayer(), .0, .0, 60. /*
                            */ "Невозможно создать узел объекта Dictionary.")
                            return -1
                        endif
                    endif
                    set Max = Max + 1
                    exitwhen true
                endif
                exitwhen this.Empty
                set this = this + 1
            endloop
            set this.Empty = false
            set this.n1 = -1
            set this.n2 = -1
            return this
        endmethod

        method destroy takes nothing returns nothing
            if n1 != -1 then
                call n1.destroy()
            endif
            if n2 != -1 then
                call n2.destroy()
            endif
            set Empty = true
        endmethod

        method count takes nothing returns integer
            local integer i = 0
            if n1 != -1 then
                set i = n1.count()
            endif
            if value != thistype(-1).value then
                set i = i + 1
            endif
            if n2 != -1 then
                return i + n2.count()
            endif
            return i
        endmethod

        method to_array takes integer n returns integer
            if n1 != -1 then
                set n = n1.to_array(n)
            endif
            if value != thistype(-1).value then
                set indexAr[n] = index
                set valueAr[n] = value
                set n = n + 1
            endif
            set Empty = true
            if n2 != -1 then
                return n2.to_array(n)
            endif
            return n
        endmethod

        static method from_array takes integer n, integer jump, integer min, integer max returns thistype
            local thistype this = create()
            if n - jump >= min then
                set this.n1 = from_array(n - jump, (jump + 1) / 2, min, n)
            endif
            set this.index = indexAr[n]
            set this.value = valueAr[n]
            if n + jump < max then
                set this.n2 = from_array(n + jump, (jump + 1) / 2, n + 1, max)
            endif
            return this
        endmethod

        method for_each takes code c returns nothing
            if n1 != -1 then
                call n1.for_each(c)
            endif
            if ForEach_Continue and value != thistype(-1).value then
                set ForEach_Stack = ForEach_Stack + 1
                set ForEach_Key[ForEach_Stack] = index
                set ForEach_Value[ForEach_Stack] = value
                call ForForce(bj_FORCE_PLAYER[15], c)
                set ForEach_Stack = ForEach_Stack - 1
            endif
            if ForEach_Continue and n2 != -1 then
                call n2.for_each(c)
            endif
        endmethod
    endstruct

    private struct ExistsStruct extends array
        method operator [] takes $indexator_type$ index returns boolean
            if this != -1 then
                loop
                    if $funcs$_equal(index, Node(this).index) then
                        return true
                    elseif $funcs$_less(index, Node(this).index) then
                        if Node(this).n1 == -1 then
                            return false
                        endif
                        set this = Node(this).n1
                    elseif Node(this).n2 == -1 then
                        return false
                    else
                        set this = Node(this).n2
                    endif
                endloop
            endif
            return false
        endmethod
    endstruct

    struct Dictionary_$indexator_type$_$value_type$ extends array
        private static integer Max = 1
        private boolean Empty
        private Node root

        static method Create takes nothing returns thistype
            local thistype this = 1
            loop
                if this == Max then
                    if Max > 8191 then
                        static /*
                        */ if DEBUG_MODE then
                            call DisplayTextToPlayer(GetLocalPlayer(), .0, .0, /*
                            */ "Невозможно создать узел объекта Dictionary.")
                        endif
                        return 0
                    endif
                    set Max = Max + 1
                    exitwhen true
                endif
                exitwhen this.Empty
                set this = this + 1
            endloop
            set this.Empty = false
            set this.root = -1
            return this
        endmethod

        method Destroy takes nothing returns nothing
            if root != -1 then
                call root.destroy()
            endif
            set Empty = true
        endmethod

        method operator [] takes $indexator_type$ index returns $value_type$
            local Node n = root
            if n != -1 then
                loop
                    if $funcs$_equal(index, n.index) then
                        return n.value
                    elseif $funcs$_less(index, n.index) then
                        if n.n1 == 0 then
                            return Node(-1).value
                        endif
                        set n = n.n1
                    elseif n.n2 == 0 then
                        return Node(-1).value
                    else
                        set n = n.n2
                    endif
                endloop
            endif
            return Node(-1).value
        endmethod

        method operator []= takes $indexator_type$ index, $value_type$ value returns nothing
            local integer i = 0
            local Node n = root
            local Node array parent
            if n == -1 then
                if value != Node(-1).value then
                    set root = Node.create()
                    set root.index = index
                    set root.value = value
                endif
            else
                set parent[0] = n
                loop
                    if $funcs$_equal(index, n.index) then
                        if value == Node(-1).value and n.n1 == -1 and n.n2 == -1 then
                            set n.Empty = true
                            loop
                                if i == 0 then
                                    set root = -1
                                    return
                                elseif n == parent[i].n1 then
                                    set parent[i].n1 = -1
                                else
                                    set parent[i].n2 = -1
                                endif
                                exitwhen parent[i].n1 != -1 or parent[i].n2 != -1
                                set parent[i].Empty = true
                                set n = parent[i]
                                set i = i - 1
                            endloop
                        else
                            set n.value = value
                        endif
                        return
                    elseif $funcs$_less(index, n.index) then
                        if n.n1 == -1 then
                            if value != Node(-1).value then
                                set n.n1 = Node.create()
                                set n.n1.index = index
                                set n.n1.value = value
                            endif
                            return
                        endif
                        set i = i + 1
                        set parent[i] = n
                        set n = n.n1
                    elseif n.n2 == -1 then
                        if value != Node(-1).value then
                            set n.n2 = Node.create()
                            set n.n2.index = index
                            set n.n2.value = value
                        endif
                        return
                    else
                        set i = i + 1
                        set parent[i] = n
                        set n = n.n2
                    endif
                endloop
            endif
        endmethod

        method Clear takes nothing returns nothing
            if root != -1 then
                call root.destroy()
                set root = -1
            endif
        endmethod

        method operator Count takes nothing returns integer
            if root == -1 then
                return 0
            endif
            return root.count()
        endmethod

        method operator Exists takes nothing returns ExistsStruct
            return root
        endmethod

        method ForEach takes code c returns nothing
            if root != -1 then
                call root.for_each(c)
                set Node.ForEach_Continue = true
            endif
        endmethod

        static method operator ForEachKey takes nothing returns $indexator_type$
            return Node.ForEach_Key[Node.ForEach_Stack]
        endmethod

        static method operator ForEachValue takes nothing returns $value_type$
            return Node.ForEach_Value[Node.ForEach_Stack]
        endmethod

        static method Break takes nothing returns nothing
            set Node.ForEach_Continue = false
        endmethod

        method Rebuild takes nothing returns nothing
            local integer size
            if root != -1 then
                set size = root.to_array(0)
                set root = Node.from_array((size - 1) / 2, (size - size / 2 + 1) / 2, 0, size)
            endif
        endmethod
    endstruct
endlibrary
//! endtextmacro
 
Last edited:
Level 3
Joined
Jan 31, 2012
Messages
42
I think you didn't read the code. I have this API with brackets.
JASS:
//! runtextmacro DeclareDictionary("handle", "integer", "HandleComparison", "8191")

function abc takes nothing returns nothing
    local Dictionary_handle_integer d = Dictionary_handle_integer.Create()
    local unit u = CreateUnit(...)
    set d[u] = 2356
    set d[CreateTimer()] = 1234
    call BJDebugMsg(I2S(d[u]))
    call d.Destroy()
endfunction
 
I did read the code.
I was on my phone though, so I'll read it again.

edit

Oh wait, I get it now.
By the way, you really don't need to use a Binary search tree.
A hashtable or Table would be fine and using one would generate less code and could be much faster :p

I like how you took advantage of library_once to generate less code and avoid syntax errors.

Actually, come to think of it, this does pretty much the same thing as Table by Bribe :/
The only difference is that here, instead of passing GetHandleId(handle), you pass handle as an index (Same for StringHash(string), and other things)
 
Level 3
Joined
Jan 31, 2012
Messages
42
I wrote this system exactly for replacing hash. Sometimes you don't need the 2D array.
I agree that it's not very efficient when the count of elements is little so it would unlikely be used in spells. But when you need a DB like in ex. 1 (reward) or 3 (funcs) that is the best way.
 
Either way, here are a few tips:

1- You don't need to size the struct. It gives users the ability to declare huge sizes thus spamming lots of globals D:
2- Instead of function interfaces, you could use modules for the ForEach feature just like LuizBills did in this resource: http://www.hiveworkshop.com/forums/submissions-414/system-buffgenerator-207342/
Function interfaces spam shit code D:
3- You're never using allocate and dellocate, so you might as well make the struct extend an array ;p (struct XXX extends array)
 
Level 3
Joined
Jan 31, 2012
Messages
42
1. If the users don't hit the limit of 8191, it won't spam. But what if they really need it?
2. Probably, you are right. But in that case data about dictionary implements into every user struct, breaking the incapsulation principle.
3.
JASS:
private struct Node[$size$]
JASS:
private struct ExistsStruct extends array
JASS:
struct Dictionary_$indexator_type$_$value_type$ extends array
 
Yeah, I'm referring to the Node struct :/
You really don't need to size it because users won't need anything more than 8191 instances, and if they did, then you could make this based on Table by Bribe (Instead of using arrays to store data, you would use Tables)

That way, you could have a little over 2 billion instances of this struct :D
 
Level 3
Joined
Jan 31, 2012
Messages
42
Updated.

Node is now an array struct.
Method ForEach now takes code. See the interface and examples for more information.

I need your help. Which of these codes is faster?
JASS:
method to_array takes integer n returns integer
    if n1 != -1 then
        set n = n1.to_array(n)
    endif
    if value != thistype(-1).value then
        set indexAr[n] = index
        set valueAr[n] = value
        set n = n + 1
    endif
    set Empty = true
    if n2 != -1 then
        return n2.to_array(n)
    endif
    return n
endmethod
JASS:
method to_array takes nothing returns integer
    local integer stack_top = 0
    local integer n = 0
    local integer array ret_addr
    local thistype array arg_stack
    set ret_addr[0] = 0
    loop
        loop
            if ret_addr[stack_top] == 0 then
                set ret_addr[stack_top] = 1
                if .n1 != -1 then
                    set arg_stack[stack_top] = this
                    set stack_top = stack_top + 1
                    set ret_addr[stack_top] = 0
                    set this = .n1
                    exitwhen true
                endif
            endif
            if ret_addr[stack_top] == 1 then
                set ret_addr[stack_top] = 2
                if .value != thistype(-1).value then
                    set indexAr[n] = .index
                    set valueAr[n] = .value
                    set n = n + 1
                endif
                set .Empty = true
                if .n2 != -1 then
                    set arg_stack[stack_top] = this
                    set stack_top = stack_top + 1
                    set ret_addr[stack_top] = 0
                    set this = .n2
                    exitwhen true
                endif
            endif
            if stack_top == 0 then
                return n
            endif
            set stack_top = stack_top - 1
            set this = arg_stack[stack_top]
        endloop
    endloop
    return 0
endmethod
 
Last edited:

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
What is thistype(-1) good for? Why not just use "0"? Invalid array indices pretty much translate to "null" the last time I checked, unless you've found something new?

What makes you think the second function would be faster than the first? I can say that a local integer array is pretty slow to allocate & deallocate, so that will be a hard point. But with recursive function calling you have to consider a function call on its own doesn't weigh very much and a creating a local is about the same speed as referencing an array index. I think the recursive function is better and it is a shorter code as well. I split things into different functions whenever there's an opportunity to remove duplicated code.
 
Level 10
Joined
May 27, 2009
Messages
494
ehhh

JASS:
                            call DisplayTimedTextToPlayer(GetLocalPlayer(), .0, .0, 60. /*
                            */ "Невозможно создать узел объекта Dictionary.")
O.O why in russian lol anyways they're just debug things

is this thing similar with Table??
or they're two very different things
(sorry I haven't touched any C++ >:D )
 
Level 3
Joined
Jan 31, 2012
Messages
42
I use Array[-1] to get the default value. It can be any type, so if I write simply 0, it would get syntax errors when compiled for handle, string or bool dict.

OK. But what if I make these arrays global? Will it improve the perfomance?

Edit:
why in russian lol
Oh, sorry. I forgot to translate it. That means "Cannot create the Dictionary object node.".
 

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,456
Global arrays will mean the array doesn't need to be allocated/deallocated each function call, so that performance impact will be diminished.

I have seen implementations of associative array in vJass and the closest existing thing I can compare it to would be Vexorian's Table library (HandleTable, StringTable and Table).

The issue with indexing with reals is that you have to consider the exponent after the ".", Nestharus seems to think it should be "R2I(real * 100)" but it could need to be greater than 100 depending on how accurate you want it to be or less than 100 for the same reason.

Boolean indexing is really useless, I can see why you commented it out but "existing for the sake of completeness" is not really ideal.

For indexing using handles or strings, like I said those can use HandleTable and StringTable, respectively, or the user can do those operations manually and use GetHandleId and StringHash manually with normal hashtables or with the NewTable library developed by Nestharus and I.

For more dynamic storage like being able to track the different nodes which have been added to a certain dictionary, I developed LinkedListStruct (which in real life has pretty limited application).

I respect the effort you put into this but I don't see what this offers that doesn't already exist.
 
Level 31
Joined
Jul 10, 2007
Messages
6,306
The only thing I can't make an argument against right now is reals. However, I think that the speed of this as compared to GetHandleId and a hashtable read should be compared. This may only end up being useful for reals, if it has absolute accuracy (I haven't delved into the code). Furthermore, it'll only be useful in either case if it's O(1).
 
Last edited:

Bannar

Code Reviewer
Level 26
Joined
Mar 19, 2008
Messages
3,140
I dont like it either. Comparator (which almost always involves "less" oprator) should be provided instead of functions with boolean return statement. Comparators return integer for a reason. Next, Its not flexible nor it allows for user specific implementation (comparators escpecialy, template for structs, handle types etc.). There are more boundaries with this than actuall std::map-ish flexibility.

There the several things present here, with which I've been fighting when implementing my map, list, vec, array (...) for the first time.
 
Top