Code Monkey home page Code Monkey logo

fifo_map's Introduction

Build Status Build status Coverage Status Try online GitHub license Github Releases Github Issues

fifo_map – a FIFO-ordered associative container for C++

Overview

C++ allows to defined associative containers such as std::map. The values are ordered according to their keys and an ordering relation. The fifo_map is an associative container which uses the order in which keys were inserted to the container as ordering relation.

As it has the same interface than std::map, it can be used as drop-in replacement. The code is header-only (see file src/fifo_map.hpp) and only relies on the STL.

Complexity

A fifo_map object has the space overhead of:

  • one std::unordered_map<Key, std::size_t> object to store the key order,
  • one pointer to this object in the Compare object.

Inserting a value (via operator[], insert) and removing a value (erase) rely on std::unordered_map::insert and std::unordered_map::erase which have O(1) average complexity and O(n) worst-case complexity. All other methods have the same performance as the equivalent std::map options.

Example

#include "src/fifo_map.hpp"

// for convenience
using nlohmann::fifo_map;

int main() {
    // create fifo_map with template arguments
    fifo_map<int, std::string> m;

    // add elements
    m[2] = "two";
    m[3] = "three";
    m[1] = "one";
    
    // output the map; will print
    // 2: two
    // 3: three
    // 1: one
    for (auto x : m) {
        std::cout << x.first << ": " << x.second << "\n";
    }
    
    // delete an element
    m.erase(2);
    
    // re-add element
    m[2] = "zwei";
    
    // output the map; will print
    // 3: three
    // 1: one
    // 2: zwei
    for (auto x : m) {
        std::cout << x.first << ": " << x.second << "\n";
    }
}

Try this code online.

License

The code is licensed under the MIT License:

Copyright © 2015-2017 Niels Lohmann

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Execute unit tests

To compile and run the tests, you need to execute

$ make
$ ./unit

===============================================================================
All tests passed (1286 assertions in 8 test cases)

For more information, have a look at the file .travis.yml.

fifo_map's People

Contributors

cbaecker avatar daniel599 avatar dkourilov avatar dmbrenn-lirr avatar h3x4n1um avatar nlohmann avatar spineight avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

fifo_map's Issues

Problem with the assignment operator

i might be doing something wrong, but i'm having some problems with the = operator.
When i build a fifo_map in a function and then return it, it seems to be ok, i can iterate over it. However, as soon as i try to use a find on it, i get a segmentation fault.

In the example below i test with both a map and a fifo_map, the map seems to be working as expected, fifo_map doesn't.

When i do the assign with the copy constructor it does seem to be working.

#include <iostream>
#include <map>
#include "fifo_map.hpp"
using nlohmann::fifo_map;

fifo_map<std::string, std:: string> generate_fifo() {
    fifo_map<std::string, std:: string> test;
    test["one"] = "first";
    test["two"] = "second";
    test["three"] = "third";
    return test;
}

std::map<std::string, std:: string> generate_map() {
    std::map<std::string, std:: string> test;
    test["one"] = "first";
    test["two"] = "second";
    test["three"] = "third";
    return test;
}

int main(int argc, char* argv[]) {
    std::map<std::string, std:: string> map_test;
    fifo_map<std::string, std:: string> fifo_test;
    map_test = generate_map();
    fifo_test = generate_fifo();

    for (const auto &item : map_test) {
        std::cout << item.first << " -> " << item.second << std::endl;
    }

    auto it = map_test.find("two");
    if (it != map_test.end()) {
        std::cout << "found" << std::endl;
    } else {
        std::cout << "not found" << std::endl;
    }



    for (const auto &item : fifo_test) {
        std::cout << item.first << " -> " << item.second << std::endl;
    }

    auto it2 = fifo_test.find("two");
    if (it2 != fifo_test.end()) {
        std::cout << "found" << std::endl;
    } else {
        std::cout << "not found" << std::endl;
    }
}

Tags with version number would be useful for packaging

Hi! I would like to add fifo_map as a package in conda-forge, to be used together with nlohmann_json there. It would be very useful if this repo had tags with version number (releases would be a plus), because the packages there need a version number.

Thanks!

swap function is error

/// swaps the contents
void swap(fifo_map& other)
{
    std::swap(m_map, other.m_map);
    std::swap(m_compare, other.m_compare);
    std::swap(m_keys, other.m_keys);
}

m_compare‘s member m_key point to m_map's m_key

find() adding a key

While combines find() followed by add/insertion of item strange thing happens.
Code

nlohmann::fifo_map<std::string,uint8_t> pe;
for(int i=0; i<1000; i++){

        std::string key = "custom_";
        key += std::to_string(i);

        //if(0 == pe.count(key)){
        if(pe.find(key) == pe.end()){

            pe[key] = (i+128) & 0xFF;
            std::cout << "OK"  << std::endl;
        } else {

            std::cout << "WRONG" << std::endl;
            auto i = pe.find(key);
            std::cout << key << " matches " << i->first << "!!" << std::endl;
            std::cout << key << " counts " << pe.count(key) << "!!" << std::endl;
            break;
        }
}  

This test won't pass (or enter "WRONG" condition) on my PC (tested on 32bit mingw530 and 64bit g++ 5.4.0) in third iteration.

Up to my knowledge it fails because new key is added into fifo_map::m_keys already with fifo_map::find(name) call.
This new key has first = name, second = 0. Second value should be timestamp > 0, so it is not valid key.
I don't know why, perhaps it could be desired behavior BUT when I want than add key of such name it has no effect because of usage insert() in fifo_map_compare::add_key.

I used simplest workaround and replace insert() by operator but I'm on serious doubts if it is the right correction (despite it works).

void fifo_map_compare<class Key>::add_key(const Key& key) {
        keys->operator[](key) = timestamp++; //bernau84 workaround
        //keys->insert({key, timestamp++});
}

To be honest - the same code runs as should on online compiler http://melpon.org/wandbox/permlink/l2f2Qxhq95qVKRgE.
This confuses me totally.

Clang libstdc++ failed with gcc

It is about

    set(CMAKE_CXX_FLAGS
        "-std=c++11 -stdlib=libc++"
    )

In general, only clang supports libstdc++.

-stdlib=<library>
Specify the C++ standard library to use; supported options are libstdc++ and libc++. If not specified, platform default will be used. 

It doesn't work with gcc and github CI. If I use fifo_map as submodule, immediately occurs error in cmake routine

[  3%] Building CXX object external/fifo_map/CMakeFiles/unit.dir/test/unit.cpp.o
c++: error: unrecognized command line option '-stdlib=libc++'
external/fifo_map/CMakeFiles/unit.dir/build.make:79: recipe for target 'external/fifo_map/CMakeFiles/unit.dir/test/unit.cpp.o' failed
make[2]: *** [external/fifo_map/CMakeFiles/unit.dir/test/unit.cpp.o] Error 1
CMakeFiles/Makefile2:197: recipe for target 'external/fifo_map/CMakeFiles/unit.dir/all' failed
make[1]: *** [external/fifo_map/CMakeFiles/unit.dir/all] Error 2
make[1]: *** Waiting for unfinished jobs....

Looking forward to your reply!

Isn't the time complexity a little high, when `for (auto x : m) { ... }`?

Isn't the time complexity a little high, when for (auto x : m) { ... }? One iteration calls fifo_map_compare n^2 times.

I think the time complexity of such a structure can be lower:

  • one map: {Key, Value is pointer to node of queue}
  • one queue: fifo, node{key, value}

For loop just iterates through the queue.

Looking forward to your reply!

Can not be compiled with clang-15 and libc++

I am playing with clang-15 in Yocto and ended up with build errors in this compoent as below

/mnt/b/yoe/master/build/tmp/work/core2-64-yoe-linux-musl/nlohmann-fifo/1.0.0+gitAUTOINC+d732aaf9a3-r0/recipe-sysroot/usr/include/c++/v1/__random/uniform_int_distribution.h:235:5: error: static assertion failed due to requirement '__libcpp_random_is_valid_urng<Catch::RandomNumberGenerator, void>::value':
    static_assert(__libcpp_random_is_valid_urng<_URNG>::value, "");
    ^             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/mnt/b/yoe/master/build/tmp/work/core2-64-yoe-linux-musl/nlohmann-fifo/1.0.0+gitAUTOINC+d732aaf9a3-r0/recipe-sysroot/usr/include/c++/v1/__algorithm/shuffle.h:154:35: note: in instantiation of function template specialization 'std::uniform_int_distribution<long>::operator()<Catch::RandomNumberGenerator>' requested here
            difference_type __i = __uid(__g, _Pp(0, __d));
                                  ^
/mnt/b/yoe/master/build/tmp/work/core2-64-yoe-linux-musl/nlohmann-fifo/1.0.0+gitAUTOINC+d732aaf9a3-r0/recipe-sysroot/usr/include/c++/v1/__algorithm/shuffle.h:166:14: note: in instantiation of function template specialization 'std::__shuffle<std::_ClassicAlgPolicy, std::__wrap_iter<Catch::TestCase *>, std::__wrap_iter<Catch::TestCase *>, Catch::RandomNumberGenerator &>' requested here
  (void)std::__shuffle<_ClassicAlgPolicy>(
             ^
test/thirdparty/catch/catch.hpp:6539:18: note: in instantiation of function template specialization 'std::shuffle<std::__wrap_iter<Catch::TestCase *>, Catch::RandomNumberGenerator &>' requested here
            std::shuffle( vector.begin(), vector.end(), rng );
                 ^
test/thirdparty/catch/catch.hpp:6557:44: note: in instantiation of function template specialization 'Catch::RandomNumberGenerator::shuffle<std::vector<Catch::TestCase>>' requested here
                    RandomNumberGenerator::shuffle( sorted );
                                           ^
1 warning and 1 error generated.

libc++ has started to drop stuff and move towards c++17 defaults. Perhaps time to start using the std::shuffle

catching polymorphic type ‘class std::out_of_range’ by value

Using the library with these compiler flags:
target_compile_options(unit PUBLIC -Werror -Wall -Wextra)

raises the error:
/fifo_map/test/unit.cpp:62:41: error: catching polymorphic type ‘class std::out_of_range’ by value [-Werror=catch-value=]
62 | CHECK_THROWS_AS(m.at("Z"), std::out_of_range);
| ^~~~~~~~~~~~
/fifo_map/test/unit.cpp:68:42: error: catching polymorphic type ‘class std::out_of_range’ by value [-Werror=catch-value=]
68 | CHECK_THROWS_AS(mc.at("Z"), std::out_of_range);

I have made a PR to address this:
#14

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.